Skip to content

Latest commit

 

History

History
2032 lines (1714 loc) · 199 KB

README-ru.md

File metadata and controls

2032 lines (1714 loc) · 199 KB
Raw

Google Interview University

Оригинальная версия: Английский

Станьте спонсором и поддержите Coding Interview University!

Особые благодарности:

OSS Capital
Основанная в 2018, OSS Capital - первая и единственная венчурная платформа, ориентированная
исключительно для поддержки основателей стартапов на ранней стадии COSS (commercial open source - коммерческий открытый источник).


Gitpod

Среды разработки, созданные для облачных сервисов

Изначально интегрированный с GitLab, GitHub и Bitbucket, Gitpod автоматически, продолжительно и предварительно собирает среды разработки всех ветвей (branches). В результате члены команды могут мгновенно приступить к написанию кода с новыми средами разработки для каждой новой задачи - независимо от того, создаете ли вы новую функцию (feature), хотите исправить ошибку или работаете над проверкой кода (code review).

Для кого это?

Это мой учебный план, рассчитанный на несколько месяцев для веб-разработчиков, не имеющих образования в Computer Science (CS) и планирующих работать инженерами-программистами (software engineer) в компании Google.

Кодирование на доске - из телесериала канала HBO Кремниевая Долина

За основу учебного плана я взял список вопросов Google's coaching notes и значительно расширил его. Тут вы найдёте много полезных вещей, которые необходимо знать. Дополнительные вопросы я добавил в конец списка: их могут задавать на интервью, a также они могут быть полезны в решении повседневных задач. Некоторые пункты я взял из поста Стива Йеги (Steve Yegge) "Получить работу в Google", а некоторые слово в слово соответствуют вопросам, разбираемых Google в их постах о подготовке.

Я сократил тот объем знаний, который необходим, по сравнению с рекомендациями Йеги. Я изменил требования Йеги исходя из той информации, которую мне предоставил мой знакомый из Google. Это важно для тех, кто сейчас еще новички в разработке программного обеспечения или являются веб-разработчиками и планируют стать инженерами-программистами (это та профессия где требуются знания в области CS). Если вы опытный разработчик, ожидайте что собеседование будет сложным. Подробнее.

Если вы обладаете многолетним опытом разработки ПО, помните, что Google разделяет понятия инженер-программист и разработчик ПО/веб-разработчик. Первое требует знаний в области CS.

Если вы хотите быть инженерами обеспечивающими надежность ПО или системными инженерами, то уделите внимание вопросам из опционального списка (разделы Сеть, Безопасность).

Содержание

---------------- Все что ниже - опционально ----------------

Чем это полезно?

Я следую этому плану, готовясь к собеседованию в Google. Я разрабатываю веб-приложения, сервисы и запускаю стартапы с 1997 года. У меня есть степень по экономике, но нет по CS. На данный момент у меня очень успешная карьера, но я хочу работать в Google. Я хочу работать с большими системами и понять принципы их работы, изучить эффективность алгоритмов и различные структуры данных, узнать, как работают низкоуровневые языки программирования. Если ты не знаешь что-то из перечисленного, Google не возьмёт тебя на работу.

Когда я начал этот проект, я ничего не знал о стеке, куче, Big-O, деревья и способах обхода графа. Если бы мне нужно было писать код для сортировки, это было бы не очень хорошо. Структуры данных, которые я использовал, были частью языка, и я не знал, как они на самом деле работали. Мне никогда не приходилось управлять памятью, если процесс, который я запускал, сообщал об ошибке "out of memory", я искал способ как ее обойти. Я использовал в своей работе несколько многомерных массивов и тысячи ассоциативных, но никогда не создавал структуру данных "с нуля".

Но после выполнения этого учебного плана я поверил, что Google меня наймет. Это длинный путь. Я потрачу на это месяцы. Если вы уже знакомы с большинством тем, то потратите намного меньше времени.

Как пользоваться

Ниже описан способ использования, вы должны выполнить пункты в описанном порядке.

