На работу в Google

[Necroman]

Компания Google легендарна не только своими зарплатами, необычными условиями работы (можно приводить на работу детей и домашних животных, питаться, лечиться и заниматься спортом бесплатно, 20% времени заниматься личными проектами, работать в маленьких динамичных коллективах по 3-4 человека, и т.п.), но и жесточайшим отбором кандидатов. Проходит несколько месяцев, прежде чем человек, пройдя несколько телефонных и очных интервью, получает приглашение. Или не получает, без объяснения причин. Надо ли объяснять причины, если в сутки Google получает до 1000 новых резюме?

Google имеет центры разработок в Калифорнии (недалеко от Сан-Франциско), Нью-Йорке, Цюрихе, Дублине, Москве и многих других роскошных местах, где приятно жить и работать. Если кто-нибудь из читателей когда-нибудь попробует туда устраиваться, возможно, будет полезным узнать про стиль вопросов, которые задаются кандидатам на интервью.

Базовая телефонная проверка:

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

2. Какой оператор C++ нужно использовать для освобождения массива, созданного с помощью ”new char[10]”?

3. Расположите процессы в порядке убывания их скорости, от самого быстрого до самого медленного:
a. чтение из регистра процессора
b. переключение контекста
c. считывание с диска
d. считывание из оперативной памяти

Алгоритмы и структуры данных:

1. Придумайте алгоритм сортировки миллиона 32-битных целых чисел, имея в наличии 2 мегабайта памяти. Какие способы улучшения производительности вашего алгоритма вы можете предложить?

2. Напишите функцию, которая определит, является ли её аргумент степенью двойки. А теперь без циклов.

3. Напишите функцию, которая найдёт K-й наименьший элемент в бинарном дереве (binary search tree).

4. Расположите алгоритмы в порядке убывания вычислительной сложности:
a. перемножение двух матриц
b. сортировка вставкой (insertion sort)
c. двоичный поиск (binary search)
d. heap sort

C/C++:

1. Когда лучше использовать C, а когда - C++?

2. Как бы вы реализовали Unix-утилиту "tail" (она возвращает N последних строк в файле). Какую структуру данных использовали бы? Есть ли структура данных, которая поддерживала бы заданное количество элементов автоматически? Как бы вы реализовали это в C++? Какие C-функции по перемещению файлового указателя (file pointer) и определения размера файла вы знаете?

3. В чем разница между malloc и calloc?

4. Зачем нужны виртуальные деструкторы?

5. Как бы вы убили все HTTPD процессы на Unix-машине? Как бы вы скормили список параметров Unix-утилите вроде ”kill”?

6. Что напечатает нижеследующая программа?

int *f(int n)
{
int r = n + 1;
return &r;
}

int main()
{
int *n1 = f(1);
int *n2 = f(2);
return printf(”%d”, *n1);
}

Алгоритмы и стуктуры данных:

1. Назовите самую интересную и значимую проблему из решенных вами.

2. Сортированный массив циклически сдвинули неизвестное число раз. Как найти элемент в таком массиве? Как это сделать за логарифмическое время?

3. Какие структуры данных можно использовать для хранения разного рода словарей? Когда вы использовали бы ту или иную? Можете ли вы сконструировать структуру данных, имеющую среднее время выборки O(1), а наихудшее - O(log n)?

4. Есть прямоугольная матрица, где числа в каждой строке и каждом столбце упорядочены (например, по возрастанию). Как бы вы искали число в такой матрице? Можете ли вы сделать это за линейное время? А за логарифмическое?

Очные интервью ("программирование у доски"):

1. Как бы вы нашли одинаковые элементы в N сортированных связанных списках?

2. Представьте, что есть массив из N=1000 элементов. Число N растёт, увеличиваясь на единицу на каждом шаге. После каждого шага в массиве должно остаться ровно k=1000 помеченных элементов и N-k непомеченных. Каждый из N элементов имеет одинаковую вероятность быть помеченным. Не зная финального значения N (допустим, что N растет бесконечно), как можно эффективно обеспечивать выполнение вышеуказанных правил о пометке на каждом шаге? Определите сложность предлагаемых решений.

3. Представьте, что у вас есть строка ”putinsayshewantstoboosteconomy” (без пробелов). Спроектируйте алгоритм расстановки пробелов в нужные места (т.е. извлечения отдельных слов из текста)? Какая структура данных особенно эффективна для этой цели? Оцените максимум и минимум требуемого места. Как выбрать из нескольких возможных вариантов разбиения? Где можно получить необходимую для этого информацию, и как?

4. Если у вас есть строка из N символов, сколько есть способов разбить её на отдельные "слова"?

5. Объясните простыми словами самое крутое, что вы сделали на вашей предыдущей (нынешней) работе.

6. Пользователь ввел поисковый запрос из N ключевых слов. У вас есть N списков (по одному на каждое ключевое слово), в которых хранятся смещения от начала документа, где это слово встречается. Списки отсортированы. Спроектируйте эффективный алгоритм поиска наименьшего фрагмента документа, содержащего каждое из ключевых слов хотя бы 1 раз? Фактически требуется найти N чисел, по одному из каждого списка, так, чтобы разница между максимальным и минимальным числом была наименьшей. Порядок слов не имеет значения, допускается многократный повтор любого слова в пределах найденного (минимального) фрагмента. Оцените сложность алгоритма. Реализуйте его.

