Карьера программиста

Книга «Карьера программиста» основана на опыте практического участия автора во множестве собеседований, проводимых лучшими компаниями. Это квинтэссенция сотен интервью со множеством кандидатов, результат ответов на тысячи вопросов, задаваемых кандидатами и интервьюерами в ведущих мировых корпорациях. Из тысяч возможных задач и вопросов в книгу были отобраны 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 .....................................................................................................683 TreeNode (бинарное дерево поиска) ......................................................................684 LinkedListNode (связный список) ..........................................................................685 Trie и TrieNode ...............................................................................................................686 Часть XIII. Подсказки (скачайте с сайтаи здательства www.piter.com).........689 1. Структуры данных................................................... 690 2. Концепции и алгоритмы.......................................... 699 3. Вопросы, основанные на знаниях............................ 713 4. Дополнительные задачи ......................................... 716