Всем привет! На связи снова Петр Коробейников, техлид сервисов DBaaS for Redis и RabbitMQ (релиз скоро) в #CloudMTS. В этой статье хочу поделиться с вами некоторым опытом подготовки к прохождению алгоритмических интервью. Конечно, статья не про хардкорные алгоритмы. Это, скорее, эскиз к роадмапу по подготовке. Тем не менее, я надеюсь, он будет полезен новичкам (и даже некоторым «старичкам»).

Готовьтесь

Это первый и самый важный совет. Если вы думаете, что, ворочая базами в десятки терабайт, вывозя 50-100k RPS к фронту, обрабатывая десятки миллионов сообщений в Kafka, вы сможете перенести свой опыт на решение алгоритмических задач, то могу вас немного расстроить.

Двоичное дерево без подготовки вы сможете покрутить в лучшем случае только на неприличном месте. Это чем-то похоже на экзамен по математике или физике: вы не сможете вывести формулу, если не знакомы с теорией и не решали задачи заранее. И вас будет ждать обидный провал.

Как же так? Столько лет (а то и десятков лет) опыта в резюме, столько продакшн-реди (миллионов) строк кода, столько (сотен) сбоев оперативно починено — и тут на тебе. Это связано с тем, что систему, с которой вы работаете, вы знаете досконально, вы знаете, какую гайку и где нужно подкрутить, чтобы всё работало как положено.

С алгоритмами этот опыт не поможет. Вы будете работать не с большой системой, а со швейцарскими часами ручной сборки, где всё должно быть выверено хирургически точно.

Пишите тесты

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

Решая задачу на leetcode, возьмите примеры в качестве тестовых данных. Попробуйте добавить свои, если понимаете, что не все варианты покрываются примерами.

Если прорабатываете или предлагаете несколько решений, не забывайте о копировании исходных тестовых данных. Часто решения алгоритмических задач предполагают изменение поданных на вход данных. Например, если вы определили два связных списка для слияния, после прогона одного алгоритма исходные данные могут измениться. Вот сниппет, как скопировать односвязный список:

func CopyList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    node := &ListNode{Val: head.Val}
    node.Next = CopyList(head.Next)

    return node
}

А вот так, например, можно копировать двоичное дерево:

func TreeClone(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }

    clone := &TreeNode{Val: root.Val}
    clone.Left = TreeClone(root.Left)
    clone.Right = TreeClone(root.Right)

    return clone
}

Если погружаетесь еще глубже, напишите бенчмарки на свои решения. Вы будете удивлены повышению скорости некоторых решений, переведя их с работы математических операторов на двоичные.

Отдельная переменная вместо вложенного вызова

В процессе решения нагляднее использовать отдельную переменную, чем вложенные вызовы, особенно рекурсивных функций:

depthLeft, depthRight := MaxDepth(root.Left), MaxDepth(root.Right)  
  
return 1 + Max(depthLeft, depthRight)

При таком подходе **не** требуется думать про количество открытых и закрытых скобок, особенно если возможности редактора будут ограничены (например, «Яндекс.Контест»).

В финальном решении вам никто не мешает избавиться от лишних переменных.

Имена переменных

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

На эту тему очень много рекомендаций, большинство из которых относится к продакшн-коду, который описывает бизнес-процессы и в котором редко используются алгоритмические подходы.

Подумайте над следующими принципами именования переменных в своем решении:

• k, v — ключ/значение в циклах foreach;
• i, j, k — счетчики циклов;
• x, y — искомое значение (по аналогии с примером по математике);
• out — искомое/выходное значение функции;
• rev — инвертированное значение, например в задачах с палиндромом;
• orig — копия оригинального значения;
• left, right — левый и правый узлы дерева;
• slow, fast — медленный и быстрый указатели;
• head, last, prev, next, curr, node, prehead, sentinel — имена указателей для работы со списками;
• top, front, rear — имена указателей для работы со стеками и очередями;
• max, min, low, high, mid, pivot — для хранения значений.

Почему имеет смысл использовать однобуквенные переменные? Если их область видимости — тело короткой функции, цикла или условия, однобуквенная переменная сделает код компактным и наглядным.

Чем плохи длинные и полные имена? Повышается вероятность внести ошибку в длинное имя, особенно когда в нём встречаются сочетания из нескольких согласных букв (например, width, height, depth против w, h, d) или слов (maximumRectangleWidth). Редактор кода не всегда сможет подсветить вам ошибку.

Что если в языке имя len для хранения длин списков, массивов и строк зарезервировано? Короткое имя l можно легко спутать с цифрой 1. Попробуйте заменить len на size, если это возможно.

