Карьера программиста. 6-е издание
Очередное собеседование обернулось разочарованием… в очередной раз. Никто из десяти кандидатов не получил работу. Может быть, «экзаменаторы» были слишком строги?
Увы, для поступления на работу в ведущую IT-компанию академического образования недостаточно. Учебники — это замечательно, но они не помогут вам пройти собеседование, для этого нужно готовиться на реальных вопросах. Нужно решать реальные задачи и изучать встречающиеся закономерности. Главное — разработка новых алгоритмов, а не запоминание существующих задач.
«Карьера программиста» основана на опыте практического участия автора во множестве собеседований, проводимых лучшими компаниями. Это квинтэссенция сотен интервью со множеством кандидатов, результат ответов на тысячи вопросов, задаваемых кандидатами и интервьюерами в ведущих мировых корпорациях. Из тысяч возможных задач и вопросов в книгу были отобраны 189 наиболее интересных и значимых.
Шестое издание этого мирового бестселлера поможет вам наилучшим образом подготовиться к собеседованию при приеме на работу программистом или руководителем в крупную IT-организацию или перспективный стартап. Основную часть книги составляют ответы на технические вопросы и задания, которые обычно получают соискатели на собеседовании в таких компаниях, как Google, Microsoft, Apple, Amazon и других. Рассмотрены типичные ошибки, а также эффективные методики подготовки к собеседованию. Используя материал этой книги, вы с легкостью подготовитесь к устройству на работу в Google, Microsoft или любую другую ведущую IT-компанию.
Предисловие...........................................................................................11
Введение.................................................................................................12
Что-то пошло не так.......................................................................................................12
Мой подход........................................................................................................................13
Моя страсть.......................................................................................................................13
Часть I. Процесс собеседования............................................................14
Почему?...............................................................................................................................15
Как выбираются вопросы.............................................................................................17
Часто задаваемые вопросы...........................................................................................18
Часть II. За кулисами.............................................................................19
Microsoft..............................................................................................................................20
Amazon.................................................................................................................................21
Google...................................................................................................................................22
Apple.....................................................................................................................................23
Facebook..............................................................................................................................24
Palantir.................................................................................................................................25
Часть III. Нестандартные случаи..........................................................27
Профессионал...................................................................................................................27
Тестеры и SDET...............................................................................................................27
Менеджеры программ и менеджеры продукта......................................................28
Ведущие разработчики и менеджеры.......................................................................30
Стартапы.............................................................................................................................31
Для интервьюеров...........................................................................................................32
Часть IV. Перед собеседованием...........................................................37
Получаем «правильный» опыт...................................................................................37
Идеальное резюме...........................................................................................................38
Часть V. Подготовка к поведенческим вопросам.................................41
Поведенческие вопросы................................................................................................41
Ответы на поведенческие вопросы............................................................................43
Часть VI. «О» большое...........................................................................47
Аналогия.............................................................................................................................47
Временная сложность....................................................................................................47
Пространственная сложность.....................................................................................49
Константы..........................................................................................................................50
Исключение второстепенных факторов..................................................................51
Составные алгоритмы: сложение и умножение....................................................52
Амортизированное время.............................................................................................52
Сложность Log N.............................................................................................................53
Сложность рекурсивных алгоритмов.......................................................................54
Часть VII. Технические вопросы...........................................................56
Как организовать подготовку......................................................................................56
Что нужно знать...............................................................................................................56
Процесс решения задачи...............................................................................................58
Метод оптимизации 1: поиск BUD...........................................................................63
Метод оптимизации 2: интуитивный подход........................................................66
Метод оптимизации 3: упрощение и обобщение..................................................66
Метод оптимизации 4: базовый случай и расширение.......................................67
Метод оптимизации 5: мозговой штурм структур данных...............................67
Неправильные ответы....................................................................................................68
Если вы уже знаете ответ..............................................................................................69
«Идеальный» язык для собеседований....................................................................69
Как выглядит хороший код..........................................................................................70
Не сдавайтесь!...................................................................................................................71
Часть VIII. После собеседования..........................................................72
Реакция на предложение и на отказ..........................................................................72
Предложение работы......................................................................................................73
Переговоры........................................................................................................................75
На работе............................................................................................................................76
Часть IX. Вопросы собеседования.........................................................78
1. Массивы и строки......................................................................................79
Хеш-таблицы.....................................................................................................................79
ArrayList и динамические массивы...........................................................................80
StringBuilder......................................................................................................................81
Вопросы собеседования................................................................................................82
2. Связные списки.........................................................................................84
Создание связного списка............................................................................................84
Удаление узла из односвязного списка....................................................................85
Метод бегунка...................................................................................................................85
Рекурсия и связные списки.........................................................................................86
Вопросы собеседования................................................................................................86
3. Стеки и очереди........................................................................................88
Реализация стека.............................................................................................................88
Реализация очереди........................................................................................................89
Вопросы собеседования................................................................................................90
4. Деревья и графы.......................................................................................92
Разновидности деревьев................................................................................................92
Бинарные деревья и бинарные деревья поиска....................................................93
Обход бинарного дерева................................................................................................95
Бинарные кучи (min-кучи и max-кучи)...................................................................96
Нагруженные (префиксные) деревья.......................................................................97
Графы...................................................................................................................................98
Список смежности..........................................................................................................98
Поиск в графе..................................................................................................................100
Вопросы интервью........................................................................................................102
5. Операции с битами...................................................................................105
Расчеты на бумаге..........................................................................................................105
Биты: трюки и факты...................................................................................................106
Поразрядное дополнение и отрицательные числа.............................................106
Арифметический и логический сдвиг....................................................................106
Основные операции: получение и установка бита.............................................107
Вопросы собеседования..............................................................................................109
6. Головоломки.............................................................................................111
Простые числа................................................................................................................111
Вероятность.....................................................................................................................113
Начинайте говорить......................................................................................................115
Правила и шаблоны......................................................................................................115
Балансировка худшего случая..................................................................................116
Алгоритмический подход...........................................................................................117
Вопросы собеседования..............................................................................................117
7. Объектно-ориентированное проектирование............................................120
Как подходить к решению заданий.........................................................................120
Паттерны проектирования.........................................................................................121
Вопросы собеседования..............................................................................................122
8. Рекурсия и динамическое программирование...........................................125
С чего начать...................................................................................................................125
Решения рекурсивные и итеративные...................................................................126
Динамическое программирование и мемоизация..............................................126
Вопросы собеседования..............................................................................................130
9. Масштабируемость и проектирование систем...........................................133
Работа с вопросами.......................................................................................................133
Проектирование: шаг за шагом.................................................................................134
Масштабируемые алгоритмы: шаг за шагом........................................................136
Ключевые концепции...................................................................................................137
Дополнительные факторы..........................................................................................140
Идеальных систем не бывает.....................................................................................140
Пример: найдите все документы, содержащие список слов...........................141
Вопросы собеседования..............................................................................................143
10. Сортировка и поиск.................................................................................145
Распространенные алгоритмы сортировки..........................................................145
Алгоритмы поиска.........................................................................................................148
Вопросы собеседования..............................................................................................149
11. Тестирование..........................................................................................152
Чего ожидает интервьюер...........................................................................................152
Тестирование реального объекта..............................................................................153
Тестирование программного обеспечения............................................................154
Тестирование функций................................................................................................156
Поиск и устранение неисправностей......................................................................157
Вопросы собеседования..............................................................................................158
12. C и C++..................................................................................................159
Классы и наследование................................................................................................159
Конструкторы и деструкторы...................................................................................160
Виртуальные функции................................................................................................160
Виртуальный деструктор............................................................................................161
Значения по умолчанию.............................................................................................162
Перегрузка операторов................................................................................................163
Указатели и ссылки.......................................................................................................163
Шаблоны..........................................................................................................................164
Вопросы собеседования..............................................................................................165
13. Java........................................................................................................167
Подход к изучению.......................................................................................................167
Перегрузка vs переопределение...............................................................................167
Java Collection Framework..........................................................................................168
Вопросы собеседования..............................................................................................169
14. Базы данных...........................................................................................171
Синтаксис SQL и его варианты................................................................................171
Денормализованные и нормализованные базы данных..................................171
Команды SQL..................................................................................................................172
Проектирование небольшой базы данных............................................................174
Проектирование больших баз данных...................................................................175
Вопросы собеседования..............................................................................................175
15. Потоки и блокировки..............................................................................177
Потоки в Java..................................................................................................................177
Синхронизация и блокировки..................................................................................179
Взаимные блокировки и их предотвращение......................................................182
Вопросы собеседования..............................................................................................183
16. Задачи умеренной сложности.................................................................185
17. Сложные задачи......................................................................................190
Часть X. Решения..................................................................................196
1. Массивы и строки.....................................................................................197
2. Связные списки........................................................................................214
3. Стеки и очереди.......................................................................................234
4. Деревья и графы......................................................................................248
5. Операции с битами...................................................................................286
6. Головоломки.............................................................................................299
7. Объектно-ориентированное проектирование............................................317
8. Рекурсия и динамическое программирование...........................................355
9. Масштабируемость и проектирование систем...........................................387
10. Сортировка и поиск.................................................................................415
11. Тестирование..........................................................................................437
12. С и C++..................................................................................................443
13. Java........................................................................................................456
14. Базы данных...........................................................................................465
15. Потоки и блокировки..............................................................................472
16. Задачи умеренной сложности.................................................................488
17. Сложные задачи......................................................................................560
Часть XI. Дополнительные материалы...............................................665
Полезные формулы.......................................................................................................666
Топологическая сортировка.......................................................................................668
Алгоритм Дейкстры......................................................................................................669
Разрешение коллизий в хеш-таблице.....................................................................672
Поиск подстроки по алгоритму Рабина — Карпа...............................................673
АВЛ-деревья....................................................................................................................674
Красно-черные деревья...............................................................................................676
MapReduce.......................................................................................................................680
Дополнительные материалы.....................................................................................681
Часть XII. Библиотека кода.................................................................683
HashMapList<T, E>......................................................................................................683
TreeNode (бинарное дерево поиска).......................................................................684
LinkedListNode (связный список)...........................................................................685
Trie и TrieNode................................................................................................................686
Часть XIII. Подсказки
(скачайте с сайта издательства www.piter.com) ..........689
1. Структуры данных...................................................690
2. Концепции и алгоритмы...........................................699
3. Вопросы, основанные на знаниях.............................713
4. Дополнительные задачи..........................................716
Изучаем Python, том 1, 5-е издание3 280 ₽
Java. Полное руководство, 10-е издание4 430 ₽
Анализ ценных бумаг. 3-е издание5 690 ₽