Как я изучал структуры данных и алгоритмы для собеседования в FAANG

Продолжая тему устройства в FAANG, которую уже мы поднимали в нашем блоге, и специально к старту нового потока нашего курса по алгоритмам сегодня делюсь описанием пути Эско Обонга, старшего инженера-программиста Uber.

Эта история началась в 2015 году, когда стартап, к которому я присоединился как «сотрудник-основатель», закрылся через шесть месяцев после первого раунда инвестиций, и я искал новую работу. Первое моё собеседование было с  Codecademy, где на этапе телефонного разговора меня заверили: «Не волнуйтесь, мы не задаём сумасшедших вопросов об алгоритмах или что-то в этом роде». И я им поверил…

---

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

while (true) {…

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

Фиаско в Codecademy открыло мне глаза на пробелы в моих знаниях. Два с половиной месяца спустя я прошёл телефонный скрининг в Google, Uber, Shutterstock и Rent the Runway. Были собеседования на месте в Shutterstock, Rent the Runway и Uber – и я прошёл их все. Google перенёс моё собеседование на две недели вперёд в последнюю минуту. К тому времени у меня уже было три предложения, и я был в восторге от Uber, поэтому я нажал на спуск – присоединился к Uber.

Я прошёл с нуля до профессионального уровня всего за несколько месяцев, но не делал ничего особенного, только последовательно учился. Вот почему я твёрдо верю, что любой инженер может справиться с этими вопросами об алгоритмах и структурах данных и попасть в F.A.A.N.G. или на аналогичные должности с высокой зарплатой. Сначала казалось, что мне не хватает квалификации, потому что для собеседования приходилось усердно учиться. В 2019 году, после того как я управлял собственной консалтинговой фирмой и стартапом в течение почти двух лет, я решил вернуться к постоянной работе и оказался в том же положении, что и в 2015 году.

На этот раз у меня было больше друзей в Uber и других ведущих компаниях, таких как Google и Facebook, которые помогли мне понять суть дела. Так же усердно пришлось учиться им всем. Даже тем, кто не бросил колледж, как и я.

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

Я отказался от представления о мифическом инженере, который может по щелчку пальцев пройти техническое собеседование, и начал понимать реальность ситуации: технические собеседования похожи на SAT [прим. перев. — «Scholastic Aptitude Test» и «Scholastic Assessment Test», дословно «Академический оценочный тест») — стандартизованный тест для приема в высшие учебные заведения в США] в школе. Не важно, что вы потратили четыре года, чтобы изучить всё, чему учатся в старшей школе. Если вы хотите сдать экзамен, вам всё равно нужно подготовиться. Как и в случае с SAT, все ваши прошлые работы и оценки не влияют на результат. Ваш успех полностью зависит от того, насколько хорошо вы сдали тест.

Как только я понял истину, что учиться нужно всем, то обрёл достаточно мотивации, чтобы трудиться усердно. Я понял, что труд обучения – это именно то, чем заняты мои конкуренты. Это послужило толчком, чтобы сформировать процесс обучения, который помог мне пройти все технические тесты и собеседования в 2019 году. Я бросил колледж и прошёл технические тесты Stripe, Coinbase и Triplebyte. Прошёл скрины и собеседования на местах в Google, Amazon, Uber (снова), Reddit, Squarespace и Braze. Я не ждал, что пройду всё идеально, но считаю, мне помогло то, что я сосредоточился на основных принципах.

Google отправляет вам сувениры, когда вы проходите собеседование.

Переход не был плавным. Когда я только начал готовиться к собеседованию, мне потребовалось более 2 часов, чтобы почти решить задачу, которую теперь можно было бы назвать «leetcode easy», а в то время это казалось невозможным! Я искренне верил, что просто недостаточно умён от природы и мне придётся учиться ещё усерднее, чтобы достичь уровня, на котором смогу решить задачу с той же скоростью, что и инженер Google. Я понял одно: мне нужно практиковаться.

Чего я не понимал, так это того, что такого уровня сложности и разочарования вначале следует ожидать всем начинающим, включая инженеров Google.

Я всё тот же человек. Единственная разница между мной тогда и сейчас – практика, практика, практика. У людей часто возникает вопрос: «Как мне учиться?» Трудно понять, с чего начать, что делать дальше, добиваетесь ли вы прогресса, и ещё труднее оставаться на верном пути. Чтобы решить многие из этих вопросов, когда я учился, я создал доску Trello со всеми темами, которые хотел охватить. Доска помогла мне сосредоточиться на самых важных темах и управлять временем, чтобы прогресс был стабильным.

Я написал пост о доске Trello в LinkedIn, этот пост стал вирусным. Менеджер Trello связался со мной по поводу создания для него официального шаблона Trello, который теперь находится здесь: Interview Study Tracker.

Чтобы учиться, в трекере есть шаблон. Он требует определения списка тем и двух или более ресурсов, которые могут научить чему-то по теме. Затем нужно задать себе 2–3 практических задачи, чтобы укрепить понимание. Задачи могут быть из любого источника, главное – это сам контент. Я нашёл большую часть своего контента с помощью простого поиска в Google, темы были ключевыми словами.