Может показаться, что в следующем примере я противоречу сам себе. Давайте представим задачу или класс задач, в котором необходимо работать с двухмерным массивом. Как раз в подобных задачах при переборе O(n^2) имеет смысл дать счетчикам циклов осмысленные, но все же короткие и понятные имена:

for person := 0; person < len(accounts); person++ {
    sum := 0
    for account := 0; account < len(accounts[person]); account++ {
        sum += accounts[person][account]
    }

    if sum > max {
        max = sum
    }
}

Обращение по индексам, имеющим смысловую нагрузку, для решения подобных задач сильно облегчит понимание вашего кода, чем безликие i и j, использованные в качестве индексов.

Вот еще один пример, иллюстрирующий наглядность правильно выбранных имен счетчиков циклов:

for row := 0; row < n; row += 1 {  
    for col := 0; col < n; col += 1 {
        board[row][col]
    }
}

При решении задачи уделите немного времени выбору имен переменных. Удачно выбранное имя сделает код более понятным, процесс решения задачи более простым, а поиск допущенной ошибки быстрым.

Запутанное решение

Если решение выглядит запутанным — это, скорее всего, не самое эффективное и не самое правильное решение. Например, проверка, является ли число палиндромом:

if x < 0 || (x%10 == 0 && x != 0) {
    return false
}

rev := 0
for x > rev {
    rev = rev*10 + x%10
    x /= 10
}

return x == rev || x == rev/10

В данном решении используется большое количество проверок и условий, расставлять которые во время интервью всегда сложно. И это, на секунду, официальное решение задачи на leetcode.

Более элегантное решение:

rev, d, orig := 0, 0, x  

for x > 0 {  
    x, d = x/10, x%10
    rev = rev*10 + d
}  

return orig == rev

При подготовке старайтесь искать наиболее элегантное решение: его проще понять, запомнить и повторить.

Оператор множественного присваивания

Если в языке, на котором вы решаете задачи, есть оператор множественного/деструктивного присваивания, попробуйте воспользоваться им, если количество переменных не превышает, скажем, трех:

head.Next, prev, head = prev, head, head.Next

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

Существуют случаи, когда, недавно узнав о таких возможностях оператора =, его пытаются использовать повсеместно. На примере алгоритма Kadane'а рассмотрим пример некорректного использования:

// Некорректное использование: переменная curr должна использоваться после присвоения
for i := 1; i < length; i++ {
    curr, max = Max(nums[i], curr+nums[i]), Max(max, curr)
}

Правильное использование:

for i := 1; i < length; i++ {
    curr = Max(nums[i], curr+nums[i])
    max = Max(max, curr)
}

Оператор инкремента и декремента

Чтобы не ошибиться с приоритетом операторов, вместо сокращенных записей i++ или i-- используйте явную форму i += 1 или i -= 1.

Особенно это важно, если просыпается желание пожонглировать префиксной (++i) и суффиксной (i++) формами.

В счетчиках простых циклов можно использовать сокращенную форму, так как в данном случае она не влияет на порядок вычислений.

Напомню, что в Go нет префиксной и суффиксной форм операторов ++ и --.

Условие цикла как замена проверке

Используйте этот прием осторожно и только для оптимизации уже существующего решения. На практике безопаснее сразу проверить крайние случаи и отсечь их, сконцентрировав внимание на общем решении.

В некоторых ситуациях можно отказаться от проверки данных на входе.

if head == nil {  
    return head  
}

Не всегда, но часто подобную проверку можно выполнить в условии цикла:

for head != nil {  
    head.Next, prev, head = prev, head, head.Next  
}

То же самое можно применить и к проверке длины массива:

if len(nums) == 1 {
    return nums
}

В данной ситуации тело цикла выполняться не будет, так как проверка уже заложена в условие цикла:

for i := 1; i < len(nums); i++ {  
    nums[i] = nums[i-1] + nums[i]  
}

В примере выше приведено решение для подсчета скользящей суммы с модификацией самого массива.

Внимательно читайте условие задачи

Обязательно ознакомьтесь с ограничениями, которые описаны в условии задачи.

Например, если в задаче указано, что размерность матрицы не может быть меньше 1x1, то проверка длины массива на 0 не требуется.

Не забывайте о переполнении. В некоторых задачах сумма или произведение могут выходить за пределы диапазона допустимых значений.

Представим пример, в котором есть риск выхода за границы диапазона:

// сумма left + right может выйти за границы int
pivot := (left + right) / 2

// или
pivot := (left + right) >> 1

Вот как можно постараться предотвратить переполнение при поиске среднего элемента массива:

pivot := left + (right-left)/2

Работа с двоичным представлением чисел

Постарайтесь, если не запомнить в принципе всё, то хотя бы какие-то шаблоны для работы с двоичным представлением.

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

Например, очень часто программисты используют неэффективную операцию получения остатка от деления (обычно это оператор %), чтобы проверить, является ли число четным или нет:

