Книга «Карьера программиста» основана на опыте практического участия автора во множестве собеседований, проводимых лучшими компаниями.
Это квинтэссенция сотен интервью со множеством кандидатов, результат ответов на тысячи вопросов, задаваемых кандидатами и интервьюерами в ведущих мировых корпорациях.
Из тысяч возможных задач и вопросов в книгу были отобраны 189 наиболее интересных и значимых.
Шестое издание этого мирового бестселлера поможет вам наилучшим образом подготовиться к собеседованию при приеме на работу программистом или руководителем в крупную ITорганизацию или перспективный стартап.
Основную часть книги составляют ответы на технические вопросы и задания, которые обычно получают соискатели на собеседовании в таких компаниях, как Google, Microsoft, Apple, Amazon и других.
Рассмотрены типичные ошибки, которые допускают кандидаты, а также эффективные методики подготовки к собеседованию.
Используя материал этой книги, вы с легкостью подготовитесь к устройству на работу в Google, Microsoft или любую другую ведущую ITкомпанию.
Author(s): Макдауэлл Г. Л. (McDowell G.L.)
Series: Библиотека программиста
Edition: 6
Publisher: Питер
Year: 2016
Language: Russian
Pages: 734
Tags: Языки программирования; Программирование
Предисловие .......................................................................................... 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 .....................................................................................................683
TreeNode (бинарное дерево поиска) ......................................................................684
LinkedListNode (связный список) ..........................................................................685
Trie и TrieNode ...............................................................................................................686
Часть XIII. Подсказки
(скачайте с сайтаи здательства www.piter.com).........689
1. Структуры данных................................................... 690
2. Концепции и алгоритмы.......................................... 699
3. Вопросы, основанные на знаниях............................ 713
4. Дополнительные задачи ......................................... 716