Я использую разметку Github, включающую список задач для оценки прогресса.

  • Создай новую ветку и тогда ты сможешь оставлять отметки у элементов списка, просто добавляя x внутрь скобок: [x]

     Скопируй репозиторий и выполни команды перечисленные ниже

git checkout -b progress

git remote add jwasham https://github.com/jwasham/google-interview-university

git fetch --all

Mark all boxes with X after you completed your changes

git add .

git commit -m "Marked x"

git rebase jwasham/main

git push --force

Подробнее о разметке на Github

Получил ли я работу?

Пока я ожидаю своей очереди. Надеюсь интервью будет скоро.

Thanks for the referral, JP.

Двигайся вместе со мной

Моя история: Почему я готовился в течении 8 месяцев для собеседования в Google

Я ещё на пути к цели. Двигаемся вперёд:

Не переживайте о том, что вы недостаточно умны

О Google

О видео ресурсах

Некоторые видео доступно в том случае, если вы являетесь слушателями курсов Coursera, EdX или Lynda.com Их называют MOOCs. Некоторые курсы не имеют круглогодичного доступа и вам нужно подождать несколько месяцев, прежде чем получите к ним доступ. Курсы на Lynda.com платные.

Я был бы вам благодарен за помощь в добавлении бесплатных, всегда доступных публичных ресурсов, таких 
как видео с YouTube сопровождающих онлайн курсы. Мне нравится использовать университетские лекции.

Процесс собеседования & Основное в подготовке к интервью

Выберите один язык для собеседования

Я написал небольшую статью об этом: Важно: Выберите один язык для собеседования в Google

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

  • C++
  • Java
  • Python

Также подойдут:

  • JavaScript
  • Ruby

Вы должны хорошо знать выбранный язык и уметь комфортно писать на нём программы.

Подробнее о выборе:

Ресурсы по языкам программирования вы можете найти тут

Вы найдете кое-что по С, С++ и Python ниже, потому что я еще в процессе обучения.

Список книг

Это краткий список того, чем я пользовался. Он сокращен для того, чтобы сэкономить ваше время.

Подготовка к собеседованию

Если у вас есть много свободного времени:

Архитектура компьютера

Если мало времени:

  • Писать отличный код: Том 1: Понимание компьютера
    • Книга была опубликована в 2004 и отчасти она устарела, но благодаря ей вы быстро поймете как устроены компьютеры.
    • Автор придумал HLA, поэтому скептически отнеситесь к примерам и упоминаниям HLA. Широко не используется, но содержит ряд примеров, демонстрирующих assembler.
    • Чтение следующих глав не займет много времени и даст хорошую основу:
      • Глава 2 - Представление в числовой форме
      • Глава 3 - Двоичная арифметика и битовые операции
      • Глава 4 - Представление числа с плавающей точкой
      • Глава 5 - Представление символа
      • Глава 6 - Организация памяти и доступа
      • Глава 7 - Составные типы данных и объекты в памяти
      • Глава 9 - Архитектура CPU
      • Глава 10 - Набор инструкций
      • Глава 11 - Архитектура и организация памяти

Если вы располагаете свободным временем (я хочу купить эту книгу):

По языкам программирования

Вам необходимо выбрать один язык для интервью (смотри выше). Здесь вы найдете мои рекомендации по языкам. У меня нет информации по всем языкам, но если есть у вас - добро пожаловать.

Если вы читали одну из них, то у вас есть достаточно знаний по алгоритмам и структурам данных и вы можете приступить к решению задач по программированию. Вы можете пропустить все видео лекции в этом разделе, если не хотите повторить темы.

Дополнительные ресурсы по языкам программирования здесь

C++

Я не читал обе, но они весьма полезны и написаны Седжвиком (Sedgewick). Он отличный автор.

Если вы можете порекомендовать литературу по C++, которая лучше, сообщите мне об этом. Я ищу лучшие книги.

Java

