Thread by @lenka_colenka

1. как человек, который проводил алгоритмические собесы в Google, а теперь собесит сеньоров, выкатываю тред про то, как готовиться к алгоритмическим собеседованиям!

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

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

4. Обычно интервью длится 45 или 60 минут, первые минут 5-10 интервьюер представляется, обычно говорит, как долго она работает в компании, в какой команде (запиши это!). Говорит формат интервью: мы порешаем задачку 30 или 45 минут, в конце оставим 10 минут на твои вопросы.

5. Тут есть 5 минут для тебя, чтобы кратко представиться: как зовут, где работаешь, кратко предыдущий опыт (буквально названия компаний и чем занималась). Если у тебя нет опыта прохождения собеседования на английском, порепетируй это!

6. Потом тебе формулируют задачку. Не бросайся сразу решать ее! нужно задать вопросы, даже если кажется, что тебе все понятно. Что-то типа "а что вернуть, если на вход дают пустой массив?", "а гарантируется, что массив отсортирован/не будет повторений"?

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

8. Сама приведи пример входных данных и напиши, какой результат ты ожидаешь! Типа если задача отсортировать массив, скажи, вот например на вход [10, -100, 22] результат будет [-100, 10, 22], а на вход [] результат будет []. Напечатай это, пусть будет у тебя перед глазами.

9. Теперь пришла пора... нет, не писать код!! Словами устно объяснить, что ты собираешься писать! Хорошая фраза в этом случае "first thing that comes to my mind is..." и говоришь очевидное brute-force решение. Например, для сортировки это будет bubble sort за квадрат.

10. Это дает тебе время подумать над более оптимальным решением. Это страховка на случай, если ты в итоге не придумаешь оптимальное решение (что-то ведь придумала!). Это дает интервьюеру понять, что ты понимаешь, что такое сложность алгоритмов.

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

12. У первого неоптимального решения обязательно скажи сложность работы! Типа "first thing that comes to my mind is bubble sort, but that will be quadratic. I think we can come up with a better solution". И переходим к более оптимальному решению!

13. Если ты сразу полностью придумала более оптимальное решение, это здорово! Если нет, нормально придумывать решение шаг за шагом, типа "I'd like to use priority queue here, then getting max will be cheap. But I need to think how to optimally insert data".

14. Интервьюер часто дает подсказки, не игнорируй их! Помни, что интервьюер на твоей стороне, она не хочет запутать тебя, она хочет помочь! Если ты понимаешь подсказки, это плюсик тебе в collaboration и technical communication.

15. Начинай писать код только после того, как интервьер подтвердила, что все поняла в твоем алгоритме и сама предложит написать код. Если интервьюер не предлагает, явно спроcи "should we start writing code?"

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

17. Теперь обязательно расскажи время работы алгоритма!! Это очень важно, ради этого мы и писали какое-то сложное решение. Метод за методом, в комментариях рядом напиши время работы в худшем и среднем случае.

18. Для этого нужно знать время работы операций структур данных в выбранном тобой языке. Заранее погугли время работы map, vector, array в твоем языке программирования. Например std::map и std::unordered_map отличаются во времени работы, так что это очень важно!

19. В конце в идеале должно остаться несколько минут для твоих вопросов. Помнишь мы записывали информацию про интервьюера в пункте 4? Пора подсмотреть в свои тетрадку и спросить, а чем именно занимается твоя команда? Чем тебе нравится компания? Что не нравится в компании?

20. Обычно в этот момент интервьюер говорит, что время закончилось и ей пора бежать. Поблагодарить и попрощаться. Вы великолепны!

21. Бонус темы для сеньоров: каков data access pattern? что мы оптимизируем, запись или чтение? является ли твое решение thread-safe? если нет, как можно его сделать thread-safe? если время осталось, можно подумать, как распараллелить на несколько машин

кстати, подписывайтесь на мой канал про (не)работу! t.me/lenka_ne_work