Задания по программированию. Третья часть.

Продолжаем разбор решений типичных задач по программированию при приеме на работу.

Давайте продолжим рассмотрение задач по программированию, которые часто встречаются на тестах при приеме на работу.

Напомним, что предыдущие публикации можно посмотреть здесь и здесь.

Задача 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…)

Поделиться...
Поделиться в facebook
Поделиться в twitter
Поделиться в vk