или:

  • Структуры данных и алгоритмы на Java
    • авторы Goodrich, Tamassia, Goldwasser
    • используется в Беркли США как опциональный учебник по введению в CS
    • смотрите мой отчет по книги по Python ниже. Эта книга содержит те же темы.

Python

Опциональные книги

**Некоторые рекомендуют эти книги, но я думаю это перебор, если только вы не инженер-программист с большим опытом работы и не ожидаете более сложного собеседования.

  • Руководство по разработке алгоритмов (Skiena)

    • Как обзор и описание проблем

    • Некоторые алгоритмы вряд ли попадутся вам на собеседовании.

    • Эта книга состоит из 2-х частей:

      • классный учебник по структурам данных и алгоритмам
        • преимущества:
          • отличный учебник, содержащий обзор существующих алгоритмов
          • автор описывает реальный опыт решения задач как академических, так и промышленных
          • примеры кода написаны на C
        • недостатки:
          • местами изложение может быть неочевидным и непонятным как в CLRS (Cormen, Leiserson, Rivest, Stein), некоторые темы лучше описаны в CLRS
          • главы 7, 8, 9 сложно понять, некоторые вещи плохо разъяснены или требуют больших знаний чем есть у меня
          • не поймите меня неправильно: Мне нравится Skiena, его стиль и манера изложения, но я не могу стать физически Stony Brook.
      • каталог алгоритмов:
        • это реальная причина, почему следует купить эту книгу.
        • о том, как дойти до этой части. Обновлю, когда изучу этот раздел.

    • Цитата Йеги: "Больше чем какая-либо другая книга, эта помогла мне понять насколько банальны задачи на графы - они должны быть в инструментарии каждого программиста. Книга так же включает в себя разбор базовых структур данных и алгоритмов сортировки, что является приятным бонусом. Но важнейшей частью стала вторая часть книги, которая написана как энциклопедия, описывающая большое количество различных алгоритмических задач и способов их решения без лишних деталей. Почти каждая страница-описание содержит изображение, облегчающее запоминание. Это полезный способ, позволяющий запомнить и в последствии идентифицировать сотни типов задач."

    • Можете ее арендовать

    • Half.com - отличный ресурс, где можно заказать книги по выгодным ценам.

    • Ответы:

    • Опечатки

  • Введение в алгоритмы

    • Важно: Чтение этой книги будет полезно только для повторения алгоритмов и структур данных. Она не научит вас программировать.
    • Цитата Йеги: "Но если вы хотите идти на собеседование, отложите его пока не изучите эту книгу."
    • Half.com - отличный ресурс, где можно заказать книги по выгодным ценам.
    • известная как CLR, иногда CLRS, потому что Stein опоздал на игру

  • Жемчужины программирования

    • В первых двух главах представлены решения задач программирования (в некоторых из них используются устаревшие типы данных), но это только введение. Это руководство по разработке программ и архитектуре, такое же как Code Complete, но более краткое.

  • "Алгоритмы и программирование: Проблемы и решения" автор Shen

    • Отличная книга, но после разбора нескольких задач написанных на Pascal я разочаровался в его синтаксисе.
    • Лучше провести время решая задачи по программированию из других книг или онлайн ресурсов.

Перед тем как вы начнете

Я создавал эту учебную программу на протяжении нескольких месяцев своими руками.

Ниже я описал некоторые ошибки, которые я совершил. Это поможет вам их избежать.

1. Вы не сможете сразу запомнить все

Я смотрел часами видео делая заметки, но спустя несколько месяцев многое из этого я не помнил. После чего потратил 3 дня разбираясь в своих заметках и делая карточки-напоминания (flashcards) для того, чтобы потом можно было повторить пройденный материал.

Прочитайте пожалуйста эту статью, что бы не совершать моих ошибок:

Как сохранить знания в CS

2. Используйте карточки-напоминания

Для решения этой проблемы я сделал небольшой сайт, на котором можно добавлять карточки двух типов: общие и с кодом. Каждая карта имеет разный формат.

Я сделал мобильную версию сайта и могу читать карточки на мобильном телефоне или планшете.

