Я хочу работать в Google! Телефонное интервью (часть 1)
Я долго гадал, нужно ли оставлять версию текста на английском. Но боясь быть заклёванным на месте — решил перевести всё на русский. Итак, это темы, которые может затронуть инженер при общении с Вами:
Продукты Google (что вы используете)
Навыки программирования, Вас попросят написать код, используя Google Doc (интервью по телефону) или же на доске (последние этапы интервью в офисе компании). Обновите свою память синтаксиса языков и стандартных библиотек
Дизайн алгоритмов и анализ
Системный дизайн
Открытое обсуждение, не забывайте думать вслух и уточнять детали проблемы, которую Вам задали
Программирование:
создание / проход структур данных
реализация системных вызовов (implement system routines)
сворачивание больших массивов данных до единственного числа
преобразование одного типа данных в другой
Дизайн алгоритмов / Анализ:
анализ большой-O (асимптотики, сложность алгоритма)
сортировка и хеширование, поиск
управление с безумно огромным количеством данных
и анализ сложности тем из «Программирование» выше
Системный дизайн:
набор функций
интерфейсы
иерархия классов
дизайн системы при определённых условиях
простота и надёжность
компромиссы
Открытое обсуждение
описать самое сложное испытание, с которым Вы сталкивались
Книги: Книга номер 2 была рекомендована несколькими инженерами и очень репрезентативно показывает вопросы, которые у Вас будут спрашивать.
Review of Basic Algorithms: Introduction to the Design and Analysis of Algorithms by Anany Levitin
Types of coding questions Google asks: Programming Interviews Exposed; Secrets to Landing Your Next Job (Programmer to Programmer) by John Mongan, Noah Suojanen, and Eric Giguere
(от себя: прочитал обе книги. Даже если вы не планируете подаваться на работу в Google, но программируете хоть иногда — прочитайте эти книги просто для себя.)
Один из инженеров дал краткий обзор тем, которые спрашивают у Software Engineer'а, во время интервью (часть тем дублируется с ранее упоминавшимися)
Сложность алгоритмов. Нужно знать большое-О. Если у Вас проблемы с базовыми анализами алгоритмов — почти гарантированно Вас не наймут. Больше информации про алгоритмы
Кодинг. Вы должны знать как минимум один язык программирования очень хорошо, и лучше если это будет С++ или Java. C# тоже сгодится, т.к. он схож с Java. Ожидайте, что Вы будете писать код во время интервью и должны будете знать особенности синтаксиса языка.
Очень советуется книга для прочтения: Programming Interviews Exposed; Secrets to landing your next job by John Monagan and Noah Suojanen (Wiley Computer Publishing)
Сортировки. Знайте как сортировать. Не вздумайте делать сортировку пузырьками. Нужно знать как минимум один n*log(n) алгоритм сортировки, а лучше два или больше (подойдёт quicksort и merge sort)
Хеширование. Не просто так считается одним из самых важных способов хранения структур данных. Необходимо знать как работает хеш. Знайте как написать его использую язык на Ваш выбор в течении 5-20 минут.
Деревья. Знайте что это такое, базовые конструкции, проход и манипуляции с ними. Ознакомьтесь с бинарными деревьями, n-арными и третичными деревьями. Знайте как минимум один тип сбалансированных бинарных деревьев: красное/чёрное дерево, скошенное (a splay tree) или AVL дерево. Знайте как его создать и проход по нему в глубину (DFS) и в ширину (BFS), знайте разницу между inorder, postorder и preorder проходом.
Графы. Очень важны для Google. Всего есть 3 основных способа представить граф в памяти: объекты и указатели, матрица и последовательности связей (adjacency list). Знайте преимущества и недостатки этих способов представления данных графа. Знайте базовые алгоритмы прохода по графу: в глубину (DFS) и в ширину (BFS). Знайте сложность этих алгоритмов, и как написать их в вашем языке программирования. Ознакомьтесь с алгоритмами Дейкстры (Dijkstra) и A*
Другие структуры данных. Изучите как можно больше других структур данных и алгоритмов. Вы должны быть знакомы с известными NP-полными проблемами, такими как путешествие коммивояжера (traveling salesman — TSP) и задача о ранце (knapsack problem). Узнавайте эти задачи в других или преобразуйте данную задачу к известным. Узнайте что значит NP-полная (NP-complete) задача.
Математика. Некоторые экзаменаторы задают задачки из основ дискретной математики. Это более распространено в Google, чем в других компаниях, потому что мы окружены счётными задачами, вычислением вероятностей и другими математическими головоломками. Обновите свои знания и навыки комбинаторного вычисления и нахождения вероятностей, выборкой и т.д.
Операционные системы. Знайте о процессах, нитях (threads) и проблемах конкуренции. Знайте о замках, мьютексах, семафорах и мониторах, и как они работают. Знайте о deadlock и livelock ситуациях, и как их избежать. Знайте какие ресурсы нужны процессу, нити, как работает переключение контекстов, как оно осуществляется на базе операционной системы и железа. Знайте о расписаниях. И так как мир движется в сторону много-ядерности, узнайте об это как можно больше.
Напомнило старый анекдот. Обычный американский фильм с обычным американским диалогом: — How do you do? — All right!
Перевод: — Как ты это делаешь?Как вы это делаете? — Всё правой.Инструкция к установке ПО: Just execute the installer. Перевод: Просто казните монтажника
Напомнило старый анекдот.Обычный американский фильм с обычным американским диалогом:— How do you do?— All right! Перевод:— Как ты это делаешь?— Всё правой.Инструкция к установке ПО: Just execute the installer.Перевод: Просто казните монтажникаНЛО прилетело и опубликовало эту надпись здесьКстати попробовал:How do you do? перевод:Как вы это делаете? в том то и дело что «как вы это делаете»вместо «как дела»это еще более фееричней чем «все правой»
Лучше уметь программировать merge (и не уметь heap), чем наоборот. Хотя и то, и другое, конечно, еще лучше.Слияние трех упорядоченных массивов студенты на экзамене написать (на C/C++) не могут — проверено :Спасибо. Кажется, они забыли сказать, что для сортировки групп надо использовать алгоритм, работающий за O(k) обменов групп (иначе все слияние в O(n) никак не уложится), но в целом, идея понятна. Как-нибудь попробую. Еще бы smoothsort понять
На мой взгляд из O(n log n) сортировок лучше вместо mergesort'а разобраться в heapsort'е, ибо: 1. В отличие от quicksort'а гарантированное Θ(n log n) время. 2. В отличие от mergesort'а, in-place, т.е. требует O(1) дополнительной памяти. 3. Используется структура heap, знать которую, конечно же, нужно.
Ну и вообще, для саморазвития не лишним будет разобраться в сортировках, работающих за линейное время, почему такое возможно, и, возможно, методами обеспечения Θ(n log n) времени для quicksort'а (см. introsort).
В русскоязычной литературе есть часто используемые названия для задач: Путешествие продавца — Задача комивояжера, Проблема о рюкзаке — Задача о ранце.Слабаков в google не берут.НЛО прилетело и опубликовало эту надпись здесь
