И вот несколько недель назад мне пришло «from Google Russia», в Московском и Питерском офисе открыты вакансии на инженеров-стажеров. Я опять сказал, что никуда пока не хочу, хочу учиться. Предложили прособеседоваться, так, на будущее.. Я был не против, и вот, на 13 декабря договорились провести со мной телефонное собеседование.
(история гораздо длиннее и интереснее, но я хочу рассказать именно о собеседовании)
Ровно в два часа дня, как и договаривались, позвонил Костя, программист из московского офиса. Собеседование состояло из трех частей: введение (по-русски, объяснили что щас будет происходить), собственно собеседование (по-английски, я должен был отвечать на вопросы) и свободный разговор (по-русски, я мог задавать вопросы). Предварительно для меня расшарили текстовичок в Google Docs, в котором происходил весь обмен письменной информацией, вполне удобно.
So let's start. Дан массив X[n] и число Y, найти такие i ≠ j, что X[i] + X[j] = Y. Гавно вопрос! За O(n²) полным перебором. Костя захотел чего-нибудь более.. Быстрого. Я решил, что O(n) все равно недостижимо (я был так наивен), и тогда не грех и отсортировать массив за O(n log(n)). Отсортированный массив это хорошо, напрашиваются два индекса, идущие с разных сторон, пусть i слева, j справа. Тут я немного затупил, но Костя попросил медленно вслух повторить мысль и затуп разрешился. Смотрим текущую сумму X[i] + X[j], если она равна Y, то разговор окончен, если она меньше Y, то двигаем i вправо, ибо j двигать влево бесполезно, если она больше Y, то двигаем j влево. Повторяем сие действо, пока i < j. Иначе решения нет. Костя согласился с алгоритмом, попросил определить скорость — O(n), попросил доказать — доказал. (Уже после собеседования я смог строго доказать корректность алгоритма, Костя не прикапывался). Получаем в итоге O(n log(n)), я решил что неплохо, но меня так между делом спросили: "А за O(n) слабо?!" Задумался минут на 5... Предложили подсказку: какие контейнеры в Java я знаю. List, vector, hash map, .. Меня остановили, спросили, что я знаю про hash map. Я начал лечить что у него время доступа линейное, точнее почти линейное.. Понял что несу чушь, поправился, время доступа константное. "So could you use hash map here?" YES — крикнул я, не скрывая ощущения полного офигевания от простоты алгоритма, который уже понял. Идем по массиву, и добавляем каждый элемент X[i] в хэш таблицу следующим образом {ключ: x[i], значение: i}, и также проверяем в таблице наличие элемента с ключом (Y-X[i]), если он есть, то берем соответствующее ему значение j и пара i,j является искомой. Линейное время, память конечно покушается в некотором количестве, но как я понял тут было важно время.
So another task. Есть функция int foo(int x) { return x*100; }, реализовать эквивалентную ей, не используя операцию умножения. Гавно вопрос! x << 6 + x << 5 + x << 2. Костя согласился и предложил обобщить: написать алгоритм, которой для произвольного N будет генерировать выражение равное x*N. Написал алгоритм нахождения максимальной степени двойки, непревосходящей N (двигаем вправо, пока число положительно; считаем сдвиги). Дальше повторяя этот алгоритм получаем конечное разложение N на сумму степеней двойки: x << k₀ + x << k₁ + ... . Костя хитрым голосом предложил продемонстрировать работу алгоритма при N = 15. Вышло стремно: 8 + 4 + 2 + 1, можно ли как-нибудь по-лучше? Да, (x << 4) - x. Написал алгоритм для нахождения и этой степени, в итоге вышло x << k₀ - x << k₁ + x << k₂ - x << k₃ + ... . Этот алгоритм вроде не является лучше, ибо очень много зависит от начального числа, но Костя сказал ОК и сообщил, что 40 минут отведенные на собеседование кончились.
Фуух, я очень волновался, и эти 40 минут пролетели нереально быстро. Костя оказался выпускником МехМата МГУ, уже более трех лет работает в гугл, как я понял ему очень нравится. Оказалось, что они не gmail на русский переводят, а деляет вполне секретные и интересные проекты вместе с зарубежными коллегами. Поинтересовался, действительно ли их офисы такие клевые.. Да, клевые, но вот он уже привык и гораздо больше акцентировал внимание на том, что работа интересная. Пожелали друг другу удачи и все.
Никаких результатов, как я понимаю, не узнать, ну что ж, будем ждать писем ближе к лету. Работать в гугл не уверен, что хочу, но от стажировки точно не откажусь.
p.s. К собеседованию никак не готовился, проходил по большей части для себя.
