Программирование, Программная инженерия
Решение вопроса на собеседовании Amazon с помощью кода
Давайте рассмотрим вопрос об алгоритмах, который использовался в интервью в Amazon, Google и Uber. Включена реализация Python.
Вопрос
У нас есть два отсортированных массива, A и B. Если мы объединим два массива и отсортируем их, мы получим новый массив с именем C. Например, если A = [1,4,6,7] и B = [2,2,13], тогда C = [1,2,2,4,6,7,13].
Наша задача - определить медиану C за O (log (n + m)) времени.
Загвоздка в том, что нам не дают C, нам просто дают A и B. А ограничение временной сложности означает, что явная разработка C невозможна, поскольку нам пришлось бы отсортировать массив длиной (A) + length (B ).
Итак, наша задача - найти эффективный способ найти медиану C.
Решение проблемы
Часть 0: Медианы и отсортированные массивы
Хорошим свойством медианы является то, что можно легко уменьшить отсортированный массив и сохранить ту же медиану - просто удалите то же количество элементов сверху медианы, что и снизу.
Рассмотрим [1,4,5,6,9]. 5 находится посередине и является средним значением. Но если мы удалим верхний и нижний элементы, получится массив [4,5,6], а 5 все еще будет медианным значением.
Если мы доведем это до крайности и создадим минимально возможный массив с той же медианой, для массива с четным числом элементов, например [1,2,3,4,5,6], мы оставим только два средних elements [3,4], а для массива с нечетным числом элементов, например [1,3,5,7,9], мы можем удалить все элементы, кроме единственного элемента в середине, оставив [5].
Что если наш массив разделен на две отсортированные части? Наша стратегия будет по сути такой же, только немного сложнее. Мы хотим идентифицировать элементы, которые, как мы уверены, не являются двумя средними элементами (если четные) или средними элементами (если нечетные), и удалить равные числа сверху и снизу, таким образом сохраняя медианное значение одинаковым.
Часть I: Наш алгоритм
- Мы определяем медианы.
- Мы сравниваем медианы.
Это позволяет нам с уверенностью определить, что определенное количество элементов находится выше медианы, а некоторые - ниже медианы.
Как так? Предположим, что медиана B больше медианы A. Теперь выберите элемент выше медианы B, который также находится в B. Этот элемент гарантированно больше, чем все элементы ниже медианы в B по определению. Но также гарантированно будет больше, чем все элементы в A ниже медианы в A, потому что медиана B больше, чем медиана в A.
Вот краткий пример.
Пусть A = [1,2,3,4] и B = [1,3,3,5,5,5, f].
Медиана A равна 2,5, а медиана B равна 5. Мы можем сразу вывести, что 1 ≤ f, потому что 1 ≤ медиана A ≤ медиана B ≤ f.
3. Мы определяем, в каком массиве меньше элементов.
Это необходимо, потому что мы хотим удалить такое же количество элементов из выше медианы C, что и из ниже медианы C. В приведенном выше примере, если мы удалим 3 элементы выше единственного среднего элемента B, затем удалили только один элемент ниже двух средних элементов A, тогда мы бы удалили 3 элемента сверху медианы C и 1 элемент снизу. В результате у результирующего массива может быть другая медиана.
4. Мы удаляем как можно больше элементов из более короткого массива и удаляем то же число из более длинного массива
Этот процесс можно увидеть на схеме ниже. Это, следуя логике в (3), гарантирует, что мы удаляем столько же элементов сверху медианы C и снизу медианы C
5 Мы повторяем шаги (1–4) до тех пор, пока меньший из двух массивов не станет достаточно маленьким. Затем присоединяемся и сортируем
Повторяя шаги 1–4, мы каждый раз удаляем чуть менее половины элементов из более короткого массива. Это означает, что за время O (log (min (n, m))) мы переходим к базовому случаю. Например, если один массив имеет длину 16, а другой - 1000000, потребуется 4 шага, чтобы уменьшить меньший массив до двух элементов. Затем требуется O (log (max (n, m))), чтобы отсортировать 2 оставшихся элемента в больший массив и определить медиану.
Часть II: Реализация кода
В моем коде Python «базовый случай» приведен ниже. Когда длина первого или второго массива ≤3, мы просто идем дальше, сортируем два массива и непосредственно находим медиану.
Перед тем, как удалить элементы сверху и снизу, мы делаем перемаркировку. Мы называем массив с большим количеством элементов long_array, его длина long_num, а массив с меньшим количеством элементов - shorter_array с длиной short_num. Это потому, что, хотя мы могли бы просто разделить оба примерно пополам и оставить по одной половине каждого, если один массив намного длиннее другого, мы не можем удалить такое же количество элементов сверху нашей медианы, как и снизу нашей медианы /
Затем мы определяем медианы long_array и shorter_array.
Для этого мы используем определенную мной вспомогательную функцию median_val. Все, что он делает, - это берет массив и его длину и возвращает его медиану.
После того, как мы определили медианы двух массивов, у нас есть два случая: в первом случае shorter_array имеет меньшую медиану, а во втором случае shorter_array имеет большую медиану.
Смотрим на первый случай. Здесь мы идентифицируем наши новые сокращенные массивы и передаем их обратно в нашу функцию как рекурсивный вызов.
Давайте разберемся с этим.
shorter_array[short_num - (short_num//2 + 1):]
это первый аргумент. Так как в этом случае short_array имеет меньшую медиану, мы хотим сохранить только большую ее половину.
[short_num - (short_num//2 + 1):]
выглядит некрасиво и неудобно, но это всего лишь арифметика. Причина, по которой это немного беспорядочно, заключается в том, что нам нужно уравнение, которое работает как для нечетного, так и для четного массива.
Второй аргумент нашей функции ниже
short_num//2 + 1
Это просто длина массива, указанного в первом предложении. Вы также можете использовать метод len, если кодируете на python
Третий и четвертый аргументы нашей функции:
longer_array[0:long_num - ((short_num-1)//2)], long_num - ((short_num-1)//2)
Это делает то же самое, что и первый и второй аргументы - идентифицирует часть массива, который мы храним, и его длину. Обратите внимание, как длина более длинного массива уменьшается на (short_num-1) // 2, что в точности совпадает с величиной, на которую мы уменьшили длину более короткого массива.
Предложение else делает то же самое, но для случая, когда более короткий массив имеет большую медиану.
Сложность времени
Если m - это размер нашего более короткого массива, мы каждый раз удаляем (почти) половину его элементов, поэтому требуется log (m) времени, чтобы уменьшить его до нашего базового случая. В нашем базовом случае мы удалили около m элементов из другого массива, оставив массив размером примерно n-m. При условии, что вы заранее зафиксируете размер базового варианта, потребуется O (log (n)) времени, чтобы добавить конечное число элементов (в нашем случае 3) в отсортированный список. Наконец, извлечение медианы занимает время O (1) над отсортированным списком. Это означает, что наш алгоритм O (log (m) + log (n)), поскольку n≥m, это O (log (n)) = O (log (n + m).
Чтобы понять, почему O (log (n)) = O (log (n + m)), обратите внимание, что log (n + m) ≤ log (2n) = log (n) + log (2).
Спасибо, что нашли время, чтобы прочитать это, надеюсь, вам понравилось :) Дайте мне знать ваши комментарии ниже. Если несколько человек хотят увидеть реализацию алгоритма на C, я могу это добавить. Я изучаю математику в Кембридже и очень люблю кодировать :) - Вы можете следить за мной (в основном) по математике и (немного) кодированию в твиттере, где я ethan_the_mathmo