7. Какие вопросы вы задали бы пользователю, если бы проектировали систему кеширования? Какие схемы кеширования (caching policies) вы можете предложить? Как бы вы реализовали каждую из них? Какие методы вы имели бы в классе, реализующем такую систему?

[Cerber]

прикольно.

[fog]

Google стал лучшим американским работодателем

Согласно ежегодному рейтингу журнала Fortune, самым привлекательным работодателем среди американских компаний оказался Google. Второе место в числе компаний, предлагающих своим струдникам наиболее выгодные условия работы заняла фармацевтическая компания Genentech а третье - Wegmans Food Markets. Google, как выяснилось, предлагает своим служащим многочисленные полезные услуги бытовой сферы, такие как бесплатные прачечная и химчистка, транспорт, спа-салон, обеды и онлайновые медицинские консультации.

Рейтинг ста лучших мест работы был составлен на основе опросных данных более 105000 сотрудников 446 организаций, сообщает Reuters. При составлении учитывалось мнение респондентов о подходе к организации и управлению рабочим процессом, удовлетворение, которое им приносят работа и коллектив, а также размер зарплаты, бонусные программы, социальные гарантии и возможности карьерного роста.

[Ab]

А про Интел там ничего не сказано?

[Necroman]

Вот здесь находится текущий рейтинг лучших работодателей по версии Fortune:
http://money.cnn.com/magazines/fortune/ ... nies/2007/

Microsoft на 50-м месте. Intel в 100 лучших не попадает.

[Necroman]

По Сети разбежалась заметка бывшей сотрудницы Google и Microsoft, которая рассказывает о плюсах и минусах работы в обеих компаниях. Из заметки создаётся впечатление, что Google - это такая анархическая коммуна а-ля "ешь и спи на работе", с кучей веселья и всяких вкусных мелочей, где у менеджера сотня подчинённых, а в компании всего 4 уровня иерархии. Microsoft выступает чем-то бюрократическим вроде ВНИИЭФ, зато программисты вместо "открытых кубиков" живут в своих небольших закрытых комнатах.

http://no2google.wordpress.com/2007/06/ ... erspective

[fog]

Из блога одного....

Олег Нестеров рассказал. Зимой его Эндрю Мортон (да-да, тот самый Эндрю Мортон) позвал работать в Google, в kernel team. В общем-то, Олег сейчас работает явно не там, где ему бы надо по его мозгам, плюс к тому же не прочь свалить в солнечную Калифорнию, где много диких обезьян.

Казалось бы, если сам Эндрю Мортон рекомендует человека, а человек не против, то всё должно быть легко и просто. Фига с два -- Гугл большая компания, там всё по правилам и регламентам, никаких исключений.

Олега начинают интервьюировать по телефону, какой-то индиец с жутким акцентом (ох, я наслушался таких, пока работал в Deutsche Bank!). А Олег ведь по email работает, по-английски устно разговаривал пару раз в жизни, даже названий английских букв (типа R - а') толком не знает. Из-за этого всё своё CPU time в процессе телефонного интервью он тратит на попытки понять собеседника, и собственно на ответы ресурсов мозга уже банально нет. Я это очень хорошо понимаю - сам был в такой ситуации, по телефону особенно сложно разговаривать, гораздо сложнее, чем очно, особенно если вообще нет никакой практики.

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

Ну вот. Короче, он не прошёл интервью! Думаете, это он потерял? Фига с два -- это Гугл потерял первоклассного кернель-хакера!

Выводы:
1. В негигантской компании (например, в нашей) такой фигни бы не случилось.
2. Учите английский! В том числе и устный тоже. Старайтесь практиковаться.

[Necroman]

Согласен с тем, что молох Google recruiting перемалывает и весьма достойных. Мне особенно легко это говорить после того, как меня самого туда не взяли

Но в данном случая я бы сам не взял этого "kernel-hacker"а. Потому как серьёзная работа делается коллективом, требуется плотное общение (в том числе - по телефону). А такой вот "немой" будет только тормозить процесс, будь он даже семи пядей во лбу.

[fog]

Цитата(Necroman @ 17.08.2007 - 00:07) Но в данном случая я бы сам не взял этого "kernel-hacker"а. Потому как серьёзная работа делается коллективом, требуется плотное общение (в том числе - по телефону). А такой вот "немой" будет только тормозить процесс, будь он даже семи пядей во лбу.

Любого человека можно выучить английскому, а вот людей уровня Мортона ты не найдешь (а научить не сможешь и подавно). Кстати, кто не знает, Мортон - второй человек (после Линуса Торвольдса) в команде разработки linux-kernel.

Но главное, коллективы, занимающиеся kernel-develop и .... каким-нибудь маркетойдной фигней - это две большие разницы! Ну не принято у девелоперов (если лично друг-друга не знают) по телефону общаться - они даже если за соседними столами сидят, будут через комментарии в cvs решать производственные вопросы.
... Ну, в крайнем случае, в рассылке.

[Necroman]

Но главное, коллективы, занимающиеся kernel-develop и .... каким-нибудь маркетойдной фигней - это две большие разницы! Ну не принято у девелоперов (если лично друг-друга не знают) по телефону общаться - они даже если за соседними столами сидят, будут через комментарии в cvs решать производственные вопросы. ... Ну, в крайнем случае, в рассылке.

Может, это у линуксоидов не принято. Там же каждый сам по себе. А в нормальных конторах - берёшь трубку и звонишь, и это не считая заранее спланированных team meetings.