Pull to refresh

Я хочу работать в Google! Телефонное интервью (часть 1)

Reading time 4 min
Views 31K
Привет Хабр! Давно не писал. Да это и понятно. Защита диссертации, получение PhD, а сейчас ещё и активный поиск работы — всё это занимает очень много драгоценного времени. Но разговор сегодня пойдёт не о том. Хотелось бы поделиться с Вами, уважаемые хабралюди, ресурсами и описанием процесса подготовки к телефонному техническому интервью с Гуглом, первый технический этап которого я уже прошёл, и теперь готовлюсь ко второму, который будет в пятницу.

Структура постов будет следующая:
  1. Темы и источники информации, которые посоветовал почитать рекрутер
  2. Технические задачки и их решения на C/C++ и Python
  3. Транскрипт моего реального интервью (Из гугла попросили не публиковать данные материалы)


Темы и источники информации



Я долго гадал, нужно ли оставлять версию текста на английском. Но боясь быть заклёванным на месте — решил перевести всё на русский. Итак, это темы, которые может затронуть инженер при общении с Вами:
  • Продукты Google (что вы используете)
  • Навыки программирования, Вас попросят написать код, используя Google Doc (интервью по телефону) или же на доске (последние этапы интервью в офисе компании). Обновите свою память синтаксиса языков и стандартных библиотек
  • Дизайн алгоритмов и анализ
  • Системный дизайн
  • Открытое обсуждение, не забывайте думать вслух и уточнять детали проблемы, которую Вам задали


Программирование:
  • создание / проход структур данных
  • реализация системных вызовов (implement system routines)
  • сворачивание больших массивов данных до единственного числа
  • преобразование одного типа данных в другой


Дизайн алгоритмов / Анализ:
  • анализ большой-O (асимптотики, сложность алгоритма)
  • сортировка и хеширование, поиск
  • управление с безумно огромным количеством данных
  • и анализ сложности тем из «Программирование» выше


Системный дизайн:
  • набор функций
  • интерфейсы
  • иерархия классов
  • дизайн системы при определённых условиях
  • простота и надёжность
  • компромиссы


Открытое обсуждение
  • описать самое сложное испытание, с которым Вы сталкивались
  • лучший / худший дизайн, который Вы видели
  • анализ производительности и оптимизация
  • тестирование
  • идеи по улучшению продуктов Google


Ссылки:
Interviewing at Google

продукты Google — http://www.google.com/intl/en/options/

Посты (всё на английском):


Книги:
Книга номер 2 была рекомендована несколькими инженерами и очень репрезентативно показывает вопросы, которые у Вас будут спрашивать.
  1. Review of Basic Algorithms: Introduction to the Design and Analysis of Algorithms by Anany Levitin
  2. 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'а, во время интервью (часть тем дублируется с ранее упоминавшимися)

  1. Сложность алгоритмов. Нужно знать большое-О. Если у Вас проблемы с базовыми анализами алгоритмов — почти гарантированно Вас не наймут. Больше информации про алгоритмы
  2. Кодинг. Вы должны знать как минимум один язык программирования очень хорошо, и лучше если это будет С++ или Java. C# тоже сгодится, т.к. он схож с Java. Ожидайте, что Вы будете писать код во время интервью и должны будете знать особенности синтаксиса языка.
  3. Очень советуется книга для прочтения: Programming Interviews Exposed; Secrets to landing your next job by John Monagan and Noah Suojanen (Wiley Computer Publishing)
  4. Сортировки. Знайте как сортировать. Не вздумайте делать сортировку пузырьками. Нужно знать как минимум один n*log(n) алгоритм сортировки, а лучше два или больше (подойдёт quicksort и merge sort)
  5. Хеширование. Не просто так считается одним из самых важных способов хранения структур данных. Необходимо знать как работает хеш. Знайте как написать его использую язык на Ваш выбор в течении 5-20 минут.
  6. Деревья. Знайте что это такое, базовые конструкции, проход и манипуляции с ними. Ознакомьтесь с бинарными деревьями, n-арными и третичными деревьями. Знайте как минимум один тип сбалансированных бинарных деревьев: красное/чёрное дерево, скошенное (a splay tree) или AVL дерево. Знайте как его создать и проход по нему в глубину (DFS) и в ширину (BFS), знайте разницу между inorder, postorder и preorder проходом.
  7. Графы. Очень важны для Google. Всего есть 3 основных способа представить граф в памяти: объекты и указатели, матрица и последовательности связей (adjacency list). Знайте преимущества и недостатки этих способов представления данных графа. Знайте базовые алгоритмы прохода по графу: в глубину (DFS) и в ширину (BFS). Знайте сложность этих алгоритмов, и как написать их в вашем языке программирования. Ознакомьтесь с алгоритмами Дейкстры (Dijkstra) и A*
  8. Другие структуры данных. Изучите как можно больше других структур данных и алгоритмов. Вы должны быть знакомы с известными NP-полными проблемами, такими как путешествие коммивояжера (traveling salesman — TSP) и задача о ранце (knapsack problem). Узнавайте эти задачи в других или преобразуйте данную задачу к известным. Узнайте что значит NP-полная (NP-complete) задача.
  9. Математика. Некоторые экзаменаторы задают задачки из основ дискретной математики. Это более распространено в Google, чем в других компаниях, потому что мы окружены счётными задачами, вычислением вероятностей и другими математическими головоломками. Обновите свои знания и навыки комбинаторного вычисления и нахождения вероятностей, выборкой и т.д.
  10. Операционные системы. Знайте о процессах, нитях (threads) и проблемах конкуренции. Знайте о замках, мьютексах, семафорах и мониторах, и как они работают. Знайте о deadlock и livelock ситуациях, и как их избежать. Знайте какие ресурсы нужны процессу, нити, как работает переключение контекстов, как оно осуществляется на базе операционной системы и железа. Знайте о расписаниях. И так как мир движется в сторону много-ядерности, узнайте об это как можно больше.
  11. для информации о Системном Дизайне


В следующей части мы поговорим о конкретных задачах и их реализациях на Си, Си++ и Питоне.
Tags:
Hubs:
+157
Comments 99
Comments Comments 99

Articles