May 15th, 2011

glider

онсайт собеседование с гуглом, часть третья, последняя

Первая часть
Вторая часть

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

В целом, вопросы можно разделить на две категории: 1) алгоритмические задачки с двойным дном, 2) открытые проблемы дизайна некоей нагруженной системы.

Вопросы из первой категории затрагивали достаточно базовые вещи: биты, строки (полезно будет узнать, как хранить наборы строк, чтобы потом быстро по ним искать), сортировки (крайне рекомендую ознакомиться с алгоритмом quick select), деревья (очень советую поискать несколько задачек на обход деревьев и графов и не полениться их закодировать - для меня результат был неожиданным), несложное динамическое программирование. Как и писали в интернете, на каждом шагу спрашивают временную сложность алгоритмов. Удивительно, но не было ничего про графы - в силу размера выборки это трудновато списать на случайность.

Вопросы из второй категории были связаны с тем, как построить ту или иную распределенную систему, которая работает с большими объемами данных и/или обрабатывает много запросов. Поговорили про партишенинг, про оптимизацию объемов трафика, про то, как переходить от обычных структур данных и алгоритмов к распределенным, немного затронули map/reduce. Важной темой также были вопросы в стиле "оцените какой объем будет занимать база данных через 10 лет".

В свете вышесказанного лучший вариант подготовки - неделю вспомнить базовые алгоритмы и неделю-две порешать TopCoder (еще пару мыслей о подготовке я написал в каментах к соседнему посту). На мой взгляд, важнее всего здесь не алгоритмические изыски или знание навороченных структур данных (изучение этих вопросов, конечно, поможет, ибо потренирует нужные отделы мозга, но это время можно употребить с большей пользой). Главное - натренироваться качественно рассматривать возможные варианты входных данных. В этом плане я сильно прокололся на последнем интервью - в упор не увидел два вырожденных случая, в результате чего алгоритм получился неправильным. Также желательно иметь представление о базовых принципах построения распределенных систем. С этими вещами я на практике вообще не сталкивался, но когда-то читал про map/reduce + послушал доклад Олега и Кирилла и этого уже хватило на увлекательную беседу. Впрочем, может, увлекательной она было только для меня, не знаю.

На закуску несколько наблюдений о интервьюерах.
1. Начинаешь что-то писать сразу после выслушивания условия, интервьюер сразу делает пометку. Такое случилось не один раз, поэтому, мне кажется, это неслучайно. Не потому ли, что типа недостаточно подумал?
2. Также несколько раз слышал: "как бы вы писали юнит-тест для данного алгоритма". Насколько я вспоминаю, во всех этих случаях у меня в алгоритме были неточности, поэтому логично предположить, что эта фраза является эвфемизмом для "у вас косяк".
3. Часто случалось так, что после буквально 30-40 секунд обдумывания (вслух или про себя - неважно) мне сразу давали хинт. Интересно, что бы это значило - может, просто интервьюерам хотелось побыстрее перейти к интересной части задачки.
4. В митинг-руме был круглый стол и стулья. Все интервьюеры, кроме последнего, садились не напротив меня, а под углом около 90 градусов от моей позиции. Удивительно, но это сработало и, действительно, делало беседу более приятной. Это было хорошо заметно на контрасте с нашим общением с последним интервьюером.

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