Изучайте одно и то же с разных точек зрения, это поможет лучше понять тему. Например, о двоичных деревьях поиска я бы прочитал статью на geeksforgeeks.org, а также главы о них в Cracking the Coding Interview. Затем я задал бы себе 2–3 практических задачи, или достаточно задач, чтобы почувствовать себя комфортно, прежде чем двигаться дальше.

Мой экземпляр «Cracking The Coding Interview 6th Edition», подписанный Гэйл Лакман Макдауэлл

Список тем для изучения

Ниже привожу список почти всех структур данных и алгоритмов, с которыми вы можете столкнуться во время технического собеседования, а также очень краткое описание и некоторые ресурсы – с их помощью можно приступить к составлению плана обучения. Цель списка – дать вам отправную точку, чтобы вы разработали план, а не подробно объяснять, что представляет собой каждая тема. Часть вашего плана – найти ресурсы, чтобы узнать больше о каждой теме с разных точек зрения.

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

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

Базовые структуры данных

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

• Массив.
• Множество.
• Хэш-отображение (HashMap, хэшмэп).
• Связный список.
• Стек.
• Очередь.
• Дерево.
• Граф.

Ничего страшного, если этот список кажется вам длинным. Многие из этих структур данных тесно связаны и даже опираются друг на друга, поэтому вы сможете изучить их все быстрее, чем думаете. Хэшмэпы базируются на массивах. Стеки строятся на основе связанных списков или массивов. Очереди основаны на связанных списках. У деревьев есть понятия «узлов» и «ссылок» из связанного списка. Графы находятся в том же поле понятий. Они также имеют много общего с деревьями. Все деревья технически тоже являются графами, так что вы можете применить к ним те же методы, что и к графам.

Продвинутые структуры данных

После освоения базовых структур данных, знание этих, более продвинутых, даст вам больше шансов на успех. Некоторые из них очень часто всплывают на собеседовании, например, кучи или бинарное дерево поиска. Кэши LRU и префиксные деревья появляются реже, но становятся всё более распространёнными. Непересекающиеся множества и списки с пропусками всплывают редко, но не важно, спрашивают ли о них явно. Они могут оказаться мощными инструментами, которые помогут вам найти быстрые и эффективные решения.

• Куча (также известная как приоритетная очередь).
• LRU-кэш.
• Двоичные деревья (AVL, красно-чёрные).
• Непересекающиеся множества.
• Trie (префиксное дерево, нагруженное дерево).
• Skip List (список с пропусками).

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

Кучи, также известные как очереди приоритетов, – это тип дерева, которое ведёт себя как очередь. Бинарное дерево поиска (BST) – это дерево, которое ускоряет поиск узлов. AVL и красно-чёрные деревья – два популярных специфических типа сбалансированных BST. Кэш LRU – это кэш с эффективным использованием памяти, он создаётся объединением Hashmap [прм. перев. — хэшмэпы — специфический тип хэш-таблицы] со связным списком. Trie – это ещё один тип дерева, который ускоряет поиск по подстроке. Непересекающиеся множества – это особый тип множества, которые разделяют элементы на неперекрывающиеся подмножества, полезные для алгоритма поиска объединения. Skip List – это оптимизированный LinkedList, он сокращает время поиска определённых узлов.

Основные алгоритмы поиска и обхода

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

• Поиск в ширину.
• Поиск в глубину.
• Двоичный поиск.

Продвинутые алгоритмы поиска и обхода

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

• Quickselect [прим. перев. — алгоритм нахождения k наименьших элементов в неотсортированном массиве].
• Алгоритм Дейкстры.
• Алгоритм Беллмана – Форда.
• А-звезда (редко).

Алгоритмы сортировки

Сортировка – это распространённый инструмент, используемый для повышения производительности решения. Существует множество алгоритмов сортировки, но самые популярные на собеседовании перечислены ниже. Нужно знать, как реализовать всё это, никуда не подсматривая:

• Быстрая сортировка.
• Сортировка слиянием.
• Топологическая сортировка.
• Сортировка подсчётом.

Важные темы

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

• Рекурсия.
• Жадные алгоритмы.
• Динамическое программирование.
• Битовые манипуляции (AND, NOT, OR, XOR).

Распространённые шаблоны

Эти шаблоны можно использовать, чтобы разобраться со многими алгоритмами:

• Поиск с возвратом.
• Метод двух указателей.
• Метод скользящего окна.
• Принцип «разделяй и властвуй».
• Reservoir Sampling (резервуарная выборка).

Математические задачи

• Перестановки.
• Комбинаторика.
• Факториал.
• Степень множества (булеан).

Другие общие задачи

• Преобразование строки в целое число.
• Преобразование целого числа в строку.
• Сложение чисел, которые не помещаются в памяти.
• Сложение, вычитание, умножение и деление без операторов.

Практика

Самостоятельная практика

