Разбор секции алгоритмов от айтишника, которого собесили в Google, Amazon, Fb

Коротко про форму и содержание

В прежние годы после предварительных собеседований вас вызывали для более подробного интервью в удобный для FAANG-компании город Европы и оплачивали все расходы. Это называлось on-site интервью. Сейчас все интервью проходят онлайн. 

Каждая компания любит свой сервис для видеозвонков. Google попросит Hangouts (у которого нет десктоп-приложения и который у меня не смог в видео в Chrome — приходилось запускать в Firefox, лол). Facebook захочет BlueJeans, а Amazon захочет Chime. У вас будет также сайт с поддержкой совместного редактирования текста. Собеседующий будет видеть и текст, и ваш курсор, и ваше выделение текста. Язык программирования вы выбираете сами. Поддерживается подсветка синтаксиса для всех популярных языков, но автодополнения, запуска программы и отладки нет.

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

У Google и Facebook интервью длится 45 минут, но из них только 40 выделено для решения задач. За это время обычно надо решить две задачи — времени в обрез.

У Amazon интервью длится 55 минут, 5 из которых также отводятся для ваших вопросов, и ещё минут 25 уйдёт на поведенческие вопросы.

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

Знания редких и экзотических алгоритмов не потребуется. Никаких редких алгоритмов можете не учить, вращать деревья руками тоже не требуется. Только базовые классические алгоритмы и базовые классические структуры данных. Но без знания кучи (heap) лучше не собеседоваться. Это редкая структура в обычной работе, но на её знание и применение нацелен целый пласт популярных и весьма прикладных задач.

Предположим, вы в прошлом выигрывали городские олимпиады по информатике и решили дальше не читать, а прямо так и пойти на интервью. Вам дали задачу, вы минутку подумали и быстренько закодировали задачу эффективным способом и без ошибок, а потом ещё и вторую, успели всё за 40 минут. Вы — молодец! Вы интервью успешно… завалили!

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

План успешного решения алгоритмической задачи на 20 минут

1. Обязательно уточните требования и разрешите любые неоднозначности в условии. Даже если вам кажется, что «и так всё ясно». Иногда эта информация может упростить решение. А иногда знание того, что, скажем, числа в последовательности могут повторяться и быть отрицательными, может поломать ваше «верное» решение. В любом случае, если вы не уточняли — это минус вам.

2. Подумайте над решением и озвучьте его. В идеале это не молчание на 5 минут, а рассуждение вслух. Плюсом будет озвучить очевидное вам неэффективное, но работающее решение. Любые соображения, что какие-то алгоритмы, структуры подходят или не подходят, лучше озвучивать.

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

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

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

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

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

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

Типичное решение редко превышает 20-30 строк кода. Никто не ждёт простыню кода. Если у вас слишком длинное решение, значит вы что-то делаете не так.

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

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

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

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

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

Очень часто в ходе отладки удачных входных данных находятся ошибки.

Хинт № 1. В случае рекурсивных функций я помечал разные версии значений переменных через слэш, где последнее значение было актуальным прямо сейчас.

Хинт № 2. Найденная и исправленная ошибка — это даже лучше, чем если бы вы всё сделали без ошибок. Вы показали дополнительный навык.

Как видите, шагов очень много, а у вас всего 20 минут. Поэтому режим очень жёсткий, надо тренироваться не выбиваться из времени: 2 минуты уточнили требования, за минутку описали наивное решение, 5 минут на поиск хорошего решения и оценку его сложности, 8 минут на написание кода, 4 минуты на выбор тестовых данных и отладку. Примерно так. Всё должно быть на автомате — ничего не забыть, нигде не замешкаться, бегом, бегом, бегом.

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

Примеры задач

=========================

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

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

Ссылка на такую же задачу на Leetcode

=========================

Список точек на плоскости задан координатами (x,y). Верните K точек наиболее близких к началу координат (0,0).

Вход: (0,1), (2,2), (5,5); K=2

Выход: (0,1), (2,2)

Ссылка на такую же задачу на Leetcode

=========================

Вернуть размер наибольшего континента на прямоугольной карте.

Связность континента по 4 направлениям (горизонтально и вертикально).

Вход: [

 [0,0,1,1],

 [0,0,0,1],

 [0,1,1,0],

 [0,1,0,0],

 [0,1,0,0],

]

Выход: 4

Ссылка на такую же задачу на Leetcode

=========================

Что общего и какие отличия у задач в Amazon, FB и Google

В целом на алгоритмическом интервью всё у всех очень похоже. Facebook даёт две задачи за одно интервью. А Amazon сначала вас выжимает поведенческими вопросами, а потом даёт одну задачу на кодирование.

У меня сложилось впечатление, будто у Google задачи немного сложнее. Не на порядок, но часто они будто из немного другого пула, чуть сложнее, чуть больше надо голову напрячь, чуть больше кодировать. Но при этом вторая задача у Google в обоих случаев была модифицированной и усложнённой первой. И решение первой у меня занимало минут 30-35. На вторую не всегда хватало времени закодировать полностью. В общем я и не получил предложение о работе.

Как к этому подготовиться

Leetcode

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

Я лично пользовался платной подпиской LeetCode.

Таким образом я получал доступ к статистике встречаемости задач в конкретных компаниях. Например, когда у меня были решены топ-20 для Amazon и Facebook, а общий счёт популярных задач был под 100, у Google из топ-10 оказалось решено меньше половины задач. Причём нерешенные были не совсем типичными.

Но главный плюс платной подписки был в доступе к разбору решений задач. У вас и без денег есть доступ к бесплатному форуму, где можно посмотреть чужие решения или задать вопрос по задаче. Но официальный разбор есть обычно у 95% задач, и он намного полезнее. Обычно разбираются все известные способы решения, начиная с неэффективного. Каждый способ идёт с описанием сути решения, программным кодом (часто на нескольких языках), часто с видео, оценкой сложности по скорости и памяти с обоснованием. 

Решив задачу, я смотрел и разбирался во всех альтернативных решениях. Часто замечал, что моё эффективное решение в разборе было реализовано более лаконично. Также полезно натренироваться обосновывать оценку сложности, особенно для всяких рекурсивных алгоритмов, алгоритмов с динамическим программированием. Полезно ознакомиться с англоязычной терминологией. Как по-английски «квадратичная сложность»? А «ребро», «вершина», «площадь фигуры», «узел дерева», «ветка дерева»?

Демо-интервью

Во-вторых, потренируйтесь с таймером. Посмотрите в интернете записи демо-интервью. Их распространяют часто сами FAANG-компании, но есть интервью с разборами ошибок и от сторонних авторов. Идеально хотя бы раз пройти демо-интервью самому и получить обратную связь. Чтобы человек со стороны сказал вам, что вы забыли, например, рассказать суть найденного решения перед кодированием или потеряли слишком много времени, расспрашивая тонкости условия задачи. Вы можете и не заметить такую ошибку в спешке.

Материалы от самих компаний

Компании FAANG открыто заявляют о необходимости подготовки к их интервью. Amazon даже рассылает в письмах ссылки вроде этих:

Блог «Cracking Amazon coding interview questions»;

Видео Amazon Coding Sample;

Видео по Amazon Leadership Principles.