Яндекс.Метрика

    Ни о чём →

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

    Привет Хабр! Давно не писал. Да это и понятно. Защита диссертации, получение PhD, а сейчас ещё и активный поиск работы — всё это занимает очень много драгоценного времени. Но разговор сегодня пойдёт не о том. Хотелось бы поделиться с Вами, уважаемые хабралюди, ресурсами и описанием процесса подготовки к телефонному техническому интервью с Гуглом, первый технический этап которого я уже прошёл, и теперь готовлюсь ко второму, который будет в пятницу.
    Структура постов будет следующая:
    1. Темы и источники информации, которые посоветовал почитать рекрутер
    2. Технические задачки и их решения на C/C++ и Python
    3. Транскрипт моего реального интервью


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



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


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


    Дизайн алгоритмов / Анализ:
    • анализ большой-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)
    5. Сортировки. Знайте как сортировать. Не вздумайте делать сортировку пузырьками. Нужно знать как минимум один n*log(n) алгоритм сортировки, а лучше два или больше (подойдёт quicksort и merge sort)
    6. Хеширование. Не просто так считается одним из самых важных способов хранения структур данных. Необходимо знать как работает хеш. Знайте как написать его использую язык на Ваш выбор в течении 5-20 минут.
    7. Деревья. Знайте что это такое, базовые конструкции, проход и манипуляции с ними. Ознакомьтесь с бинарными деревьями, n-арными и третичными деревьями. Знайте как минимум один тип сбалансированных бинарных деревьев: красное/чёрное дерево, скошенное (a splay tree) или AVL дерево. Знайте как его создать и проход по нему в глубину (DFS) и в ширину (BFS), знайте разницу между inorder, postorder и preorder проходом.
    8. Графы. Очень важны для Google. Всего есть 3 основных способа представить граф в памяти: объекты и указатели, матрица и последовательности связей (adjacency list). Знайте преимущества и недостатки этих способов представления данных графа. Знайте базовые алгоритмы прохода по графу: в глубину (DFS) и в ширину (BFS). Знайте сложность этих алгоритмов, и как написать их в вашем языке программирования. Ознакомьтесь с алгоритмами Дейкстры (Dijkstra) и A*
    9. Другие структуры данных. Изучите как можно больше других структур данных и алгоритмов. Вы должны быть знакомы с известными NP-полными проблемами, такими как путешествие коммивояжера (traveling salesman — TSP) и задача о ранце (knapsack problem). Узнавайте эти задачи в других или преобразуйте данную задачу к известным. Узнайте что значит NP-полная (NP-complete) задача.
    10. Математика. Некоторые экзаменаторы задают задачки из основ дискретной математики. Это более распространено в Google, чем в других компаниях, потому что мы окружены счётными задачами, вычислением вероятностей и другими математическими головоломками. Обновите свои знания и навыки комбинаторного вычисления и нахождения вероятностей, выборкой и т.д.
    11. Операционные системы. Знайте о процессах, нитях (threads) и проблемах конкуренции. Знайте о замках, мьютексах, семафорах и мониторах, и как они работают. Знайте о deadlock и livelock ситуациях, и как их избежать. Знайте какие ресурсы нужны процессу, ните, как работает переключение контекстов, как оно осуществляется на базе операционной системы и железа. Знайте о расписаниях. И так как мир движется в сторону много-ядерности, узнайте об это как можно больше.
    12. для информации о Системном Дизайне


    В следующей части мы поговорим о конкретных задачах и их реализациях на Си, Си++ и Питоне.
    05.02.2012 21:59+0400