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

    Привет Хабр! Давно не писал. Да это и понятно. Защита диссертации, получение 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. для информации о Системном Дизайне


    В следующей части мы поговорим о конкретных задачах и их реализациях на Си, Си++ и Питоне.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 99

      +31
      В русскоязычной литературе есть часто используемые названия для задач:
      Путешествие продавца — Задача комивояжера,
      Проблема о рюкзаке — Задача о ранце.
        +5
        Точно-точно. Спасибо за подсказку, сейчас поправлюсь.
        +17
        Слабаков в google не берут.
        • UFO just landed and posted this here
            +7
            Или они набирают тех, кто сможет нормально понимать английский, нет?)
              +28
              Будет интересно, как Вы на русском будете объяснять китайцу и индусу, что вы хотите сделать со своими данными в дереве например.
              • UFO just landed and posted this here
                  0
                  А что вы будете делать с документацией?
                    +4
                    Если программист не знает английского языка, то и функции он не сможет запомнить, а только зазубрить, т.к. большинство функций несут в себе смысловое описание на английском (да и не только функций, взять те же string, array).
                      +3
                      Я бы сказал проще: если программист не знает английского языка — то он не программист.
                        0
                        А как же 1С?
                          +1
                          Программирование 1С — не программирование, а вообще фигня какая то.
                            0
                            К SAP у Вас такое же отношение?
                              0
                              ABAP?
                                0
                                Да, спасибо за уточнение
                                  0
                                  Не поймите меня неправильно, я ничего против этих систем против не имею (Вообще говорю только про 1С Бухгалтерия, ABAP не видел).
                                  Но я ни разу не видел красивого кода на 1С, обычно это просто быдлокод причем логика там минимальная. Не говоря уже о том, что сам ЯП выглядит отвратительно.

                                  А русские названия в коде, впринципе, как и транслит — это чертовски плохо. Выучить английский не настолько сложно, а код будет выглядеть намного приятней и аккуратней.
                                  За названия типа jachekaGetZnachenie или [Статусы Гос Служащих] просто убить готов.
                                  • UFO just landed and posted this here
                                      0
                                      Может быть, но по-крайней мере, англоговорящие люди не делают вставок на русском :)

                                      Мне это не нравится по двум причинам:
                                      1) Постоянное переключение раскладки.
                                      2) Постоянное щелканье в мозгу «русский, английский». Однородная информация лучше воспринимается.
                      +4
                      Уж проще нанять квалифицированного программиста (такого же уровня или лучше), но который еще и язык хорошо знает. Тем более, что это не проблема.
                        +7
                        А гуглопереводчик само собой сам появился. Из ниоткуда.
                        • UFO just landed and posted this here
                            –1
                            Как буд-то бы других причин учить английский нету. Ну это же смешно. Как вы представляете себе работу с менеджерами? Выкрутиться можно, но намного полезнее выучить язык. В жизни пригодиться.
                              +2
                              Ну русский тоже не плохо бы знать, чтобы мягкие знаки в ненужных местах не расставлять.
                                +1
                                Странно почему вы «буд-то» не заметили.
                                  0
                                  Потому что так и я изредка косячу :) Привычка: слышишь «то» — поставь дефис. Но вроде как стараюсь проверять и пресекать такие попытки моих пальцев. А вот мягкие знаки дико слух режут.
                              0
                              Когда мне пишут через переводчик, то не всегда с первого раза можно понять что именно хотел спросить человек или даже двояко. Особенно когда изначально предложение было слишком сложно или не совсем грамотно составлено.
                                +14
                                С ужасом представляю техническое задание на важном проекте, которое было написано через такой переводчик и переведено несколько раз через разные языки.

                                Напомнило старый анекдот.
                                Обычный американский фильм с обычным американским диалогом:
                                — How do you do?
                                — All right!

                                Перевод:
                                — Как ты это делаешь?
                                — Всё правой.
                                  +32
                                  актуальнее этот анекдот:

                                  Инструкция к установке ПО: Just execute the installer.
                                  Перевод: Просто казните монтажника
                                  • UFO just landed and posted this here
                                      0
                                      Кстати попробовал:
                                      How do you do?

                                      перевод:
                                      Как вы это делаете?

                                      в том то и дело что «как вы это делаете»
                                      вместо «как дела»
                                      это еще более фееричней чем «все правой»
                                      • UFO just landed and posted this here
                                          +7
                                          Your bunny wrote, упоротый ты.
                                            +3
                                            (это тролль)
                                              0
                                              ух ты, на хабре тролли не вымерли!
                                                +1
                                                Не вымрут пока их кормят.
                                  +3
                                  Вот знаете, есть у меня друг, который на одеске пытается писать через гугл транслэйт т.е. английский не знает. Так вот его не то что англоговорящие не понимают, его никто не понимает, даже он сам не может вспомнить что хотел сказать этой чудо фразой из гугл транслеэйта…
                                +1
                                Книги вы тоже гуглом переводите?
                                • UFO just landed and posted this here
                                    +1
                                    Если представить закон Мура в грубой форме, то каждых 2 года количество информации для IT-шника удваивается, при этом вы стабильно отстаёте на год лишь из-за незнания языка. Такой специалист неконкурентоспособен.

                                    И ещё интересно как вы хотите работать в США не зная английского, в магазин тоже с гугл транслейтом ходить будете? ИМХО это превращение рабочего процесса в горы лулзов.
                                    • UFO just landed and posted this here
                                        +1
                                        Здесь почти каждый месяц что-то новое появляется, да и тут тоже интересно.
                                      • UFO just landed and posted this here
                                          0
                                          (глядя на время коммента) полагаю, что ответа нет, потому что даже программисты иногда спят по ночам
                                    +2
                                    Хорошо, ты собираешься сесть или не являешься тобой?
                                  +2
                                  Мне одному кажется, что незнание английского в IT это признак профнепригодности?
                                  Потому что вся документация — на нем, родимом. А ошибок в переводной документации полно, ибо переводят ее зачастую далекие от IT люди.
                                    0
                                    На хабре удачно сказали: первым языком любого программиста должен быть английский.
                                      0
                                      а с коллегами вы, пардон, на каком языке общаться будете? ;) нет, ну правда интересно!
                                    +2
                                    Проходил собеседование в амазон, было аж 3 телефонных интервью. Вопросы очень похожи на указанные автором. И рекомендации правильные. В амазон конечно не спрашивали про продукцию гугл, но про идеи развития амазон, конечно да.
                                      +28
                                      Успехов вам в пятницу.
                                        +8
                                        Огромное спасибо!
                                        –3
                                        google…
                                          +2
                                          Да, интересно было почитать. Уверен, у Вас всё получится!
                                            –4
                                            Здорово, классно, правильно, но не подписывали ли вы какого-нибудь NDA, которое может помешать вам с чистой совестью выкладывать все об интервьюировании на Гугл?
                                            Список теории и кижки, это безусловно правильно, но вот транскрипт и задачи — это как-то чуть слишком. Не находите?
                                              +1
                                              А это разве не вещи такого же уровня, как опубликовать, скажем, список билетов для экзамена и список точных ответов на эти билеты? Автор вроде как просто огласил билеты.

                                              Или даже это может быть закрыто по NDA?
                                                +2
                                                Во-первых большинство вещей, описанных в топике — общеизвестные и причем даже Google сами дают ссылки на некоторые материалы, которые надо знать для второго собеседования по телефону.

                                                Во-вторых, NDA они подписывают после второго собеседования по телефону, когда приглашают к себе в офис.
                                                  0
                                                  Они на первых интервью ничего не подписывают, но просят обещать не распространять точную информацию о вопросах — например, все вопросы, которые были заданы.
                                                  А вот примерную информацию как тут можно и так найти на сайтах Google, но тут вместе собрано.

                                                  Им ведь нужны люди, которые могут мыслить на ходу, а не зубрить чужие ответы.
                                                    0
                                                    Ну например, для Juniper'овского экзамена JNCIA явным образом подписывается NDA о любых подробностях, не говоря уж о списках вопросов и ответов.
                                                    +1
                                                    Вопрос был обговорён. Задачи я беру из обще-доступных источников. Про интервью — меня не просили не разглашать задачи. Но как человек порядочный, я подожду чуть больше месяца перед обсуждением оных. И на самом деле, задачи действительно очень-очень общие. Что хочется обсуждать при решении задач, это не просто конкретный способ, хотя его конечно хорошо бы знать, а скорее то, на что стоит обращать внимание при кодинге. Так что даже не просто подготовка к интервью, а наработка навыков хорошего программирования.
                                                      0
                                                      Удачи на интервью.
                                                      А насчет «меня не просили не разглашать задачи», на самом деле просили. Прочитайте документы которые вам высылал рекрутер. Перед телефонным интервью не просят ничего подписать, но как раз таки просят не рассказывать вопросы.
                                                      почему? устроитесь в гугл, поймете :)
                                                      –2
                                                      Дорогие товарищи. Спасибо.
                                                      Специально для вас всех, я покажу те строки в посте, к которым хотел привлечь внимание:

                                                      Технические задачки и их решения на C/C++ и Python
                                                      Транскрипт моего реального интервью

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

                                                      Еще раз, для тех, кто читает быстро — скидывать реальные вопросы и реальный транскрипт по меньшей мере неэтично (для меня по крайней мере), ну и скорее всего, есть какое-то NDA на эту тему.
                                                      Автор, я просто прошу тебя подумать, не нарушаешь ли ты ненароком чего.
                                                      +14
                                                      0
                                                      Интересно, а на интервью они просматривают ваши поисковые запросы? :)
                                                        +3
                                                        Нет. Читайте пользовательское соглашение с гуглом.
                                                          +9
                                                          Читайте с гуглом, смотрите с гуглом, пишите с гуглом.
                                                        +9
                                                        От себя могу порекомендовать сайты:
                                                        1) www.careercup.com/page — Можно фильтровать вопросы по позиции и компаниями. Выглядит страшновато, но много полезного.

                                                        2) www.geeksforgeeks.org/ — задачки разбиты по категориям, так же есть список обновляющихся вопросов на собеседованиях, как и пункт 1 — www.geeksforgeeks.org/forum/view/company-interview

                                                        3) Книга от авторов первого сайта — «Cracking the Coding Interview: 150 Programming Questions and Solutions». Ставлю ее рядом с Programming Interviews Exposed.

                                                        4) www.glassdoor.com/ — кандидаты выкладывают свои впечатления и вопросы на собеседованиях. Менее техническое чем 1 и 2.
                                                          0
                                                          То есть бакалавриатский курс CS.
                                                            0
                                                            У кого-нибудь книги в электронном формате есть?

                                                            Весь гугл обрыл, что-то «Programming Interviews Exposed Secrets to Landing Your Next Job 2nd Edition» так и не нашел.
                                                              +3
                                                              bit.ly/yR30hW
                                                              Первая ссылка.
                                                                –10
                                                                спасибо, а без выебонов можно было?
                                                                0
                                                                На library.nu / gigapedia есть в ассортименте.
                                                                0
                                                                Достаточно базовые знания. Конечно, что-то я уже подзабыл, но практически всё, что вы перечислили, мне давали в университете. Разве что с мегабольшими объёмами данных не работали. В общем, удачи!
                                                                  0
                                                                  Похоже на егэ.

                                                                  Там тоже не учат, например, математику. А учатся отвечать на вопросы егэ по математике.
                                                                  (для школофобов напомню что егэ начали экспериментально вводить с начала нулевых)

                                                                  Хотя конечно полезно когда все в команде гарантировано знают какой-то общий стандартизированный набор понятий из области программирования.

                                                                  Наверное отбирать огромное кол-во эффективных специалистов это очень трудная работа. Интересно, каков процент непрохождения испытательного срока.
                                                                    0
                                                                    Не думаю, что после телефонного интервью вас попросят руководить созданием нового сервиса. Это скорее проверка на вшивость, чем, собственно, является егэ.
                                                                    0
                                                                    Спасибо! Мне тут тоже предлагали пособеседоваться, но я решил повременить. И не зря — теперь смогу подготовиться.
                                                                    0
                                                                    > Я хочу работать в Google!

                                                                    Почему?
                                                                      0
                                                                      Миллионы мух не могут ошибаться! =)

                                                                      А вообще, что привлекает в гугле: задачи, аналогов которым нет в других компаниях, люди, которые обладают, как техническими навыками, так и сами-по-себе разносторонне развиты, перспектива роста, как по вертикали, так и перевода между разными отделениями. Ну и из мелочей: английский, путешествия, перки, бесплатная еда :D
                                                                      +9
                                                                      «Я долго гадал, нужно ли оставлять версию текста на английском. Но боясь быть заклёванным на месте — решил перевести всё на русский.»



                                                                      «имлементирование системных рутин»

                                                                      :)
                                                                        +1
                                                                        вот такой вот хреновый я переводчик!
                                                                        +2
                                                                        давайте на хабре сделаем цикл статей по перечисленным пунктам, многое уже было в том или ином виде, а многое еще не разу не публиковалось.
                                                                          0
                                                                          Interview Anti-Loop — можете объяснить что это?
                                                                            +4
                                                                            От себя могу рассказать:
                                                                            1) Собеседование на стажёра в Microsoft
                                                                            2) Собственно, сама летняя стажировка в офисе в Редмонде
                                                                            3) Опыт собеседования в Фейсбук (пока не окончено — впереди on-site интервью в Калифорнии =))
                                                                            Интересно кому? =)
                                                                              +1
                                                                              про мелкомягких — интересно
                                                                                +2
                                                                                Конечно, интересно. И про МС, и про Фейсбук.
                                                                                Удачи на он-сайт ))
                                                                                  +1
                                                                                  Недавно интервьюировался в Google и Facebook — субъективно в Google интервью было сложнее (оба прошел).
                                                                                    0
                                                                                    Судя по Glassdoor, гугл куда более строгий. Сестра друга прошла в гугл, задания там реально сложнее.
                                                                                  0
                                                                                  А на какую именно должность собеседовали? SE, SRE? И в европейские отделения или в штаты?

                                                                                  Я летом собеседовался на SRE в европейские офисы, пообщался с ними в Дублине, но дальше наши отношения не сложились :)
                                                                                    0
                                                                                    s/SE/SWE. Ну так уж принято.
                                                                                    +1
                                                                                    Хм, мануал по устройству на работу. Замечательно.

                                                                                    Не наброса для, но меня действительно интересует: а разве нормальный программист, получивший профильное образование и любящий программирование на входе не знает всех этих вещей?

                                                                                    Ну, то есть, очень базовые штуки как темы названы, странно, что их могут не знать те, кто уже идёт на собеседование.
                                                                                      +2
                                                                                      Одно дело знать, что такие вещи есть — а другое, как их применять и где. Тем более все зависит от того же профильного образования. Если человек в жизни не видел задачу о ранце, то он точно не сможет понять как и где её применить. И понятие «нормальный пограммист» — довольно размытое понятие.
                                                                                      +2
                                                                                      Удачи на интервью! ;)
                                                                                        0
                                                                                        Спасибо!
                                                                                        0
                                                                                        На мой взгляд из O(n log n) сортировок лучше вместо mergesort'а разобраться в heapsort'е, ибо:
                                                                                        1. В отличие от quicksort'а гарантированное Θ(n log n) время.
                                                                                        2. В отличие от mergesort'а, in-place, т.е. требует O(1) дополнительной памяти.
                                                                                        3. Используется структура heap, знать которую, конечно же, нужно.

                                                                                        Ну и вообще, для саморазвития не лишним будет разобраться в сортировках, работающих за линейное время, почему такое возможно, и, возможно, методами обеспечения Θ(n log n) времени для quicksort'а (см. introsort).
                                                                                          0
                                                                                          Лучше уметь программировать merge (и не уметь heap), чем наоборот. Хотя и то, и другое, конечно, еще лучше.
                                                                                          Слияние трех упорядоченных массивов студенты на экзамене написать (на C/C++) не могут — проверено :(
                                                                                            +1
                                                                                            mergesort тоже in-place бывает :)
                                                                                              0
                                                                                              Любопытно. Надо будет изучить подробнее.
                                                                                                +1
                                                                                                алгоритм несколько упорот, вот bit.ly/t1rcBe
                                                                                                  0
                                                                                                  Спасибо. Кажется, они забыли сказать, что для сортировки групп надо использовать алгоритм, работающий за O(k) обменов групп (иначе все слияние в O(n) никак не уложится), но в целом, идея понятна. Как-нибудь попробую.
                                                                                                  Еще бы smoothsort понять :)

                                                                                          Only users with full accounts can post comments. Log in, please.