Добавлено: Пт дек 01, 2006 12:37 am
Компания 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) вы можете предложить? Как бы вы реализовали каждую из них? Какие методы вы имели бы в классе, реализующем такую систему?
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) вы можете предложить? Как бы вы реализовали каждую из них? Какие методы вы имели бы в классе, реализующем такую систему?