Привет! Давно не писал. Да это и понятно. Защита диссертации, получение PhD, а сейчас ещё и активный поиск работы — всё это занимает очень много драгоценного времени. Но разговор сегодня пойдёт не о том. Хотелось бы поделиться с Вами, уважаемые читатели, ресурсами и описанием процесса подготовки к телефонному техническому интервью с Гуглом, первый технический этап которого я уже прошёл, и теперь готовлюсь ко второму, который будет в пятницу.
Структура постов будет следующая:Темы и источники информации, которые посоветовал почитать рекрутер
Технические задачки и их решения на C/C++ и Python
Транскрипт моего реального интервью
Темы и источники информации
Я долго гадал, нужно ли оставлять версию текста на английском. Но боясь быть заклёванным на месте — решил перевести всё на русский. Итак, это темы, которые может затронуть инженер при общении с Вами:Продукты Google (что вы используете)
Навыки программирования, Вас попросят написать код, используя Google Doc (интервью по телефону) или же на доске (последние этапы интервью в офисе компании). Обновите свою память синтаксиса языков и стандартных библиотек
Дизайн алгоритмов и анализ
Системный дизайн
Открытое обсуждение, не забывайте думать вслух и уточнять детали проблемы, которую Вам задали
Программирование:создание / проход структур данных
имлементирование системных рутин
сворачивание больших массивов данных до единственного числа
преобразование одного типа данных в другой
Дизайн алгоритмов / Анализ:анализ большой-O (асимптотики, сложность алгоритма)
сортировка и хешинг, поиск
управление с безумно огромным количеством данных
и анализ сложности тем из «Программирование» выше
Системный дизайн:набор функций
интерфейсы
иерархия классов
дизайн системы при определённых условиях
простота и надёжность
компромиссы
Открытое обсуждениеописать самое сложное испытание, с которым Вы сталкивались
лучший / худший дизайн, который Вы видели
анализ производительности и оптимизация
тестирование
идеи по улучшению продуктов Google
Ссылки:
Interviewing at Google
продукты Google — http://www.google.com/intl/en/options/
Посты (всё на английском):
The Official Google Blog: Baby steps to a new job by Gretta Cook (Google Engineer)
How to Get Hired by Steve Yegge (Google Engineer)
How to Get Hired by Dan Kegel (Google Engineer)
Five Essential Phone Screen Questions by Steve Yegge (Google Engineer)
Двоичный поиск — Binary Search
Задачи для практики программирование — Project Euler
Types of algorithm questions Google asks: Top Coder Tutorials
Industry News: search engine land
Книги:
Книга номер 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)
Системный дизайн
Google File System
Google Bigtable
Google MapReduce
Сортировки. Знайте как сортировать. Не вздумайте делать сортировку пузырьками. Нужно знать как минимум один 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 ситуациях, и как их избежать. Знайте какие ресурсы нужны процессу, ните, как работает переключение контекстов, как оно осуществляется на базе операционной системы и железа. Знайте о расписаниях. И так как мир движется в сторону много-ядерности, узнайте об это как можно больше.
для информации о Системном Дизайне
В следующей части мы поговорим о конкретных задачах и их реализациях на Си, Си++ и Питоне.
