Давайте продолжим рассмотрение задач по программированию, которые часто встречаются на тестах при приеме на работу.
Напомним, что предыдущие публикации можно посмотреть здесь и здесь.
Задача 1 (Число пи).
Классическая задача вычисления числа пи. Требуется написать функцию, вычисляющую число пи с точностью до 10 знака после запятой.
Решение
Это классическая задача, очень часто задаваемая работодателем, чтобы проверить базовые навыки программирования, а также основы математики. По определению, число пи равняется отношению длины окружности к ее диаметру. Есть масса решений, основанных на разложении числа пи в ряд (Виета, Валлиса, Лейбница и др.).
В настоящее время самым эффективным признан итеративный алгоритм Брента — Саламина, который, используя лишь арифметику, на каждом шаге удваивает кол-во вычисляемых знаков:
Начальные условия:
a[0] = 1, b[0]=1/sqrt(2), t[0]=1/4, p[0]=1
Итерации:
a[n+1] = (a[n]+b[n])/2, b[n+1] = sqrt(a[n]*b[n]), t[n+1] = t[n] – p[n]*(a[n]-a[n+1])^2, p[n+1] = 2p[n]
и
pi = (a[n] + b[n])^2/4t[n]
Такой алгоритм просто запрограммировать, он очень похож на итеративное вычисление ряда Фибоначчи, который мы рассматривали в первом выпуске заданий по программированию.
Уже на четвертой итерации мы получаем точное значения 10 знаков после запятой. Это очень эффективное решение O(1).
Мы также можем воспользоваться для решения случайными числами и фактом того, что число пи равно площади круга радиуса 1. Это не точный алгоритм и достаточно затратный по вычислениям, но он обычно хорошо оценивается на интервью, так как демонстрирует хорошее знание математики и основ программирования.
Задача 2 (Соединенные точки на плоскости)
На плоскости задано множество N точек (1…N) и M линий, соединяющих точки попарно. Для каждой пары точек соответственно определен их ранг, как общее число линий, выходящих из двух точек.
Множество задано целым числом N, и двумя массивами равной длины A[1…M] и B[1…M], где пара A[i] и B[i] определяет линию, соединяющую две данные точки, а M – общее число соединений.
Необходимо найти максимальный ранг заданного множества.
Например, заданные множества A = [1,2,3,4] и B[6,6,5,5] при N=6, как видно из рисунка
определяют ранг 2: (1,6), (2,6) или (3,5), (4,5).
Решение
Данная задача относится к разновидности задач о множестве точек на плоскости и комбинаторике их соединений.
Давайте сначала вспомним какое максимальное кол-во соединений возможно между N точками на плоскости. Так как линии не имеют направлений и между двумя точками возможно только одно соединение, то макcимальное число соединяющих линий: N(N-1)/2. То есть, при N = 100, к примеру, M <= 100 * 99 / 2 = 4950.
Если соединены все точки, то каждая имеет N-1 соединений, то есть максимальный ранг полностью связанного множества: 2N-3
Такие рассуждения очень полезны провести перед началом решения, даже если они и не войдут в алгоритм, они показывают ваше понимание задачи и хорошо оцениваются при устном интервью.
Как несложно понять, взяв пару i (циклом по одному из массивов), надо просто посчитать число включений A[i] и B[i] в оба массива и вычесть единицу (так как i-я пара будет посчитана дважды):
Вы видите, что код выглядит достаточно просто, но решение имеет вычислительную затратность O(M*N), что не оптимально.
Решение можно существенно упростить, если вначале заполнить массив размерностью N (или максимального n из массивов A и B), определяющий число вхождений i-й точки в оба массива.
Это существенно более эффективное решение затратностью O(N), что обычно оценивается на тесте как 100%.
Задание 3 (Глубина ямы)
Задан массив A из N целых чисел. Три числа (P, Q, R) называются ямой, если:
– 0 <= P < Q < R <=N,
– Последовательность A[P] > A[P+1] > … > A[Q] строго убывающая
– Последовательность A[Q] < … < A[R-1] < A[R] строго возрастающая
Глубина ямы определяется как min(A[P] – A[Q], A[R] – A[Q]).
Необходимо найти глубину самой глубокой ямы в заданном массиве A. В случае, если в массиве нет ям, то ответ должен равняться -1.
Например, пусть A = [0, 1, 3, -2, 0, 1, 0, -3, 2, 3]. Тогда тройка индексов (2,3,4) является ямой глубиной 2, (2,3,5) – ямой глубиной 3, (5,7,8) – ямой глубиной 4. Видно, что тройка (5,7,8) определяет самую глубокую яму массива A. То есть, ответ равен 4.
При этом N задано на интервале [1…1,000,000], а элементы массива A в пределах [-1,000,000,000…1,000,000,000]
Решение
Давайте вначале, как и в предыдущих случаях, закодируем правильное решение, не уделяя внимания эффективности.
Самый простой способ – это нахождение локальных минимумов циклом по заданному массиву, и затем вычисление глубин левой и правой «стенок», и определение их минимума как глубины локальной ямы. Такой код выглядит достаточно просто:
Такое решение будет корректным, но, очевидно, неэффективным с time complexity O(N^2).
Эффективность решения достаточно просто улучшить, если не искать вначале локальные минимумы, а сделать более сложный анализ при прохождении массива.
Такое решение имеет затратность O(N), что оптимально для данной задачи.
В целом, можно дать общую рекомендацию не искать эффективное решение с самого начала, а сфокусироваться на правильности и простоте алгоритма. Не усложняйте решение. Не эффективный, но верный код обычно оценивается в 2/3 максимальной оценки. Если у вас останется время, то можно заняться оптимизацией решения, что значительно проще, чем добиваться эффективности изначально.
(to be continued…)
