Карьера программиста: прохождение собеседования, разработка программного обеспечения, структуры данных и алгоритмы: 16+

Книга основана на опыте практического участия автора во множестве собеседований, проводимых лучшими компаниями. Это квинтэссенция сотен интервью со множеством кандидатов, результат ответов на тысячи вопросов, задаваемых кандидатами и интервьюерами в ведущих мировых корпорациях. Из тысяч возможных задач и вопросов в книгу были отобраны 189 наиболее интересных и значимых. Шестое издание этого мирового бестселлера поможет вам наилучшим образом подготовиться к собеседованию при приеме на работу программистом или руководителем в крупную IT-организацию или перспективный стартап. Основную часть книги составляют ответы на технические вопросы и задания, которые обычно получают соискатели на собеседовании в таких компаниях, как Google, Microsoft, Apple, Amazon и других. Рассмотрены типичные ошибки, которые допускают кандидаты, а также эффективные методики подготовки к собеседованию. Используя материал этой книги, вы с легкостью подготовитесь к устройству на работу в Google, Microsoft или любую другую ведущую IT-компанию. Оглавление Предисловие Введение Что-то пошло не так Мой подход Моя страсть От издательства Часть I. Процесс собеседования Почему? Как выбираются вопросы Все относительно Часто задаваемые вопросы После собеседования мне ничего не сказали. Это отказ? Могу ли попытаться еще раз, если мне отказали? Часть II. За кулисами Microsoft Amazon Google Apple Facebook Palantir Часть III. Нестандартные случаи Профессионал Тестеры и SDET Совет Менеджеры программ и менеджеры продукта Ведущие разработчики и менеджеры Стартапы Процесс подачи заявления Виза разрешение на работу Резюме Процесс собеседования Для интервьюеров Часть IV. Перед собеседованием Получаем «правильный» опыт Идеальное резюме Правильный размер Трудовой стаж Проекты Языки программирования программные продукты Часть V. Подготовка к поведенческим вопросам Поведенческие вопросы Как подготовиться Ваши слабые места Какие вопросы нужно задавать интервьюеру Знание технических проектов Ответы на поведенческие вопросы Часть VI. «О» большое Аналогия Временная сложность Лучший, худший ожидаемый случай Пространственная сложность Константы Исключение второстепенных факторов Составные алгоритмы: сложение и умножение Амортизированное время Сложность Log N Сложность рекурсивных алгоритмов Часть VII. Технические вопросы Как организовать подготовку Что нужно знать Таблица степеней двойки Процесс решения задачи Чего ожидать 1. Внимательно слушайте Схема решения задачи 2. Представьте пример 3. Опишите решение методом «грубой силы» 4. Переходите оптимизации 5. Проведите пошаговый разбор 6. Напишите код 7. Переходите тестированию Метод оптимизации 1: поиск BUD «Узкие места» Лишняя работа Повторяющаяся работа Метод оптимизации 2: интуитивный подход Метод оптимизации 3: упрощение и обобщение Метод оптимизации 4: базовый случай и расширение Метод оптимизации 5: мозговой штурм структур данных Неправильные ответы Если вы уже знаете ответ «Идеальный» язык для собеседований Как выглядит хороший код Не сдавайтесь! Часть VIII. После собеседования Реакция на предложение и на отказ Предложение работы Переговоры На работе Часть IX. Вопросы собеседования 1. Массивы и строки Хеш-таблицы ArrayList и динамические массивы Почему амортизированное время вставки равно O(1)? StringBuilder Вопросы собеседования 2. Связные списки Создание связного списка Удаление узла из односвязного списка Метод бегунка Рекурсия и связные списки Вопросы собеседования 3. Стеки и очереди Реализация стека Реализация очереди Вопросы собеседования 4. Деревья и графы Разновидности деревьев Бинарные деревья и бинарные деревья поиска Сбалансированные несбалансированные деревья Законченные бинарные деревья Полные бинарные деревья Идеальные бинарные деревья Обход бинарного дерева Бинарные кучи (min-кучи и max-кучи) Вставка Извлечение минимума Нагруженные (префиксные) деревья Графы Список смежности Матрицы смежности Поиск в графе Поиск глубину Поиск ширину Двунаправленный поиск Вопросы интервью 5. Операции с битами Расчеты на бумаге Биты: трюки и факты Поразрядное дополнение и отрицательные числа Арифметический и логический сдвиг Основные операции: получение и установка бита Извлечение бита Установка бита Сброс бита Обновление бита Вопросы собеседования 6. Головоломки Простые числа Делимость Проверка на простоту Генерирование списка простых чисел: решето Эратосфена Вероятность Вероятность события A B Вероятность A или B Независимость Взаимоисключающие события Начинайте говорить Правила и шаблоны Балансировка худшего случая Алгоритмический подход Вопросы собеседования 7. Объектно-ориентированное проектирование Как подходить к решению заданий Шаг 1. Избавьтесь от неоднозначностей Шаг 2. Определите основные объекты Шаг 3. Проанализируйте связи Шаг 4. Исследуйте действия Паттерны проектирования Одиночка Фабричный метод Вопросы собеседования 8. Рекурсия и динамическое программирование С чего начать Решения рекурсивные и итеративные Динамическое программирование и мемоизация Числа Фибоначчи Рекурсия Нисходящее динамическое программирование (или мемоизация) Восходящее динамическое программирование Вопросы собеседования 9. Масштабируемость и проектирование систем Работа с вопросами Проектирование: шаг за шагом Шаг 1. Определите масштаб задачи Шаг 2. Делайте разумные предположения Шаг 3. Нарисуйте главные компоненты Шаг 4. Выявление ключевых проблем Шаг 5. Изменение проекта учетом ключевых проблем Масштабируемые алгоритмы: шаг за шагом Шаг 1. Задайте вопросы Шаг 2. Абстрагируйтесь от реальности Шаг 3. Вернитесь реальности Шаг 4. Решите проблемы Ключевые концепции Горизонтальное вертикальное масштабирование Распределение нагрузки Денормализация баз данных NoSQL Сегментация баз данных Кэширование Асинхронная обработка очереди Сетевые метрики MapReduce Дополнительные факторы Идеальных систем не бывает Пример: найдите все документы, содержащие список слов Вопросы собеседования 10. Сортировка и поиск Распространенные алгоритмы сортировки Алгоритмы поиска Вопросы собеседования 11. Тестирование Чего ожидает интервьюер Тестирование реального объекта Тестирование программного обеспечения Тестирование функций Поиск и устранение неисправностей Вопросы собеседования 12. C и C++ Классы и наследование Конструкторы и деструкторы Виртуальные функции Виртуальный деструктор Значения по умолчанию Перегрузка операторов Указатели и ссылки Ссылки Вычисления указателями Шаблоны Вопросы собеседования 13. Java Подход к изучению Перегрузка vs переопределение Java Collection Framework Вопросы собеседования 14. Базы данных Синтаксис SQL и его варианты Денормализованные и нормализованные базы данных Команды SQL Запрос 1. Регистрация студента Запрос 2. азмер аудитории Проектирование небольшой базы данных Проектирование больших баз данных Вопросы собеседования 15. Потоки и блокировки Потоки в Java Реализация интерфейса Runnable Расширение класса Thread Расширение класса Thread реализация Runnable-интерфейса Синхронизация и блокировки Синхронизация методов Синхронизованные блоки кода Блокировки Взаимные блокировки и их предотвращение Вопросы собеседования 16. Задачи умеренной сложности 17. Сложные задачи Часть X. Решения 1. Массивы и строки 2. Связные списки 3. Стеки и очереди 4. Деревья и графы 5. Операции с битами 6. Головоломки 7. Объектно-ориентированное проектирование 8. Рекурсия и динамическое программирование 9. Масштабируемость и проектирование систем 10. Сортировка и поиск 11. Тестирование 12. C и C++ 13. Java 14. Базы данных 15. Потоки и блокировки 16. Задачи умеренной сложности 17. Сложные задачи Часть XI. Дополнительные материалы Полезные формулы Сумма целых чисел от до N Сумма степеней 2 Основания логарифмов Перестановки Сочетания Доказательство методом индукции Топологическая сортировка Алгоритм Дейкстры Приоритетная очередь время выполнения Разрешение коллизий в хеш-таблице Поиск подстроки по алгоритму Рабина — Карпа АВЛ-деревья Красно-черные деревья MapReduce Дополнительные материалы Часть XII. Библиотека кода HashMapList TreeNode (бинарное дерево поиска) LinkedListNode (связный список) Trie и TrieNode Часть XIII. Подсказки 1. Структуры данных 2. Концепции и алгоритмы 3. Вопросы, основанные на знаниях 4. Дополнительные задачи График подготовки собеседованию Now In The 6th Edition, The Book Gives You The Interview Preparation You Need To Get The Top Software Developer Jobs. This Is A Deeply Technical Book And Focuses On The Software Engineering Skills To Ace Your Interview. The Book Includes 189 Programming Interview Questions And Answers, As Well As Other Advice. 1. The Interview Process. Why? -- How Questions Are Selected -- Timeline And Preparation Map -- It's All Relative -- Frequently Asked Questions -- 2. Behind The Scenes. The Microsoft Interview -- The Amazon Interview -- The Google Interview -- The Apple Interview -- The Facebook Interview -- The Palantir Interview -- 3. Special Situations. Experienced Candidates -- Testers And Sdets -- Product (and Program) Managment --dev Lead And Managers -- Start-ups -- Acquisitions And Acquihires -- For Interviewers -- 4. Before The Interview. Getting The Right Experience -- Writing A Great Resume -- Preparation Map -- 5. Behavioral Questions. Interview Preparation Grid -- Know Your Technical Projects -- Responding To Behavioral Questions -- So, Tell Me About Yourself -- 6. Big O. An Analogy -- Time Complexity -- Space Complexity -- Drop The Constraints -- Drop The Non-dominant Terms -- Multi-part Algorithms: Add Vs. Multiply -- Amortized Time -- Log N Runtimes -- Recursive Runtimes --^ Examples And Exercises -- 7. Technical Questions. How To Prepare -- What You Need To Know -- Walking Through A Problem -- Optimize & Solve Technique # 1: Look For Bud -- Optimize & Solve Technique #2: Diy (do It Yourself) -- Optimize & Solve Technique #3: Simplify And Generalize -- Optimize & Solve Technique #4: Base Case And Build -- Optimize & Solve Technique #5: Data Structure Brainstorm -- Best Conceivable Runtime (bcr) -- Handling Incorrect Answers -- When You've Heard A Question Before -- The 'perfect' Language For Interviews -- What Good Coding Looks Like -- Don't Give Up! -- 8. The Offer And Beyond. Handling Offers And Rejection -- Evaluating The Offer -- Negotiation -- On The Job -- 9. Interview Questions. Data Structures: Arrays And Strings ; Linked Lists ; Stacks And Queues ; Trees And Graphs --^ Concepts And Algorithms. Bit Manipulation ; Math And Logic Puzzles ; Object-oriented Design ; Recursion And Dynamic Programming ; System Design And Scalability ; Sorting And Searching ; Testing -- Knowledge Based. C And C++ ; Java ; Databases ; Threads And Locks ; Additional Review Problems. Moderate ; Hard -- 10. Solutions. Data Structures -- Concepts And Algorithms -- Knowledge Based -- Additional Review Problems -- 11. Advanced Topics. Useful Math -- Topological Sort -- Dijkstra's Algorithm -- Hash Table Collision Resolution -- Rabin-karp Substring Search -- Avl Trees -- Red-black Trees -- Mapreduce -- Additional Studying -- 12. Code Library. Hashmaplist -- Treenode (binary Search Tree) -- Linkedlistnode (linked List) -- Trie & Trienode -- 13. Hints. Hints For Data Structures -- Hints For Concepts And Algorithms -- Hints For Knowledge-based Questions -- Hints For Assorted Review Problems -- 14. About The Author. Gayle Laakmann Mcdowell, Founder And Ceo, Careercup.com. I am not a recruiter. I am a software engineer. And as such, I know what it's like to be asked to whip up brilliant algorithms on the spot and then write flawless code on a whiteboard. I've been through this as a candidate and as an interviewer. Cracking the Coding Interview, 6th Edition is here to help you through this process, teaching you what you need to know and enabling you to perform at your very best. I've coached and interviewed hundreds of software engineers. The result is this book. Learn how to uncover the hints and hidden details in a question, discover how to break down a problem into manageable chunks, develop techniques to unstick yourself when stuck, learn (or re-learn) core computer science concepts, and practice on 189 interview questions and solutions. These interview questions are real; they are not pulled out of computer science textbooks. They reflect what's truly being asked at the top companies, so that you can be as prepared as possible. WHAT'S INSIDE? - 189 programming interview questions, ranging from the basics to the trickiest algorithm problems. - A walk-through of how to derive each solution, so that you can learn how to get there yourself. - Hints on how to solve each of the 189 questions, just like what you would get in a real interview. - Five proven strategies to tackle algorithm questions, so that you can solve questions you haven't seen. - Extensive coverage of essential topics, such as big O time, data structures, and core algorithms. - A behind the scenes look at how top companies like Google and Facebook hire developers. - Techniques to prepare for and ace the soft side of the interview: behavioral questions. - For interviewers and companies: details on what makes a good interview question and hiring process.