Во многих крупных российских IT-компаниях давно набирает популярность тенденция задавать алгоритмические задачки на технических интервью, даже если вы мобильный или фронтенд-разработчик, не говоря уже о бекендерах и ml-инженерах. Это может быть как одна задача в рамках основного технического интервью, так и отдельная секция длительностью в час. Увы, ключом к прохождению подобных интервью является не рабочий опыт, а именно целенаправленная подготовка, поскольку предлагаемые к решению задачки в работе не встречаются, а лежащие в их основе алгоритмы в рамках рабочих задач типичного программиста опять же реализуются достаточно редко.
Поэтому, если интервью уже назначено, а времени мало, то имеет смысл подготовиться к решению наиболее популярных задач и разобрать наиболее часто встречающиеся темы. К счастью, большинство популярных задач далеко не так сложны, каковыми могут показаться на первый взгляд, а для успешного прохождения интервью, как правило, достаточно владеть несколькими базовыми методами.
Один из таких очень популярных методов – «метод двух указателей» – мы и рассмотрим в данной статье. Почему же именно его?
Во-первых, по субъективному впечатлению, на знание этого метода в российских компаниях дается больше всего задач.
Из 43 задач, собранных по знакомым разработчикам и открытым источникам, 12 были именно на «метод двух указателей», т.е. составляли почти 30%.
Так же эти задачи довольно часто повторялись (давались нескольким людям), так что шансы встретить такую задачу на интервью еще больше увеличиваются.
Вторая важная причина заключается в том, что даже если вы изучали алгоритмы для себя, т.е. читали классические книги Кормена или других авторов и прорешивали классические задачи, то, скорее всего, не знакомы с этим методом. Действительно, даже в оглавлении фолианта Кормена на тысячу страниц вы не найдете его упоминания. На это есть банальная причина, и мы рассмотрим ее позже. Но этот метод рассматривается в книгах по спортивному программированию, которые, увы, напоминают скорее решебник, чем учебник.
Третья причина заключается в том, что многие интервьюеры относят эти задачи к очень простым (хотя, если вы сталкиваетесь с задачей впервые, то простейшей ее назвать нельзя), и если вы не смогли написать решение, то, скорее всего, последует однозначный отказ. А в купе с тем, что описание этого сложно найти в книгах, ситуация только усугубляется.
Четвертая причина – часто метод двух указателей дает самые оптимальные решения из возможных. Например, вместо O(n^2) по времени всего лишь O(n). Или же оценку O(n) по памяти оптимизирует до идеальной O(1) ! А интервьюеры любят самые лучшие (или точнее сказать бескомпромиссные) решения, даже если они чреваты ошибками или избыточны для многих практических задач.
И, наконец, пятая причина – некоторые задачки на этот метод могут быть достаточно интересными и вызывать «вау-эффект», при этом формулироваться очень просто, т.е. кандидат сразу понимает, что нужно сделать.
В первой части статьи мы подробно разберемся с основами метода двух указателей и решим несколько базовых, но часто встречающихся задач. Во второй части рассмотрим более сложные, хотя и реже встречающиеся задачи.
Третья причина заключается в том, что многие интервьюеры относят эти задачи к очень простым (хотя, если вы сталкиваетесь с задачей впервые, то простейшей ее назвать нельзя), и если вы не смогли написать решение, то, скорее всего, последует однозначный отказ. А в купе с тем, что описание этого сложно найти в книгах, ситуация только усугубляется.
Четвертая причина – часто метод двух указателей дает самые оптимальные решения из возможных. Например, вместо O(n^2) по времени всего лишь O(n). Или же оценку O(n) по памяти оптимизирует до идеальной O(1) ! А интервьюеры любят самые лучшие (или точнее сказать бескомпромиссные) решения, даже если они чреваты ошибками или избыточны для многих практических задач.
И, наконец, пятая причина – некоторые задачки на этот метод могут быть достаточно интересными и вызывать «вау-эффект», при этом формулироваться очень просто, т.е. кандидат сразу понимает, что нужно сделать.
В первой части статьи мы подробно разберемся с основами метода двух указателей и решим несколько базовых, но часто встречающихся задач. Во второй части рассмотрим более сложные, хотя и реже встречающиеся задачи.
1. Начнем с классической задачи «Слияние двух отсортированных массивов или списков»
С методом проще всего познакомиться на примере решения классической задачи по слиянию двух отсортированных массивов, которую мы разберем даже излишне подробно.
Даны два отсортированных массива, необходимо получить третий отсортированный массив.
Встретив такую задачу в работе, мы бы просто объединили два массива c помощью метода «concat» и затем вызвали стандартный метод «sort». При этом алгоритмическая сложность была бы всё еще приемлема и составляла O(n log n), чего на практике обычно вполне достаточно. Но интервьюеры хотят от нас оценку O(n), а ее в общем случае не достичь обычной сортировкой.
Идея подхода:
будем последовательно заполнять результирующий массив минимальными значениями из двух исходных массивов. А раз массивы отсортированы по возрастанию, то минимальное значение находится в самом начале массива, и нам каждый раз нужно сравнивать только два этих первых значения для выявления наименьшего из них, а не искать минимум среди всех элементов обоих массивов. Именно в этом заключается суть ускорения!
Подзадача заполнения массива из n элементов новыми значениями уже дает сложность O(n). Однако подзадача поиска каждого очередного элемента, который нужно добавить в результирующий массив, занимает всего O(1), ведь мы сравниваем всего два значения, а не бежим дальше по массиву. Тогда общая сложность равна произведению этих задач O(n) * O(1), т.е. O(n).
Проиллюстрируем идею графически:
1) Начальное состояние
Проиллюстрируем идею графически:
1) Начальное состояние
2) Начинаем формировать результат
3) Продолжаем формировать результат
4) Почти финальное состояние
Для наглядности реализуем алгоритм на JS, поскольку у массивов в JS есть удобный метод «shift», который удаляет из массива первый элемент и возвращает его. И метод «push», который добавляет элемент в конец массива. Это всё, что нам нужно. Тогда комбинация result.push(arr.shift()) переместит элемент из начала исходного массива в конец результирующего массива. Тогда код мог бы выглядеть так:
function merge_sorted(arr1, arr2) {
let result = []
while (arr1.length > 0 || arr2.length > 0) {
if (arr1.length == 0)
result.push(arr2.shift())
else if (arr2.length == 0)
result.push(arr1.shift())
else if (arr1[0] <= arr2[0])
result.push(arr1.shift())
else
result.push(arr2.shift())
}
return result
}
Остановимся на коде подробнее.
На любом шаге, пока мы не заполнили весь результирующий массив у нас есть четыре возможных состояния:
На любом шаге, пока мы не заполнили весь результирующий массив у нас есть четыре возможных состояния:
- Исходные массивы пусты и, соответственно, результирующий массив полон - значит завершаем работу.
- Первый массив уже пуст, а второй нет. Тогда перемещаем в результат элемент из второго массива.
- И наоборот, второй массив уже пуст, а первый нет. Тогда перемещаем в результат элемент из первого массива.
- И, наконец, если в обоих исходных массивах есть элементы, то сравниваем первые два элемента разных массивов и перемещаем в результат меньший из них!
Идея метода «двух указателей» должна быть хорошо ясна. Но почему метод называется «два указателя», ведь у нас в коде никаких указателей нет?
Вместо использования метода «shift», который удаляет и возвращает элементы с начала массива, и который не во всех стандартных библиотеках может быть эффективно реализованным за O(1), будем использовать просто индексы и сдвигать их вперед, вместо удаления элемента из исходного массива.
Вместо использования метода «shift», который удаляет и возвращает элементы с начала массива, и который не во всех стандартных библиотеках может быть эффективно реализованным за O(1), будем использовать просто индексы и сдвигать их вперед, вместо удаления элемента из исходного массива.
Тогда два индекса будут являться теми самыми «двумя указателями» из названия метода, а код будет выглядеть следующим образом:
function merge_sorted(arr1, arr2) {
let result = []
let p1 = 0
let p2 = 0
while (p1 < arr1.length || p2 < arr2.length) {
if (p1 == arr1.length) {
result.push(arr2[p2])
p2++
} else if (p2 == arr2.length) {
result.push(arr1[p1])
p1++
} else if (arr1[p1] <= arr2[p2]) {
result.push(arr1[p1])
p1++
} else {
result.push(arr2[p2])
p2++
}
}
return result
}
Можно сделать код немного лаконичнее, объединив условия блоков с одинаковыми действиями и переместив инкременты внутрь индексирования:
function merge_sorted(arr1, arr2) {
let result = []
let i1 = 0
let i2 = 0
while (i1 < arr1.length || i2 < arr2.length)
if (i1 == arr1.length)
result.push(arr2[i2++])
else if (i2 == arr2.length || arr1[i1] <= arr2[i2])
result.push(arr1[i1++])
else
result.push(arr2[i2++])
return result
}
По сути, мы реализовали кусочек алгоритма «Сортировка слиянием». Правда, в классических книгах по алгоритмам за авторством Томаса Кормена или Стивена Скиены акцент делается не на слиянии, а на разбиении массива на log(n) частей (т.е. на совершенно другом методе «разделяй и властвуй»), поэтому описание метода сложно отыскать в классических книгах, а само название «метод двух указателей» вообще не используется. И уж тем более не разбираются дополнительные задачи на этот метод.
Метод «двух указателей» отлично работает не только для массивов, но и для отсортированных списков. Например, эту популярную на интервью задачку «Merge two sorted lists», в которой два отсортированных списка нужно слить в один, можно было бы решить на Python так:
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge(l1, l2):
pre_head = ListNode()
curr = pre_head
while l1 or l2:
if not l1:
curr.next = l2
l2 = l2.next
elif not l2:
curr.next = l1
l1 = l1.next
elif l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
return pre_head.next
Логика здесь такая же, как и в случае массивов, только манипуляции с индексами заменяются на манипуляции с указателями, более сложные по своей природе, а именно:
- Вместо копирования значения в ячейку целевого массива записываем ссылку в curr.next.
- А вместо увеличения индексов i1++ или i2++ перемещаем вперед указатели l1 = l1.next и l2 = l2.next
- Чтобы где-то сразу сохранить ссылку на голову списка и не потерять ее, мы вводим искусственный элемент pre_head.
- Важно отметить, что кроме O(n) по времени алгоритм работает так же за O(1) по памяти! Ведь дополнительно выделяемая память под два указателя и один вспомогательный указатель для хранения вершины не зависит от длины списка. Внутри цикла мы просто манипулируем указателями без дополнительного копирования узлов.
На практике в рабочих задачах редко приходится манипулировать даже одним индексом или указателей, ведь обычно мы используем выразительные методы filter, map, reduce/fold и прочие. А тут целых два индекса и обработка случаев достижения конца одного из массивов - одним словом, запутаться очень легко.
Поэтому, если на интервью вам попалась задачка слить два массива или списка, то можно дать следующие рекомендации:
- Не сокращайте кол-во условий и инкрементов в процессе (пока вы не написали и не отладили весь алгоритм), иначе можно легко запутаться.
- Не забывайте проверять условия достижения конца массива или списка одним из указателей или индексов.
- Пишите самую объемную, но наглядную версию. Потом, при необходимости, удалите избыточность.
- Верно обосновывайте алгоритмическую сложность. Каждый индекс пробегает последовательно значения от 0 до length ровно один раз - значит сложность по времени O(n). В случае со списками, поскольку мы не создаем новые узлы, расход памяти будет O(1).
Обратим внимание, что в этой задаче указатели росли в одном и том же направлении (слева направо) и строго на единичку. Далее мы рассмотрим другие варианты роста указателей.
2. Навстречу друг другу
Согласно рейтингу популярности leetcode задача «Two Sum» является самой популярной задачей на алгоритмических интервью в мире и формулируется так:
Дан массив целых чисел и число target. Необходимо вернуть индексы двух значений, которые в сумме дают target. При этом каждый элемент может использоваться только один раз. А сама задача так же имеет ровно одно решение (т.е. возвращаем первые попавшиеся индексы, удовлетворяющие условию)
Конечно, мы можем просто перебрать все пары значений в массиве с помощью двух вложенных циклов и проверить их сумму, но тогда сложность будет O(n^2). Этот вариант, разумеется, не годится, если мы не хотим получить отказ или понижение грейда по результатам интервью.
Другой вариант заключается в том, чтобы вычитать каждый элемент из target и искать эту разницу в оставшейся правой части массива (а не всем массиве, чтобы не учитывать два раза простую перестановку слагаемых) с помощью линейного поиска. Но по сути это решение эквивалентно первому, ведь для каждого элемента мы выполняем поиск второго слагаемого за O(n), что дает общую сложность O(n^2).
Другой вариант заключается в том, чтобы вычитать каждый элемент из target и искать эту разницу в оставшейся правой части массива (а не всем массиве, чтобы не учитывать два раза простую перестановку слагаемых) с помощью линейного поиска. Но по сути это решение эквивалентно первому, ведь для каждого элемента мы выполняем поиск второго слагаемого за O(n), что дает общую сложность O(n^2).
Классическое решение подразумевает использование хэш-таблицы, в которую мы заносим элементы исходного массива. Мы так же ищем второе слагаемое для каждого элемента массива, но делаем это не линейным поиском за O(n) в массиве, а поиском в хэштаблице за О(1) и получаем общую сложность O(n). Сама хеш-таблица подготавливается так же за O(n), что не влияет на общую сложность, которая остается O(n).
Этот тот редкий случай, когда код читается даже проще объяснения этого кода:
def two_sum(arr, target):
hash = {}
for (i, val) in enumerate(arr):
hash[val] = i
for (i, val) in enumerate(arr):
second_add = target - val
# Ищем второе слагаемое в хэштаблице и проверяем,
# что не складываем элемент с самим собой.
if second_add in hash and hash[second_add] != i:
return [i, hash[second_add]
При этом задача может иметь множество вариаций, например:
- Нужно вернуть все возможные пары значений, которые дают в сумме target, а не только первые попавшиеся
- Нужно вернуть сумму, максимально близкую к target, но не равную ему! и т.п. и т.д.
Но что если интервьюер хочет получить от нас оценку по памяти лучшую, чем O(n) ? Или модифицирует задачу так, что нужно вернуть значения, которые максимально близки к сумме, но не равны ей?
Тогда хеш-таблица не подойдет, ведь она занимает O(n) памяти, да и искать в ней мы можем быстро только конкретные значения, а не по условию больше или меньше.
Тогда на сцену выходит метод двух указателей! Давайте решим ту же самую задачу, только представим, что исходный массив уже заботливо отсортирован. Пусть первый индекс указывает на начало массива, а второй на конец. Тогда мы можем сложить два этих значения, сравнить сумму с target и рассмотреть три возможных варианта:
Тогда хеш-таблица не подойдет, ведь она занимает O(n) памяти, да и искать в ней мы можем быстро только конкретные значения, а не по условию больше или меньше.
Тогда на сцену выходит метод двух указателей! Давайте решим ту же самую задачу, только представим, что исходный массив уже заботливо отсортирован. Пусть первый индекс указывает на начало массива, а второй на конец. Тогда мы можем сложить два этих значения, сравнить сумму с target и рассмотреть три возможных варианта:
1) Сумма больше target.
Может показаться неочевидным, но в этом случае мы можем только уменьшить правый индекс на единицу, т.е. сдвинуть его влево. Почему? Потому что сумма уже больше target, а это значит что нам нужно уменьшить одно из слагаемых
Так как массив отсортирован, то меньшие значения находятся левее, значит двигаем правый индекс влево ⬅. Движение правого или левого индекса вправо только увеличит сумму. Но можно заметить, что для уменьшения суммы мы так же можем двинуть левый индекс влево. Так делать не нужно, потому что мы повторно рассмотрим уже обработанный элемент. Да и если индексы будут двигаться в произвольные стороны это усложнит алгоритм.
2) Сумма меньше target.
Чтобы ее увеличить, мы двигаем левый индекс вправо ➡
3) Сумма равна target.
В этом случае мы просто возвращаем индексы.
Итого, на каждом шаге мы либо двигаем левый индекс вправо, либо правый влево. То есть индексы двигаются навстречу друг другу.
Решение на Python может выглядеть так:
def two_sum(arr, target):
left = 0
right = len(arr) - 1
while left < right:
if arr[left] + arr[right] == target:
return [left, right]
if arr[left] + arr[right] < target:
left += 1
else:
right -= 1
В общем-то мы можем сами выполнять сортировку и не требовать упорядоченности входного массива. Но поскольку оригинальная задача с leetcode требует возвращать индексы элементов, которые после сортировки меняются, то, чтобы отправить решение на leetcode, нам потребуется модификация, которая сортирует исходный массив , но при этом сохраняет оригинальные индексы:
def two_sum_with_sort(arr, target):
# Преобразуем массив в набор пар (значение, оригинальный индекс).
arr = [(val, i) for i, val in enumerate(arr)]
# Сортируем по значению.
arr.sort(key = lambda x: x[0])
# Теперь каждый элемент отсортированного массива хранит пары, первое значение которой можно получить так arr[i][0],
# а оригинальный индекс так arr[i][1].
left = 0
right = len(arr) - 1
while left < right:
if arr[left][0] + arr[right][0] == target:
return [arr[left][1], arr[right][1]]
if arr[left][0] + arr[right][0] < target:
left += 1
else:
right -= 1
Можно отправить решение на leetcode и убедиться, что оно работает. Хотя, применение для этой задачи метода двух указателей хоть и может иметь смысл, но все же выглядит несколько искусственно.
Поэтому решим еще одну задачу, для которо метод двух указателей подходит идеально – «Two Sum Less Than K»
Дан массив целых чисел, нужно вернуть сумму любых двух значений, максимально близкую к указанной, но меньше ее. Если такой суммы не существует, то вернуть -1.
Два поясняющих примера:
Пример 1.
Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Объяснение: Мы можем использовать 34 и 24, которые в сумме дают 58, что меньше 60.
Пример 2.
Input: nums = [10,20,30], k = 15
Output: -1
Объяснение: В массиве нет пары чисел, которые дали бы сумму, меньшую 15.
Идея будет абсолютна идентична предыдущему решению, только с небольшими отличиями:
1) Заводим переменную для хранения максимальной суммы, изначально равную -1.
2) Если текущая сумма больше целевой, то как обычно сдвигаем правый указатель влево ⬅
2) Если текущая сумма больше целевой, то как обычно сдвигаем правый указатель влево ⬅
3) Если текущая сумма меньше целевой, то обновляем максимальную сумму, а далее как обычно сдвигаем левый указатель вправо ➡.
4) Если же сумма равна целевой, то так же сдвигаем правый указатель влево ⬅, ведь нас интересуют суммы только меньшие целевой.
Если продолжить рассматривать пример входных данных из иллюстрации, то алгоритм завершится на таком состоянии:
После чего максимальная сумма будет равна 9, а индекс left сравняется с right и цикл while left < right завершится по условию.
Код на Python может выглядеть так:
Код на Python может выглядеть так:
def two_sum_less(arr, target):
arr.sort()
nearest_sum = -1
left = 0
right = len(arr) - 1
while left < right:
if arr[left] + arr[right] < target:
nearest_sum = max(nearest_sum, arr[left] + arr[right])
left += 1
else:
right -= 1
return nearest_sum
Какова будет его вычислительная сложность? Цикл while будет работать за O(n) по времени и за O(1) по памяти. Поэтому итоговая сложность будет равна сложности сортировки — по времени это O(n log n), а по памяти в зависимости от реализации стандартной сортировки: от O(log n) до O(n).
3. Расходимся в противоположные стороны
Мы рассмотрели задачи, где указатели движутся в одном направлении, либо навстречу друг другу. Было бы логично рассмотреть задачу, где указатели движутся в противоположные стороны. И такая задачка тоже имеется – «Squares of a Sorted Array».
Дан массив целых чисел, отсортированный по возрастанию. Необходимо вернуть массив квадратов этих чисел, отсортированный так же по возрастанию.
На первый взгляд кажется, что достаточно возвести каждый элемент массива в квадрат и вернуть результат. Но если у нас в массиве есть отрицательные значения, то мы получим следующую картину:
Получим два отсортированных подмассива:
- Первый подмассив из бывших отрицательных чисел убывает
- Второй подмассив из бывших положительных чисел растет
То есть, после возведения в квадрат массив перестает быть отсортированным. К счастью, задачу можно легко свести к нашей первой задаче слияния двух отсортированных массивов, только индексы будут расти не в одном направлении, а в разных.
Напишем решение на Python:
def sorted_squares(arr):
# Устанавливаем индексы left и right на начало подмассивов.
#
# left будет указывать на последний отрицательный элемент, либо будет равен -1,
# если все элементы в массиве положительные.
left = -1
for i, val in enumerate(arr):
if val > 0:
left = i - 1
break
else:
left = len(arr) - 1
# right будет идти сразу за left, но если в массиве нет положительных элементов,
# то right будет равен длине массива.
right = left + 1
# Возводим в квадрат.
arr = [n * n for n in arr]
# Сливаем два отсортированных массива в один, как делали раньше.
result = []
while left >= 0 or right < len(arr):
if left < 0:
result.append(arr[right])
right += 1
elif right >= len(arr):
result.append(arr[left])
left -= 1
elif arr[left] <= arr[right]:
result.append(arr[left])
left -= 1
else: # arr[left] > arr[right]
result.append(arr[right])
right += 1
return result
Код получился довольно объемным, а значит в нем легко ошибиться. Нам дополнительно пришлось:
- Отыскивать left в середине массива.
- Создавать массив с квадратами.
- Бежать по массиву в разные стороны и проверять выход за границы.
Как правило, простые задачи на интервью не подразумевают многословных решений, поэтому можно предложить два существенных улучшения:
- А что если бежать по исходному массиву, а не по массиву квадратов? В квадрат возводить при помещении в результирующий массив, а не сразу. Это упростит логику.
- Зачем нам искать начало подмассивов? Можно ведь установить left = 0 на начало массива, а right = len - 1 на конец массива. Тогда мы будем бежать навстречу друг другу и двигаться по массивам от большего значения к меньшему. Просто при сравнении больший элемент помещать в результирующий массив начиная с конца
Реализация на Python может выглядеть так:
def sorted_squares(arr):
# Заранее создаем пустой массив нужной длины,
# ведь мы будем наполнять его с конца.
result = [None] * len(arr)
left =
right = len(arr) - 1
i = right
while i >= 0:
if abs(arr[left]) >= abs(arr[right]):
result[i] = arr[left] * arr[left]
left += 1
else:
result[i] = arr[right] * arr[right]
right -= 1
i -= 1
return result
Код стал концептуально проще по сравнению с предыдущей версией и чреват меньшим количеством потенциальных ошибок.
На этом мы заканчиваем знакомство с методом двух указателей на примере задач уровня сложности easy по версии leecode. Надеюсь, если вы не были знакомы с методом двух указателей, то у вас получилось погрузиться в эту тему. И если одна из таких популярных задач попадется вам на реальном интервью, то вы с легкостью с ней справитесь!
На этом мы заканчиваем знакомство с методом двух указателей на примере задач уровня сложности easy по версии leecode. Надеюсь, если вы не были знакомы с методом двух указателей, то у вас получилось погрузиться в эту тему. И если одна из таких популярных задач попадется вам на реальном интервью, то вы с легкостью с ней справитесь!
Кстати, мы регулярно запускаем курс по подготовке к алгоритмическим собеседованиям
На курсе мы:
- прорабатываем всю теорию, которая нужна для успешного прохождения алгосекции
- учимся понимать суть и идею каждой задачи без заучивания схемы решения
- решаем все задачи, которые могут встретиться на алгоритмическом собеседовании: простые и уровня hard+
- разбираем задачи, которые встречались на реальных собеседованиях в OZON, Яндекс, ВК, Тинькофф, СБЕР и Авито + рассказываем особенности прохождения собеседований в эти компании и типичные темы, которые они спрашивают
- проводим mock-собеседования и code-review, чтобы избавиться от боязни интервьюера и научиться читать код своих коллег на работе
Подробнее о курсе