Сделай свой собственный бесплатно:

Заметка о карточках: в первый раз вы сразу вспомните ответ, но не помечайте эту карточку как изученную. Нужно просмотреть много раз карточку и ответить правильно прежде чем вы действительно ее запомните. Повторение позволяет мозгу надолго запомнить материал.

В качестве альтернативы вы можете использовать сайт Anki, который мне рекомендовали много раз. Он использует систему повторений для того что бы помочь вам запомнить. Это ресурс user-friendly, доступен на всех платформах и имеет возможность синхронизации с облаком. На платформе iOS стоит 25$, на других бесплатный.

Моя база данных в формате Anki: https://ankiweb.net/shared/info/25173560 (спасибо @xiewenya)

3. Повторение, повторение, повторение

У меня постоянно с собой шпаргалки по ASCII, стеку OSI, Big-O нотации и другим темам. Я повторяю их когда у меня есть свободное время.

Делай перерывы от программирования на пол часа и повторяй свои карточки.

4. Фокусируйтесь

Есть много отвлекающих факторов, на которые тратится время. Сосредотачиваться и концентрироваться сложно.

То, что не охватывает этот учебный план

Это список персональных тем, взятых из заметок Google по подготовке к собеседованию. Это распространенные технологии, но они не встречаются в других ресурсах:

  • SQL
  • JavaScript
  • HTML, CSS и другие front-end технологии

План на день

Для изучения некоторых тем требуется один день, для других несколько. Некоторые нужно только изучить и не нужно программировать.

Каждый день я беру одну тему из списка ниже, смотрю видео на эту тему и программирую, используя пройденный материал:

  • C - используя структуры и функции, которые в качестве аргументов принимают указатель на структуру или что-нибудь еще.
  • C++ - без использования встроенных типов
  • C++ - используя встроенные типы, такие как std::list для связанного списка
  • Python - используя встроенные типы (для практики на Python)
  • написание тестов для проверки правильности кода, иногда просто используя выражение assert()
  • Вы можете программировать на Java или других языках, это только лишь мой выбор.

Вам не нужны все эти языки для собеседования, нужен только один один язык для собеседования.

Зачем нужно программировать на нескольких языках:

  • Практика, практика, практика пока это не надоедает мне я программирую
  • Работа в рамках установленных ограничений (выделение/освобождение памяти без помощи сборщика мусора (кроме Python))
  • Используйте встроенные типы, потому как у меня есть опыт использования встроенных инструментах в реальных проектах (нет смысла в написание своей реализации связанного списка для продакшена)

У меня может и не будет времени на все это, но я попробую.

Вы можете посмотреть на мой код тут:

Вам не нужно запоминать внутренности каждого алгоритма.

Пишите код на доске или листе бумаги, но не компьютере. Проверяйте на простых входных данных. Затем тестируйте на компьютере.

Необходимые знания

Сложность алгоритмов, Big-O, Асимптотический анализ

