Карьера программиста. 6-е издание

Предисловие...........................................................................................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