Всем привет! Я давно обещал рассказать о своём собеседовании в Facebook. Всё никак этого не делал, но лучше поздно, чем никогда. Сегодня я хочу рассказать о первом этапе — Skype-собеседовании.

Disclaimer. ❗️ Это статья из цикла рассказов о том, как я проходил собеседования в различные IT-компании. В этих статьях я из этических соображений не раскрываю задачи, которые мне давали. Цель этих статей — сформировать картину того, какие знания и навыки требуют от кандидатов на позицию разработчика современные IT-компании.

Процесс собеседования в Facebook в моём случае начинался так
1️⃣ Мне пришло письмо от их рекрутера примерно с таким текстом: «Привет, Илья! Ты проходил у нас собеседование 2,5 года назад. Ты показал себя очень круто, давай попробуем ещё раз»
2️⃣ После моего согласия мы с рекрутером созвонились, и он рассказал, как замечательно работать в Facebook London и как много у них разных увлекательных проектов. Вот я не понимаю эту особенность рекрутеров что в Facebook, что в Google — им обязательно надо позвонить тебе по телефону. Ни Skype, ни Whatsapp им не подходят. Только телефон, только хардкор. Из-за этого половина разговора состоит из фразы: «Sorry, I didn't get your question. Can you repeat it?»
3️⃣ Когда рекрутер убедился, что я живой человек, у которого есть телефон, он передал меня другому человеку (он называется Recruiting Coordinator), который через e-mail согласовал со мной дату Skype-собеседования.
4️⃣ Где-то в процессе этого согласования мне объяснили, что дадут задачу на написание кода, который надо будет писать в онлайн-редакторе, а также прислали материалы для подготовки, в которых объясняется, как всё будет проходить и чего от меня ждут.

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

Интересным выдался день самого Skype-интервью. Так вышло, что я очень плохо спал предыдущей ночью, поэтому в день собеседования я поступил так. За два часа до собеседования поспал часок, а затем в течение часа непосредственно перед собеседованием порешал задачи на leetcode, чтобы «включить мозги».

Итак, началось собеседование. Оно развивалось по стандартной схеме: интервьюер представился, рассказал в двух словах, чем занимается в компании, и дал алгоритмическую задачку. В ней фигурировало два параметра: N и M. Я начал с того, что быстренько описал тривиальное решение за O(N log N). Интервьюер сказал, что это ок, но стоит поискать что-то побыстрее. Я стал рассуждать и достаточно быстро придумал решение за O(NM). Оно было неплохим, потому что по условию задачи M очень маленькое.

И вот тут произошло странное 🤔 Я спрашиваю интервьюера, стоит ли мне поискать асимптотически более быстрое решение или можно переходить к реализации того, что есть? А он отвечает: «Как хочешь». Честно говоря, я впал в ступор, потому что когда я сам собеседую людей, я не даю им писать код, пока они не придумают алгоритм с подходящей асимптотикой. При этом совсем не понятно, как интерпретировать вот это «как хочешь». Это значит «меня эта асимптотика устраивает, давай посмотрим, как ты пишешь код» или «делай что хочешь, а я потом напишу, что ты не придумал оптимальный алгоритм, поэтому собеседование провалено»? При этом моя интуиция говорила, что у задачи должно быть асимптотически более быстрое решение, поэтому я стал его искать.

К счастью, я нашёл его довольно быстро — с асимптотикой O(N log M). Интервьюера это удовлетворило, и я перешёл к реализации.

Я думаю, я не раскрою великую тайну, если скажу, что частью решения была реализация алгоритма многопутевого слияния (M-way merge, как сортировка слияниями, только сливаем не два отрезка, а M). Прямо скажем, не самая простая штука для написания в онлайн-редакторе без возможности запуска и отладки 😄 У меня получилось 32 строчки кода.