Структуры данных

  • Массивы

    • Реализация динамического вектора.
    • Описание:
    • Реализация вектора (изменяемый массив с автоматическим изменением размера):
      • Тренируйтесь программировать используя массивы, указатели и арифметику указателей для перехода к индексу вместо индексации.
      • выделение памяти для массива
        • можно выделить память для массива целых чисел, просто не используя его возможности
        • начиная с 16, или если начальная цифра больше, использовать степень 2 - 16, 32, 64, 128
      • size() - количество элементов
      • capacity() - количество элементов которое он может содержать
      • is_empty()
      • at(index) - возвращает элемент по индексу, изменяет размер, если индекс выходит за пределы
      • push(item)
      • insert(index, item) - вставка элемента по индексу, сдвигает значение по индексу и следующие за ним элементы вправо
      • prepend(item) - может вставить элемент выше индекса 0
      • pop() - удалить последний элемент, вернуть значение
      • delete(index) - удаляет элемент по индексу, сдвигает все следующие за ним элементы влево
      • remove(item) - ищет элементы по значению и удаляет их, даже если их несколько
      • find(item) - ищет элемент по значению и возвращает индекс первого найденного элемента, возвращает -1 если ничего не найдено
      • resize(new_capacity) // private function
        • когда массив полностью заполнен, увеличивает его размер вдвое
        • при добавлении элемента, если размер массива 1/4 от общего размера, увеличиваем на половину
    • Время
      • O(1) для операций add/remove в конце (амортизируется для размещения большего объема), index, или update
      • O(n) для insert/remove в любом месте
    • Работа с памятью
      • смежные в памяти, это помогает повысить производительность
      • необходимое пространство = (размер массива, который >= n) * размер элемента, но даже если 2n, по прежнему O(n)

  • Связные списки (Linked Lists)

    • Описание:
    • C Code (video) - не все видео целиком, только кусочки об узлах и распределении памяти.
    • Связные списки vs Массивы:
    • why you should avoid linked lists (video)
    • Ага, попался: тебе нужны знания указателей на указатели: (для тех случаев, когда ты передаешь указатель функции, которая может менять адрес, куда указывает указатель) Это страница просто для того, чтобы понять указатели на указатели. Читабельность и обслуживаемость страдает из-за искусности.
    • воплотить в жизнь (я сделал это с помощью указателя на хвост и без):
      • size() - возвращает количество элементов в листе
      • empty() - возвращет true если список пуст
      • value_at(n) - возращет значение n-го элемента, где 0 - первый элемент
      • push_front(value) - добавляет элемент в начало списка
      • pop_front() - удаляет первый и возращает его значение
      • push_back(value) - добавляет элемент в конец списка
      • pop_back() - удаляет последний и возращает его значение
      • front() - возращает значение первого элемента в списке
      • back() - возращает значение последнего элемента в списке
      • insert(index, value) - помещает значение (value) в элемент по индексу (index), при этом заменяемый элемент добавлен в список как новый элемент
      • erase(index) - удаляет узел (элемент) по данному индексу
      • value_n_from_end(n) - возращает значение n-го элемента c конца списка
      • reverse() - реверсирует весь список
      • remove_value(value) - удаляет первый элемент в списке с указанным значением (value)
    • Двусвязный список

  • Стек

  • Очередь

    • Использование очереди First-In First-Out(video)
    • Очередь (video)
    • Circular buffer/FIFO
    • Очередь с приоритетом (video)
    • Реализация с использованием связанного списка и указателя на последний элемент(tail):
      • enqueue(value) - добавляет элемент в конец очереди
      • dequeue() - возвращает значение и удаляет из очереди последний добавленный элемент(front)
      • empty()
    • Реализация с применением массива фиксированного размера:
      • enqueue(value) - добавляет элемент в конец очереди
      • dequeue() - возвращает значение и удаляет из очереди последний добавленный элемент
      • empty()
      • full()
    • Затраты:
      • плохая реализация с применением связанного списка когда элемент добавляется в начало очереди и удаляется с конца очереди за O(n), операция dequeue в таком случае будет требовать каждый раз обхода всего списка
      • enqueue: O(1) (amortized, связанный список и массив [probing])
      • dequeue: O(1) (связанный список и массив)
      • empty: O(1) (связанный список и массив)

  • Хеш-таблица

Дополнительно

Деревья

Сортировка

Если вам необходимо больше информации, смотрите секцию "Сортировка" в Дополнительные детали о некоторых разделах

Графы

Графы могут быть использованы для представления многих задач в области CS, поэтому раздел включает в себя такие темы как деревья и сортировку.

Вы найдете больше практических задач на графах в книге Стивена Скина (см. раздел книги ниже) и в книгах о прохождении интервью.

Еще больше знаний

Проектирование систем, Масштабируемость, Обработка данных

Заключительный обзор

В этом разделе вы найдете короткие видео, которые можно посмотреть достаточно быстро чтобы повторить наиболее важные моменты.
Полезно освежать свои знания чаще.