func IsEven(n int) bool {
    return 0 == n % 2
}

Гораздо более эффективным решением будет один из следующих вариантов:

func IsEvenXor(n int) bool {
    return n^1 == n+1
}

func IsEvenAnd(n int) bool {
    return !(n&1 == 1)
}

func IsEvenOr(n int) bool {
    return n|1 > n
}

Ознакомьтесь с шаблонами решений

Многие задачи имеют общие подходы. Подготовьте себе ряд шаблонных решений и попробуйте подобрать подходящий шаблон для задачи, которую решаете в данный момент.

Вот некоторые из известных подходов:

1. Быстрый и медленный указатели.
2. Три указателя.
3. Обход массива можно начинать не только с начала, но и с конца.
4. Sentinel/Guard — узлы в списках и деревьях.
5. Использование двоичного поиска.

В конце статьи я привожу несколько ссылок, обратите на них внимание.

Вспомните, как работает O(n)

Один из самых важных навыков — постараться определить «скорость» алгоритма. Для этого используется асимптотика O(n) [о большое от эн].

Какие навскидку бывают сложности O(n)?

• O(1)
• O(n)
• O(log n)
• O(n log n)
• O(n ^ 2)
• O(2 ^ n)
• O(n!)

Разберитесь, в каком случае какую сложность будет представлять собой тот или иной алгоритм. Попробуйте выяснить, за какое O(n) выполняются те или иные операции в стандартной библиотеке используемого вами языка.

Вспомните, почему O(k * n) = O(n), где k — константа.

Чему равно основание логарифма в записи O(n log n)?

Составьте план изучения алгоритмов и структур данных

В первую очередь я бы рекомендовал изучить сами структуры данных. Может показаться смешным, но начать стоит с простейшей — массива, вспомнить о стеках, очередях и деках. Потом перейти к односвязным и двусвязным спискам, перейти к двоичной куче и двоичному дереву. Будет не лишним, если вы самостоятельно попробуете реализовать хэш-таблицу с открытой и закрытой адресацией.

После того как вы будете ориентироваться в самих структурах, их реализациях, хорошо понимая, как они ложатся в память, переходите к операциям над ними.

Попробуйте удалить все дублирующиеся значения в массиве, удалить элемент из связного списка, реализовать свою собственную очередь и стек с поддержкой максимума или минимума. Обойдите дерево по уровням и в разных порядках: inorder, preorder, postorder. Чтобы не перечислять все задачи, вы можете самостоятельно выбрать доступные задачи из списка проблем на leetcode или других ресурсах, например на hackerrank.

Чаще всего у многих задач есть несколько решений, скажем, рекурсивное и итеративное. Попробуйте реализовать операции над структурой несколькими способами.

Что почитать?

Существует три книги, которые дают возможность погрузиться в тему. В списке они представлены в порядке от простого к сложному:

• «Грокаем алгоритмы». Бхаргава;
• «Алгоритмы. Руководство по разработке». Скиена;
• «Алгоритмы: построение и анализ». Кормен и др.

Если все плохо: не знаете, как выглядит связный список, что такое бинарное дерево и как работает O(n) — начинать следует с книги «Грокаем алгоритмы». Материал объясняется на пальцах. Лучший выбор для новичка.

Скиену можно читать более опытным специалистам.

Кормен прекрасен, но не поможет вам подготовиться к предстоящему собеседованию. Это фундаментальная толстая книжка с математикой. Ее надо прорабатывать в принципе, а не перед интервью.

Если вы подумали, что я забыл про 3-томник Кнута (4, 4.5 или уже 5) — нет. Даже не думайте брать эту книгу для подготовки. Читать её без математического бэкграунда сложно, применять на практике еще сложнее. Эта книга для экспертов.

Вывод

Подготовка к алгоритмической части собеседований требует времени и усилий над собой. Однако она приносит и очень много пользы. Если вы плотно занимаетесь подготовкой, так или иначе вы:

• лучше погрузитесь в стандартную библиотеку вашего языка и, возможно, глубже узнаете некоторые нюансы, которые до этого не применяли на практике;
• потренируетесь писать тесты и видеть различные крайние случаи, о которых нельзя забывать;
• поработаете с бенчмарками и узнаете тонкости их применения;
• будете видеть более оптимальные решения ваших текущих задач;
• сможете лучше выражать свои намерения в коде;
• само собой, изучите или повторите основные алгоритмы.

Успехов в подготовке! ????

P. S.
Конечно, эта статья охватывает далеко не все аспекты подготовки к алгоритмическому интервью. Предлагаю в комментариях поделиться вашими впечатлениями о книгах, курсах и других источниках информации. Буду рад дополнить ее самыми интересными предложениями. Спасибо за внимание!