Обучение ничего не значит без практики. Каждый раз, когда вы изучаете новую тему из своего учебного плана, вы должны использовать знания из неё. Это поможет вам лучше запомнить тему, даст понимание глубже. Задайте самому себе несколько практических задач по каждой завершённой теме. На таких сайтах, как leetcode.com, можно найти практические вопросы, воспользовавшись тегами «trees» или «graphs».

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

Во время собеседования вы должны решить задачу за 15–45 минут в зависимости от сложности. Вначале вам, скорее всего, понадобится несколько часов, чтобы решить первую задачу. В первые несколько недель это время должно начать сокращаться. Через месяц или два месяца постоянной практики (а не просто времени) вы должны научиться решать приличное количество задач вовремя. Иногда ваша задача – реализовать единственную структуру данных, например LRU-кэш или Trie. В других случаях нужно выполнить только одну операции над структурой данных, например удаление элемента в двоичном дереве.

Практикуйтесь в реализации всех упомянутых здесь структур данных до тех пор, пока вам не придётся ничего искать, и вам будет очень легко отвечать на перечисленные выше вопросы, когда собеседование будет настоящим. Сосредоточьтесь на понимании того, почему код написан именно так, а не на попытках запомнить код точно. Когда вы пишете код, исходите из понимания того, что должно произойти дальше, а не ориентируйтесь по памяти. Вероятно, вас не попросят реализовать массив или сбалансированные деревья BST, такие как деревья АВЛ/красно-черные, но вы должны знать, как они работают.

Практика с ассистентом (имитация собеседования)

Одной практики по темам и вопросам недостаточно. Во время собеседования вы будете общаться с реальным человеком, который оценивает ваши навыки прямо здесь и сейчас. Это ситуация более напряжённая, чем когда вы учитесь дома. Чтобы обойти неловкость и беспокойство настоящего собеседования, заранее проведите много имитационных собеседований. Это поможет вам чувствовать себя комфортно и сосредоточиться на вопросе собеседования, а не отвлекаться на что-то нетехническое. Вы можете попросить друга помочь вам или найти в Интернете сервис, который подберёт вам человека, чтобы пройти имитационное собеседование.

Когда вы будете готовы?

Вы никогда не почувствуете себя «готовым», как бы долго вы ни учились. Всегда есть множество тем, в которые можно погрузиться глубже, или требующие больше практики слабые места. Во всем этом определённо есть элемент удачи. Вполне возможно, что вам зададут вопрос по теме, к которой совсем не подготовились или где очень слабы. Также возможно, что вы получите все вопросы по темам, в которых вы действительно сильны два месяца назад, и вам не нужно было тратить дополнительное время на изучение, чтобы сдать экзамен. Вы не можете подготовиться ко всем возможным исходам, но ваши шансы на успех будут выше, чем у других, если вы будете больше практиковаться.

Очень важно отслеживать прогресс и получать обратную связь, чтобы знать, когда вы действительно готовы выступить на настоящем собеседовании, не полагаясь только на эмоции. Следите за временем выполнения, когда вы задаёте себе практические задачи, и старайтесь не более 40 минут на ответы на большинство вопросов среднего уровня и 1 час на ответы на сложные вопросы на leetcode.com или hackerrank.com.

Большая часть кода на собеседовании оценивается на небольшом наборе крайних случаев, и небольшие ошибки всегда пропускаются или считаются несущественными. Люди не ждут совершенства, но они должны увидеть достаточно «сигналов», чтобы убедиться в том, что вы подходите. Пройдите как минимум три фиктивных собеседования, прежде чем идти на настоящее. Двигайтесь вперёд только в момент, когда сможете стабильно хорошо работать во время тренировки.

Крупные технологические компании нанимают сотрудников постоянно, поэтому они могут очень гибко планировать или переносить дату собеседования. Я перенёс свои собеседования в Google и Uber на 2 и 1 месяц соответственно, потому что не был готов. В прошлом я делал ещё более длительные переносы. Чтобы перенести собеседование, не нужно никаких особых оправданий. Я просто говорил: «Мне нужно больше времени на подготовку». Эти компании тратят много денег на ваше собеседование. 5–6 штатным сотрудникам платят за собеседование в течение 4–5 часов с последующей оценкой результатов. Учитывайте зарплаты рекрутеров, они нашли время, чтобы найти вас и обработать лишь небольшой процент заявок от людей, которые прошли через них, и это как минимум несколько тысяч долларов за собеседование. Компании хотят, чтобы люди приходили подготовленными. Они будут ждать, а не тратить время, деньги (и не только их) на отказ от инженера, который мог бы подойти, если бы они просто подождали ещё месяц или два. Так что отложите мероприятие, если не готовы. Никогда не идите на собеседование, не будучи готовым!

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

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


Надеюсь, данная статья была вам полезна. Главная мысль, которую я хотел донести — чтобы устроиться на работу в ведущую технологическую компанию, вам не нужно специальное высшее образование (хотя оно будет полезно), гены счастливчика или длинный послужной список. Единственное, что вам нужно, – это уделять время последовательному обучению и практике и не забывать про промокод HABR, который добавит дополнительно 10% к скидке на баннере.

---

• Профессия Data Scientist
• Профессия Data Analyst
• Курс «Алгоритмы и структуры данных»