Практика: задачи по программированию

Теперь, когда вы узнали все вышерассмотренные темы по компютерным наукам, настало время попрактиковаться в решении задач по программированию.

Решение задач по программированию - это не запоминание решений.

Для чего вам нужно практиковаться в решении задач по программированию:

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

Вот пример отличного введения в методичное, коммуникативное решение задач на собеседовании. Вы так же найдете это в книгах по интервью для программистов, но это подход мне кажется однм из лучших: Схема разработки алгоритма

Мой процесс подготовки к собеседованию по программированию (Книга) Упражнения

У вас нет доски дома? Не удивительно. Я немного неормальный и у меня есть большая доска дома. Но вместо доски можно использователь и планшет для рисования из магазина художественных товаров, и практиковаться сидя на диване. Это моя "диванная доска". На фото я положил ручку чтобы иметь вы имели представление о масштабе. Если вы будете пользоваться ручкой, постоянно будет возникать желание что-то исправить и решение захламляется достаточно быстро.

моя диванная доска

Дополнительно:

Прочитайте и выполните упражнения (именно в этом порядке):

См. Список книг ниже

Упражнения по программированию

Как только вы заполнили свою голову знаниями, самое время применить их на практике. Выполняйте упражнения по программированию каждый день, чем больше тем лучше.

Сайты с упражнениями:

Возможно:

Перед собеседованием

Ваше резюме

Подумайте об этом когда подходит время собеседования

Подумайте как отвечать приблизительно на 20 распостраненных вопросов которые задают на собеседовании, подготовьте 2-3 ответа на каждый из них. Расскажите историю, а не просто сухой пересказ о том над чем вы работали.

  • Почему вы хотите получить эту работу?
  • Какая самая большая проблема которую вам приходилось решать?
  • Самые сложные задачи с которыми вам приходилось сталкиваться?
  • Лучшие/худшие дизайн решения с которыми вы сталкивались?
  • Идеи как улучшить какой-нибудь существующий продукт.
  • Вы более продуктивны как часть команды или как иднивидуальный разработчик?
  • Какие из ваших навыков или что из опыта будет наиболее ценным для данной позиции?
  • Что вам больше всего понравилось в работе над [проектом Х/в компании Х]?
  • Какие самые сложные задачи вы решали в [компании X/проекте Х]?
  • С каким самым сложным багом вам приходилось сталкиваться в [компании X/проекте Х]?
  • Чему вы научились в [компании X/проекте Х]?
  • Что бы вы могли сделать лучше работая в [компании X/проекте Х]?

Приготовьте вопросы для интервьювера

Вот, некоторые из моих (возможно, я уже знаю ответ, но хочу я услышать мнение интервьювера или точку зрения команды):
  • Сколько человек в команде?
  • Как выглядит ваш цикл разработки? Работаете ли вы по agile, спринтам или водопад?
  • Насколько часто бывают переработки и дедлайны? Или сроки достаточно гибкие?
  • Как в вашей команде принимаются решения?
  • Сколько встреч вы проводите в неделю?
  • Располагает ли ваше рабочее окружение к концентрации?
  • Над чем вы работаете?
  • Что вам в этом нравится?
  • Как в целом протекает работа?

Когда вас приняли на работу

Поздравляю!

Не прекращайте учиться.

На самом деле это не конец.

*****************************************************************************************************
*****************************************************************************************************

Все что находится ниже этого места - опционально. Это мои рекоммендации, а не от Google.
Изучая все это вы узнаете больше о компьютерных науках, и будуте лучше готовы для любой вакансии программиста.
Вы станете более всесторонне-развитым разработчиком.
*****************************************************************************************************
*****************************************************************************************************

Дополнительная литература

Дополнительная литература

--

Additional Detail on Some Subjects

I added these to reinforce some ideas already presented above, but didn't want to include them
above because it's just too much. It's easy to overdo it on a subject.
You want to get hired in this century, right?

Video Series

Sit back and enjoy. "Netflix and skill" :P

Computer Science Courses