Гейл Лакман МакдауэллКарьера программиста.

Как устроиться на работу вGoogle, Microsoft или другую

ведущую IT-компанию

Текст предоставлен правообладателемhttp://www.litres.ru/pages/biblio_book/?art=8343620

Карьера программиста. Как устроиться на работу в Google,Microsoft или другую ведущую IT-компанию.: Питер; Санкт-

Петербург; 2012ISBN 978-5-459-01120-3

АннотацияПятое издание этого мирового бестселлера поможет

вам наилучшим образом подготовиться к собеседованиюпри приеме на работу программистом или руководителемв крупную IT-организацию или перспективный стартап.Основную часть книги составляют ответы на техническиевопросы и задания, которые обычно получают соискателина собеседовании в таких компаниях, как Google,Microsoft, Apple, Amazon и других. Рассмотренытипичные ошибки, которые допускают кандидаты, атакже эффективные методики поготовки к собеседованию.

Используя материал этой книги, вы с легкостьюподготовитесь к устройству на работу в Google, Microsoftили любую другую ведущую IT-компанию.

СодержаниеПредисловие 14Введение 17

Что-то не так 17Мой подход 20Моя страсть 21От издательства 22

Часть I. Процесс собеседования 23Небольшое вступление 23Как выбираются вопросы 26График и карта подготовки 29Процедура оценки 32Неправильные ответы 35Дресс-код 3710 наиболее частых ошибок 39

1. Использование компьютера 392. Игнорирование поведенческихвопросов

39

3. Отказ от псевдоинтервью 404. Попытка зазубрить ответ 405. Решение задачи «в уме» 416. Спешка 417. Грязный код 428. Отказ от проверки 42

9. Небрежное отношение кисправлению ошибок

43

10. Отказ от решения 43Часто задаваемые вопросы 45

Нужно ли мне говорить интервьюеру,что я уже знаком с вопросом?

45

Какой язык программирования следуетиспользовать?

46

После собеседования мне ничего несказали. Мне отказали?

46

Могу ли я попытаться еще раз, еслимне отказали?

47

Часть II. За кулисами 48Microsoft 50Amazon 53Google 56Apple 59Facebook 61Yahoo! 64

Часть III. Нестандартные случаи 66Кандидат-профессионал 66Тестеры и SDET 68Менеджеры программ и менеджерыпродукта

70

Стартап 76Процесс подачи заявления 76

Виза и разрешение на работу 77Резюме 77Процесс собеседования 77

Часть IV. Перед собеседованием 79Получаем «правильный» опыт 79Налаживаем связи 82

Правильный круг знакомств 82Как построить сильный круг знакомств 83

Идеальное резюме 85Правильный размер 85Трудовой стаж 86Указывайте только значимые позиции 86Проекты 87Языки программирования ипрограммные продукты

88

Часть V. Подготовка к поведенческимвопросам

90

Поведенческие вопросы 90Как подготовиться 90Ваши слабые места 92Что заставляет вас работать 93Какие вопросы нужно задаватьинтервьюеру

93

Ответы на поведенческие вопросы 96Отвечайте четко, но без высокомерия 96

Часть VI. Технические вопросы 100

Подготовка 100Как организовать подготовку 100Что нужно знать 101Таблица степеней двойки 103Нужно ли знать все опрограммировании на C++, Java илидругих языках

104

Ответы на технические вопросы 105Пять шагов к решению 106

Шаг 1. Задайте вопросы 106Шаг 2. Разработайте алгоритм 108Шаг 3. Псевдокод 109Шаг 4. Код 109Шаг 5. Проверка 110

Пять подходов к алгоритмизации 112Подход 1. Приводим пример 112Подход 2. Сопоставление с образцом 113Подход 3. Упростить и обобщить 115Подход 4. Базовый случай и сборкарешения

116

Подход 5. Мозговой штурм структурданных

118

Как выглядит хороший код 120Структуры данных 121Обоснованное многократноеиспользование кода

123

Модульность 125Гибкость и надежность 128Проверка 128

Часть VII. Жизнь после собеседования 131Реакция на предложение и на отказ 131

Сроки принятия решения 131Вы отказываетесь от работы 132Вам отказали 132

Вам сделали предложение 134Финансовый пакет 134Карьерный рост 135Стабильность компании 137Удовольствие от работы 137

Переговоры 139На работе 142

Создайте график своего карьерногороста

142

Устанавливайте прочные отношения 143Спросите себя, что вам нужно 143

Часть VIII. Вопросы собеседования 145Структуры данных. Вопросы и советы 146

1. Массивы и строки 146Хэш-таблицы 146ArrayList (динамический массив) 148StringBuffer (буфер строк) 149Вопросы интервью 150

2. Связные списки 152Создание связного списка 152Удаление узла из односвязногосписка

153

Метод бегунка 154Рекурсия и связные списки 155Вопросы собеседования 156

3. Стек и очередь 158Реализация стека 158Реализация очереди 159Вопросы собеседования 160

4. Деревья и графы 163Потенциальные ловушки 163Обход бинарного дерева 165Балансировка: красно-черные иАВЛ-деревья

165

Префиксное дерево 165Обход графа 166Вопросы собеседования 169

Концепции и алгоритмы. Вопросы исоветы

172

5. Поразрядная обработка 172Расчеты на бумаге 172Биты: трюки и факты 174Основные задачи: получение,установка, очистка и обновление

175

битаВопросы собеседования 177

6. Головоломки 179Начните говорить 180Правила и шаблоны 180Балансировка худшего случая 182Алгоритмический подход 184Вопросы собеседования 184

7. Математика и теория вероятностей 186Простые числа 186Теория вероятностей 191Обратите внимание! 196Вопросы собеседования 196

8. Объектно-ориентированноепроектирование

198

Как подготовиться к заданиям поООП

198

Разработка шаблонов 201Вопросы собеседования 203

9. Рекурсия и динамическоепрограммирование

205

С чего начать 206Динамическое программирование 207Рекурсивные и итерационныерешения

209

Вопросы собеседования 210

10. Сортировка и поиск 213Общие алгоритмы сортировки 214Алгоритмы поиска 220Вопросы собеседования 221

11. Масштабируемость и ограниченияпамяти

224

Пошаговый подход 224Что нужно знать: информация,стратегия и проблема

226

Конец ознакомительного фрагмента. 227

Гейл Лакман МакдауэллКарьера программиста.

Как устроиться наработу в Google,

Microsoft или другуюведущую IT-компанию

150 тестовых заданий

CRACKING THE CODING INTERVIEW5th Edition

150 Programming Interview Questions and Solutions

GAYLE LAAKMANN MCDOWELLFounder and CEO, CareerCur.com

CareerCur, LLCPalo Alto, CA

Все права защищены. Никакая часть данной книгине может быть воспроизведена в какой бы то ни было

форме без письменного разрешения владельцев ав-торских прав.

Информация, содержащаяся в данной книге, полу-чена из источников, рассматриваемых издательствомкак надежные. Тем не менее, имея в виду возможныечеловеческие или технические ошибки, издательствоне может гарантировать абсолютную точность и пол-ноту приводимых сведений и не несет ответственно-сти за возможные ошибки, связанные с использова-нием книги.

© 2008–2011 by Gayle Laakmann McDowell© Перевод на русский язык ООО Издательство «Пи-

тер», 2012© Издание на русском языке, оформление ООО Из-

дательство «Питер», 2012

Перевел с английского Д. Колисниченко

Предисловие

Дорогой читатель!Я не HR-менеджер и не работодатель, а всего лишь

разработчик программного обеспечения. Именно по-этому я знаю, что может произойти на собеседова-нии (например, вас попросят быстренько разработатьблестящий алгоритм, а затем написать к нему без-упречный код). Мне самой давали такие же задания,когда я проходила собеседование в Google, Microsoft,Apple, Amazon и в других компаниях.

Случалось мне быть и по другую сторону баррикад– я проводила собеседования, просматривала стоп-ки резюме соискателей, занимаясь подбором персо-нала для компании Google, я выбирала из множествакандидатов самого подходящего. Именно поэтому я сполной уверенностью могу утверждать, что мне зна-комы все круги того ада, который называется устрой-ством на работу.

Если вы читаете эти строки, то это означает, что высобираетесь пройти собеседование завтра, на следу-ющей неделе или через год. И смею предположить,это собеседование будет иметь отношение к инфор-мационным технологиям.

В этой книге мы не будем заниматься основами, вы

не найдете здесь информации о том, что такое би-нарное дерево поиска или как пройтись по связанно-му списку. Эти элементарные вещи должны быть вамзнакомы, а если это не так, то эта книга не для вас.

Моя задача – помочь вам перейти в IT-области нановый уровень и понять, как использовать свои зна-ния, чтобы с успехом пройти собеседование. В пятомиздании моей книги вас ожидают более 400 страницс вопросами, задачами, решениями и пр. Обязатель-но загляните на сайт www.careercup.com, там вы мо-жете пообщаться с другими соискателями и получитьновую информацию.

Хорошая подготовка позволит вам расширить вашитехнические и коммуникативные способности, а этоникогда не бывает лишним. Даже если информацияво вступительных главах вам покажется неинтерес-ной или хорошо знакомой, не пролистывайте их: мо-жет быть, именно там найдется тот самый ключик, ко-торый откроет для вас заветную дверь офиса потен-циального работодателя.

Не расслабляйтесь – собеседование будет слож-ным! В свое время (в период моей Google’вской рабо-ты) я видела многих интервьюеров, одни из них зада-вали легкие вопросы, а другие – сложные. Но слож-ность вопросов никак не влияла на результат собесе-дования.

Главное – не вопросы, а ваши ответы на них. Иваши ответы должны выгодно отличаться от ответовдругих кандидатов. И не паникуйте, если вам достал-ся сложный вопрос, – те, кто его задают, знают, что во-прос сложен и не ждут от вас моментального ответа.

Читайте, учитесь, а я желаю вам удачи!

Гэйл Лакман Макдауэлл,основатель CareerCup.com

Введение

Что-то не так

Мы провели очередное собеседование… И никтоиз десяти кандидатов не получил работу. Может быть,мы были слишком строги? Лично меня ждало глубо-кое разочарование: мой бывший студент не прошелсобеседование, а ведь я его рекомендовала. У негобыл достаточно высокий средний балл (3,73 GPA1) вВашингтонском университете – одной из лучших школмира по компьютерным дисциплинам, – и он актив-но занимался OpenSource-проектами. Он был энерги-чен, креативен, он упорно трудился и был компьютер-ным фанатом в хорошем смысле этого слова.

Но, к сожалению, члены комиссии были неумоли-мы, и я должна была согласиться с их мнением. Дажеесли бы сыграла свою роль моя рекомендация, мое-

1 GPA (Grade Point Average) – средний балл за время обучения. В СШАвместо пятибалльной системы используют буквенные оценки, при этомA (наивысший балл) соответствует 4, B – 3, C – 2, D – 1, F – 0. Считается,что если GPA выше 3, то об этом стоит упомянуть в резюме. В почетноеобщество Phi Thetta Kappa (http://www.ptk.org/) входят студенты, у кото-рых GPA не меньше 3,5. – Примеч. перев.

му ученику отказали бы на более поздних этапах от-бора. Слишком много было «красных» карточек.

Интервьюеры ожидали, что он проявит креатив-ность мышления, а он просто изо всех сил решал за-дачи, поставленные на собеседовании. Более успеш-ные кандидаты быстро разобрались с первым вопро-сом, который был построен на известной задаче. Ау моего студента возникли проблемы с разработкойалгоритма. Когда он наконецто осилил алгоритм, тоне смог оптимизировать решения для других сцена-риев. Когда дело дошло до написания кода, он допу-стил множество ошибок. Это был не худший кандидат,но все видели, как он далек от победы.

Пару недель спустя он подошел ко мне, а я не зна-ла, что сказать. Нужно стать еще умнее? Дело былоне в этом, я знала, что у него блестящий ум. Научить-ся лучше программировать? Нет, его навыки были нехуже, чем у других программистов, которых я толькознала.

Он тщательно готовился, как и большинство канди-датов. Он изучил K&R2 и CLRS3. Он может описать в

2 K&R (Kernighan and Ritchie) – The C Programming Language (Б. Кер-ниган, Д. Ритчи. Язык программирования C) – классический учебник попрограммированию на языке C, написанный его разработчиками. – При-меч. перев.

3 CLRS (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,Clifford Stein) – Introduction to Algorithms (Т. Кормен, Ч. Лейзерсон, Р. Ри-

подробностях множество способов балансировки де-рева и умеет делать на C такие вещи, которые боль-шинству программистов просто не снились.

Мне пришлось сказать ему горькую правду – книж-ного академического образования недостаточно. Кни-ги – это замечательно, но они не помогут вам пройтисобеседование. Почему? Подскажу: интервьюеры невстречали «деревьев» со времен обучения в универ-ситете.

Собеседование – не университетский экзамен, тамвас ждут реальные вопросы и практические задачи.Книга «Карьера программиста» основана на опытемоего практического участия во множестве собеседо-ваний, проводимых лучшими компаниями. Это квинт-эссенция сотен интервью с множеством кандидатов,результат ответов на тысячи вопросов, задаваемыхкандидатами и интервьюерами в ведущих мировыхкорпорациях. В эту книгу из тысяч задач и вопросовбыли отобраны 150 наиболее интересных.

вест, К. Штайн. Алгоритмы. Построение и анализ) – популярнейшая кни-га по алгоритмам и структурам данных.

Мой подход

В данной книге основное внимание уделено зада-

чам алгоритмизации, программирования и дизайна.Почему? Ответы на «поведенческие» вопросы могутварьироваться, как и ваше резюме. В большинствефирм предпочитают задавать тривиальные вопросы(например, «Что такое виртуальная функция?»), поответам на которые легко можно понять уровень под-готовки кандидата. Я расскажу и о таких вопросах, нопрежде всего я хотела бы уделить внимание болеесложным вещам.

Моя страсть

Моя страсть – преподавание. Мне нравится помо-

гать людям совершенствоваться и узнавать новое.Мой первый «официальный» преподавательский

опыт я получила в колледже Пенсильванского универ-ситета на должности ассистента преподавателя, этобыл курс информатики.

Как инженеру Google, мне всегда нравилось обу-чать и воспитывать «нуглеров» (nooglers) – так вGoogle называют новичков. Я уделяла 20 % временипреподаванию курса информатики в Вашингтонскомуниверситете.

Эта книга и сайт CareerCup.com – отражения моейстрасти к преподаванию. Даже сейчас вы можете най-ти меня на CareerCup.com, где я помогаю пользовате-лям. Присоединяйтесь к нам!

Гэйл Лакман Макдауэлл

Зарегистрируйтесь на сайте http://www.crackingthecodinginterview.com, чтобы получитьдоступ ко всем решениям, обновлениям, принять уча-стие в обсуждении задач, приведенных в этой книге,и разместить свои резюме.

От издательства

Ваши замечания, предложения, вопросы отправ-

ляйте по адресу электронной почты comp@piter.com(издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение! На веб-сайтеиздательства http://www.piter.com вы найдете подроб-ную информацию о наших книгах.

Часть I. Процесс собеседования

Небольшое вступление

Способы проведения собеседования у всех компа-ний практически одинаковы. Мы вкратце рассмотрим,как компании проводят собеседование и какова егоцель. Эта информация поможет вам подготовиться ипокажет, как правильно себя вести на собеседовании.

Если ваше резюме покажется работодателю инте-ресным, вас ожидает так называемое предваритель-ное (скрининговое) собеседование. Обычно оно про-водится по телефону.

Но пусть «удаленная» форма этого собеседованияне введет вас в заблуждение. Вам могут быть зада-ны вопросы по кодингу (программированию) и алго-ритмизации, а от полученных результатов будет зави-сеть ваша дальнейшая судьба. Если вы хотите зара-нее знать специфику собеседования, узнайте долж-ность вашего интервьюера. Инженеры и специалистылюбят задавать технические вопросы.

Некоторые компании для обмена информациейпри собеседовании используют онлайн-редакторы, нобудьте готовы к тому, что вас попросят записать код на

бумаге и продиктовать его по телефону. В некоторыхслучаях вы можете получить «домашнее задание», анаписанный код потребуется отправить по электрон-ной почте.

После одного или двух успешных предварительныхинтервью вам предложат пройти

очное собеседование. Основное собеседованиесостоит из 4–6 небольших интервью. Одно из нихобычно носит неформальный характер, и на нем бу-дут заданы вопросы о ваших интересах и вашем от-ношении к корпоративной культуре. Остальные – тех-нические интервью – состоят из множества вопросовпо алгоритмизации и программированию. Кроме того,будьте готовы ответить на вопросы по вашему резю-ме.

Затем интервьюеры встречаются, чтобы обсудитьрезультаты и принять решение.

Обычно это решение доводится до соискателя в те-чение недели. Если за этот срок с вами никто не свя-зался, проявите инициативу. Молчание еще не озна-чает, что вам отказали. С вами обязательно свяжутся,когда будет принято окончательное решение.

Задержка с ответом – это не редкость. Свяжитесьс вашим нанимателем, если прошло много времени,но будьте вежливы. Наниматели такие же люди, как ивы, – они бывают заняты и им свойственна забывчи-

вость.

Как выбираются вопросы

Кандидаты часто спрашивают меня, какие вопросы

задавались на последнем собеседовании в той илииной компании, наивно полагая, что вопросы не ме-няются. Но то, какие вопросы будут заданы, зависиттолько от интервьюера.

В крупных компаниях интервьюеры проходят подго-товку на специальных курсах. Так, во время своей ра-боты в Google я посещала курсы интервьюеров. По-ловина учебного времени была посвящена мораль-но-этическим вопросам собеседования – никогда неспрашивайте кандидата о его семейном положении,национальности и т. д. Вторая половина отводиласьработе с «проблемными» кандидатами. Дело в том,что некоторые люди неадекватно реагируют на вопро-сы, касающиеся программного кода, считая что ин-тервьюер сомневается в их профессионализме.

По окончании курсов мне была предоставлена воз-можность поприсутствовать на паре реальных собе-седований и прочувствовать, как все происходит вдействительности. Только после этого я считалась до-статочно подготовленной, чтобы проводить самосто-ятельные собеседования.

Это всё, чему нас учили на этих курсах, и для боль-

шинства компаний такое обучение типично. На кур-сах не рассматривалась тема «Обязательные вопро-сы собеседования Google», никто не оглашал списоктипичных вопросов и не требовал избегать какихлибопрофессиональных тем.

Так откуда же берутся вопросы? Да откуда угодно!Некоторые интервьюеры используют вопросы, задан-ные им самим, когда они были кандидатами. Неко-торые обмениваются вопросами с коллегами. Неко-торые ищут вопросы в Интернете и даже бессовест-но используют вопросы, взятые с сайта CareerCup.com. А отдельные интервьюеры используют творче-ский подход: они находят готовые вопросы любым изперечисленных выше способов, а потом видоизменя-ют их. Компании чаще всего не предоставляют ин-тервьюерам списки вопросов. Интервьюер приходитс собственным списком, который содержит как ми-нимум пять вопросов. Поэтому, когда вы в следую-щий раз захотите узнать, какими были «последние»вопросы на собеседовании в Google, вспомните, чтовопросы Google будут мало отличаться от вопросовAmazon, поскольку они не зависят от компании. Сло-во «возраст» для вопросов не актуально: они остают-ся неизменными в течение очень долгого времени.

Вопросы могут зависеть от направления работыкомпании. В веб-ориентированных компаниях могут

задаваться вопросы по дизайну, а в компаниях, рабо-тающих с базами данных, – вопросы по базам дан-ных. Большинство вопросов, как правило, относятсяк категории «структуры данных и алгоритмы» и могутбыть заданы при приеме в любую компанию.

График и карта подготовки

Успех собеседования зависит только от вашей под-

готовки, а она может начаться задолго до самого собе-седования – даже за несколько лет. Если вас интере-сует определенная компания или компании, преждевсего вам следует получить некоторый техническийопыт, который может интересовать эту компанию, акроме того вы должны уметь решать практические за-дачи. Следующая схема демонстрирует все то, о чемвы должны думать до, во время и после собеседова-ния.

Если вы читаете эту книгу, а собеседование уже увас на носу, не волнуйтесь. Постарайтесь извлечь изкниги как можно больше полезной информации и со-средоточьтесь на подготовке к собеседованию. Удачи!

Процедура оценки

На вопрос, как оцениваются кандидаты, большин-

ство HR-менеджеров ответят, что используются четы-ре критерия: предшествующий опыт, корпоративнаякультура, навыки программирования и аналитическиеспособности. Эти четыре кита без сомнения важны,но на деле все сводится к оценке ваших навыков про-граммирования и аналитических способностей (ин-теллекта). Именно поэтому большая часть этой книгипосвящена улучшению ваших навыков программиро-вания и алгоритмизации.

Но это не означает, что вы можете игнорироватьпервые два критерия. В крупных IT-корпорациях вашпредшествующий опыт может не играть решающейроли, но оказать влияние на дальнейшее собеседо-вание. Например, если вы упомянете о ранее напи-санной программе, а интервьюер решит, что она пре-восходна, то, в конечном счете, он может проститьвам некоторые ошибки. Ведь собеседование – это неэкзамен. Так что стоит потратить немного времении вспомнить свой успешный программистский опыт.Корпоративная культура (сюда же относится и вашеотношение к компании) важна скорее для небольшихкомпаний, а не для крупных. Она определяет, будете

ли вы принимать самостоятельные решения или надвами постоянно должен стоять руководитель. Вот ещена что нужно обратить внимание:

• Если интервьюер посчитает, что вы высокомер-ны или склочны, вас, несмотря на всю вашу гениаль-ность, скорее всего, не возьмут на работу. Даже су-перзвезде можно отказать, если окажется, что она неспособна работать в коллективе.

• Подготовьтесь к вопросам о вашем резюме. Этохоть и не решающий фактор, но довольно значимый.Потратьте толику времени на прочитывание вашегорезюме, это позволит вам не сесть в лужу на собесе-довании.

• Сфокусируйтесь на главном – на вопросах алго-ритмизации и кодирования.

Всегда помните, что интервьюирование – это неточная наука. Решение принимается под влияниеммножества случайных факторов. Любая группа лю-дей, проводящих собеседование, субъективна: вы мо-жете больше понравиться как человек, нежели какспециалист. По отношению к вашему профессиона-лизму это будет не очень справедливо, но тем не ме-нее поможет пройти собеседование.

И наконец: с отказом жизнь не заканчивается. В те-чение года вы можете повторно попытаться пройтисобеседование: многие кандидаты, изначально полу-

чившие отказ, позднее получали приглашение на ра-боту.

Неправильные ответы

Одним из распространенных и опасных заблужде-

ний является то, что кандидат должен абсолютно пра-вильно и грамотно ответить на все поставленные во-просы. Это утверждение далеко от истины.

Во-первых, ответы на вопросы собеседования неоцениваются по принципу «правильный – неправиль-ный». Когда я даю оценку кандидату, то никогда неподсчитываю количество правильных ответов на во-просы. Скорее я оцениваю оптимальность вашего ре-шения, сколько времени было потрачено и насколькочист ваш код. Это не двоичная оценка – «да» (1) или«нет» (0), на результат оказывает влияние множествофакторов.

Во-вторых, ваши результаты рассматриваются всравнении с другими кандидатами. Вы нашли опти-мальное решение за 15 минут, а кто-то решил ту жезадачу за пять. Означает ли это, что он лучше вас?Может быть, да, а может и нет. Если вам задают-ся простые вопросы, то ожидается, что оптимальноерешение будет получено быстро. Но если вопросысложные, то интервьюер предполагает, что вы можетедопустить ряд ошибок.

На собеседованиях в Google я видела единствен-

ного кандидата (из нескольких тысяч), который не до-пустил ни одной ошибки. Все остальные, включая сот-ни тех, кто был принят, их допускали.

Дресс-код

Разработчики программного обеспечения, как и

свободные художники, одеваются достаточно нефор-мально. Но собеседование – это как раз то меропри-ятие, на котором вас встретят по одежке. Существуетнегласное правило: ваша одежда должна выгодно от-личаться от одежды других кандидатов на эту же ва-кансию.

Я даже могу дать вам некоторые рекомендации привыборе одежды для собеседования. Знание правилдресс-кода обеспечит вам попадание в «безопаснуюзону» – нужно выглядеть не слишком модным, но ине слишком обычным. Многие люди, приходящие насобеседование в крупную компанию в драных джин-сах и футболках, получили работу. В конце концов, ин-тервьюеры в первую очередь оценивают навыки про-граммирования, а не внешний вид.

Все это – абстрактные рассуждения, вы должныучитывать специфику компании, где будете проходитьсобеседование. Если вы планируете получить долж-ность проект-менеджера, ведущего разработчика илилюбую другую административную должность, то выдолжны одеться более строго.

10 наиболее частых ошибок

1. Использование компьютера

Станете ли вы учиться серфингу в бассейне? Ско-рее всего, нет. Ведь вам нужны волны и другие осо-бенности «живой природы». Могу поспорить, что вашвыбор падет на океанское побережье.

Использование компилятора для «репетиции» со-беседования подобно тренировкам в бассейне. За-будьте про компилятор, возьмите ручку и лист бума-ги. Используйте компилятор для проверки решения,но только после того, как написали и протестироваликод.

2. Игнорирование

поведенческих вопросов

Многие кандидаты тратят все свое время на подго-товку к техническим вопросам и упускают поведенче-ские. Но ваш интервьюер, скорее всего, их не упустит!Более того, ответы на поведенческие вопросы могутизменить восприятие интервьюером ваших профес-сиональных данных. К ответам на поведенческие во-

просы легко подготовиться. Вспомните все свои про-екты и используйте их для подготовки.

3. Отказ от псевдоинтервью

Представьте, что вы готовитесь к публичному вы-

ступлению перед своей группой, компанией или ка-кой-нибудь другой большой аудиторией. Ваше буду-щее зависит от этого. Только сумасшедшие или из-лишне самоуверенные люди будут готовить такуюречь в одиночку.

Один из способов подготовки – так называемоепсевдоинтервью. Если вы инженер, то должны бытьзнакомы с коллегами. Попросите приятеля провестидля вас «собеседование». Этот метод принесет толь-ко пользу!

4. Попытка зазубрить ответ

Запоминание решения конкретной задачи приго-

дится вам только в том случае, если интервьюер дастименно эту задачу, но никак не поможет решить но-вые задачи. Очень маловероятно, что в этой книге вынайдете все или хотя бы большую часть вопросов, ко-торые могут достаться вам на собеседовании.

Намного эффективнее не привязываться к конкре-

тике. Это поможет вам разработать стратегии реше-ния новых задач. Лучше качество, нежели количество.

5. Решение задачи «в уме»

Открою вам секрет – я не телепат и не знаю, что

происходит у вас в голове. Следовательно, если выничего не произносите вслух, не известно, о чем выдумаете. Если вы молчите, я считаю, что у вас нетрешения. Больше говорите и пытайтесь комментиро-вать решение. Это покажет интервьюеру, что вы ре-шаете поставленную задачу, а ваше молчание будетрасценено как то, что вам нечего сказать.

Дайте возможность интервьюеру подсказать вампуть решения или указать на ошибку, когда вы в этомбудете нуждаться. Простейшие навыки коммуника-ции помогут получить желаемую вакансию. Что можетбыть лучше?

6. Спешка

Программирование – это не ралли, даже на собесе-

довании. Уделите больше времени написанию кода.Спешка приводит к ошибкам, а они могут быть рас-ценены как небрежность. Пишите код последователь-но и неторопливо, анализируйте задачу и проверяйте

код. В итоге вы закончите работу за меньшее времяи с минимальным количеством ошибок (а может и безних).

7. Грязный код

Знаете ли вы, что код, даже написанный без оши-

бок, может быть просто ужасным? К сожалению, этотак! Дублирование, огромные структуры данных (от-каз от объектно-ориентированного программирова-ния) и т. д. являются показателями плохой програм-мы! Когда вы пишете код, представьте, что он долженбыть «ремонтопригодным». Разбейте код на подпро-граммы и выберите оптимальную структуру, соответ-ствующую данным.

8. Отказ от проверки

Когда вы пишете код в реальной жизни, вы его те-

стируете, так почему бы этого не сделать на собесе-довании? Когда код написан, «запустите» его (в каче-стве компилятора будете выступать вы сами) и про-тестируйте. При решении сложных задач тестируйтефрагменты кода по мере написания.

9. Небрежное отношениек исправлению ошибок

Ошибки неизбежны. Это норма жизни и програм-

мирования. Если вы тщательно протестируете код, тонаверняка обнаружите свои ошибки, – и это хорошо.Если вы обнаружили ошибку, то прежде чем испра-вить ее, постарайтесь разобраться, откуда она появи-лась. Некоторые кандидаты, обнаруживая, что приопределенных условиях функция возвращает false,просто инвертируют значение, а не разбираются, по-чему так происходит. Конечно, это встречается не ча-сто, но подобное действие порождает дополнитель-ные ошибки и показывает, насколько вы небрежно от-носитесь к написанию кода.

Никто не застрахован от ошибок, но бездумное ис-правление кода недопустимо.

10. Отказ от решения

Очень часто вопросы оказываются достаточно

сложными. Примете ли вы вызов или повернете на-зад? Я рекомендую достойно встретить трудную за-дачу. Ведь собеседования для этого и проводятся.Не удивляйтесь, когда вам достанется действительно

сложный вопрос.

Часто задаваемые вопросы

Нужно ли мне говорить интервьюеру,что я уже знаком с вопросом?

Да! Вы обязательно должны сказать своему интер-

вьюеру, что знаете вопрос (и ответ на него). Конечно,многим людям это может показаться глупым, ведь ес-ли вы знаете вопрос и ответ, то с легкостью справи-тесь, правильно? Не совсем так.

Существует несколько причин, по которым выдолжны сказать экзаменатору, что знакомы с этим во-просом:

• Вы завоюете расположение интервьюера. Вы про-демонстрируете свою честность, а это много значит.Помните, что интервьюер оценивает вас как потен-циального товарища по команде, и в этом случае выпроявите себя как честный и порядочный человек.

• Постановка задачи могла быть изменена. Не нуж-но рисковать, повторяя неправильный ответ.

• Если вы легко и быстро дадите правильный ответ,интервьюер сам догадается, что вы знакомы с этой за-дачей. Он знает уровень сложности задания, и быст-рое (и правильное) решение будет выглядеть подо-

зрительным.

Какой язык программированияследует использовать?

Многие говорят, что можно использовать любой

язык, лишь бы вы им отлично владели, но в идеалеэто должен быть язык, которым пользуется интервью-ер. Обычно я рекомендую писать код на C, C++ илиJava, поскольку большинство интервьюеров владеютэтими языками. Мое личное предпочтение – Java (заисключением заданий, требующих C/C++), посколькуэтот язык прост и понятен любому человеку, даже ес-ли он программирует на C++. Именно по этой причинерешения всех задач в этой книге выполнены на Java.

После собеседования мне ничего

не сказали. Мне отказали?

Нет. Практически все компании сообщают своимкандидатам об отказе. Если вам сразу ничего не ска-зали, то это ничего не означает. Возможно, вы приня-ты, но у вашего агента (представителя рекрутинговойкомпании) выходной, и он сообщит вам об этом поз-же. В компании может производиться реорганизация,и еще не ясно, сколько сотрудников понадобится. Хо-

тя может оказаться, что вы действительно не подхо-дите, но рекрутинговая компания не удосужилась со-общить вам об этом. Довольно странно для компанииотказать кандидату и не сообщить о своем решении. Винтересах нанимателя уведомить вас об окончатель-ном решении, как только оно принято.

Могу ли я попытаться еще

раз, если мне отказали?

Практически всегда можно сделать еще одну по-пытку, но нужно сделать паузу (обычно от 6 месяцевдо одного года). Плохие результаты наверняка окажутнегативное влияние на результаты повторного собе-седования. Но многие люди, которым отказал Googleили Microsoft, впоследствии получили работу.

Часть II. За кулисами

Для большинства кандидатов собеседование похо-

же на черный ящик. Вы входите, получаете вопросыи выходите… с предложением работы или без него.Задавались ли вы вопросами:

• Как принимаются решения?• Общаются ли интервьюеры друг с другом?• Что интересует компанию?Скоро вы узнаете ответы!Специально для этой книги мы нашли экспер-

тов-интервьюеров от пяти ведущих компаний –Microsoft, Google, Amazon, Yahoo! и Apple, – чтобыузнать из первых рук, что происходит там, за кулиса-ми.

Эти эксперты рассказали нам про типичное собе-седование и поведали, что происходит после того, каквы уходите.

От них мы узнали, чем различаются собеседова-ния – от Amazon до Google. У каждой компании естьособенности, знание которых позволит вам избежатьситуации, когда один строгий экзаменатор из Amazonили два из Apple указывают вам на дверь.

Кроме того, эксперты поведали нам, на что впервую очередь обращают внимание. Компании, за-

нимающиеся разработкой программного обеспече-ния, фокусируются на алгоритмах и коде. В другихкомпаниях могут быть другие специфические приори-теты. Зная особенности компании, вы сможете лучшеподготовиться.

Поэтому присоединяйтесь к нам, поскольку мысобираемся заглянуть за кулисы Microsoft, Google,Amazon, Yahoo! и Apple.

Microsoft

Microsoft ищет умных людей – фанатов, увлеченных

технологиями. Скорее всего, здесь не потребуют отвас идеального знания C++ API, но ожидают, что вы всостоянии написать код.

Итак, типичное собеседование от Microsoft. Одна-жды утром вы появляетесь в офисе и заполняетепредварительные документы. Затем вас ждет корот-кое собеседование со специалистом по подбору кад-ров, который задаст ряд несложных вопросов. Задачаэтого специалиста – подготовить вас к интервью, а немучить техническими вопросами. Он должен помочьвам собраться, для того чтобы вы меньше нервнича-ли на настоящем собеседовании.

Будьте вежливы со специалистом по подбору кад-ров. Он будет вашим адвокатом в том случае, если выпровалитесь на первом собеседовании. Он поможетвам попасть на повторное собеседование. Рекрутерымогут отстаивать ваши интересы вне зависимости оттого, будете вы наняты или нет.

Вам предстоят четыре или пять собеседований, за-частую с разными командами интервьюеров. В отли-чие от других компаний, где вы встречаетесь с эк-заменаторами в конференц-зале, вы будете беседо-

вать с интервьюерами в их офисе. Рассматривайтеэти собеседования как возможность прочувствоватькомандный дух.

Интервьюеры могут сказать, какое впечатление вына них произвели (или, наоборот, не сказать). Когдаинтервью закончено, с вами может побеседовать спе-циалист из отдела кадров, но только если вы успеш-но прошли собеседование. Знайте, если вы увиделименеджера по кадрам – это хороший знак!

Решение вам сообщат в течение дня или, макси-мум, недели. Если неделя прошла, а вы не получилиникаких известий от рекрутера, напомните ему о себепо электронной почте.

Не забывайте, что отсутствие ответа может озна-чать лишь то, что ваш рекрутер рассеянный или оченьзанятой человек, а не то, что вам отказали.

Подготовиться!Почему вы хотите работать именно в

Microsoft?В ответе на этот вопрос Microsoft хочет

услышать, что вы увлечены их технологиями.Лучший ответ выглядит примерно так: «Явсегда использовал программное обеспечениеMicrosoft, и действительно впечатлен тем,как Microsoft удается создавать превосходныйпрограммный продукт. Например, я использовалVisual Studio для программирования игр, а API

просто превосходен». Покажите свое увлечениетехнологией!

ОсобенностиВы будете иметь беседу с менеджером

по кадрам только в том случае, если выпрошли собеседование. Расценивайте разговор сменеджером как хороший знак.

Amazon

В Amazon процесс обычно начинается с пары скри-

нинговых интервью по телефону, во время которыхкандидат беседует с разными командами. Впрочем,собеседований может быть и больше – это означа-ет, что интервьюеры сомневаются или же вас рас-сматривают как кандидата в несколько команд. Режеограничиваются одним скрининговым интервью. Такпроисходит, если кандидат знаком интервьюерам илинедавно проходил собеседование на другую вакан-сию.

Инженер, проводящий собеседование, обычно про-сит написать небольшой фрагмент кода, используяспециальный редактор, например CollabEdit4. Зача-стую интервьюеров интересует, какими технологиямивы владеете.

Затем вас приглашают в Сиэтл. Вам предстоитпройти еще четыре или пять собеседований с однойили двумя командами, которые выбрали вас на ос-новании резюме и телефонного интервью. Вам пред-ложат написать программный код, чтобы другие ин-

4 Данный редактор используется для совместной работы над докумен-тами. То есть интервьюер будет видеть все изменения, вносимые вамив документ, в реальном времени. – Примеч. перев.

тервьюеры смогли оценить ваши навыки. У каждогоинтервьюера свой профиль, поэтому вопросы могутсильно различаться. Интервьюер не может знать ре-шение коллег до тех пор, пока не поставит собствен-ную оценку.

У собеседования в Amazon есть особенность –главный интервьюер (bar riser). Он проходит специ-альную подготовку и может общаться с кандидатамивне пределов их группы, чтобы сбалансировать груп-пу в целом. Если вопросы одного из интервьюеровоказываются более сложными, чем у остальных, ско-рее всего, это главный интервьюер. У него огромныйопыт в проведении собеседований, и его решение мо-жет быть окончательным. Помните: если в собеседо-вании с главным интервьюером вы показали себя схорошей стороны, это еще не означает, что решениядругих интервьюеров не будут учитываться.

Как только интервьюеры выставили оценки, онивстречаются, чтобы принять окончательное решение.В большинстве случаев HR-менеджеры от Amazonпревосходно выполняют свои обязанности, но и у нихбывают накладки. Если вы не получили ответ в тече-ние недели, напомните о себе по электронной почте.

Подготовиться!Amazon – веб-ориентированная компания,

и она беспокоится о масштабировании.

Убедитесь, что вы готовы к вопросамо модульном наращивании систем. Длялучшей подготовки к вопросам интервьюеровпрочитайте главу «Масштабируемость иограничения памяти». В Amazon любят задаватьвопросы по объектно-ориентированномупрограммированию. Прочитайте главу 8«Объектно-ориентированное проектирование».

ОсобенностиВы должны произвести должное впечатление

на главного интервьюера и менеджера по найму,если хотите пройти собеседование и получитьдолжность.

Google

Ходит много страшных рассказов о прохождении

собеседования в Google, но это только слухи. На са-мом деле собеседование в Google не очень отличает-ся от собеседования в Microsoft или Amazon.

Прежде всего инженер Google побеседует с вамипо телефону, так что ожидайте технических вопросов.Эти вопросы могут включать в себя написание кода,иногда через совместную работу с документом. Обыч-но кандидатам задаются одинаковые вопросы и прителефонном собеседовании, и на личной встрече.

На личном собеседовании с вами будут общатьсяот четырех до шести интервьюеров, в том числе иглавный интервьюер (lunch interviewer). Решение ин-тервьюера является тайной, никто не знает, что дума-ет его коллега. Вы можете быть уверены, что интер-вьюер дает независимую оценку.

У интервьюеров нет согласованной «структуры»или «системы» вопросов. Вам могут задать любой во-прос, который посчитают нужным. Затем результатысобеседования передаются в комитет по подбору пер-сонала, инженеры и менеджеры которого принимаютрешения о приеме на работу. Обычно оцениваютсячетыре критерия (аналитические способности, навы-

ки программирования, опыт и коммуникативные спо-собности), по каждому из них выставляются оценки от1.0 до 4.0. Интервьюеры обычно не участвуют в ра-боте комитета по подбору персонала, поэтому они немогут повлиять на решение. Решающую роль играютваши оценки. Комитет хочет видеть ваши преимуще-ства по отношению к другим кандидатам. Оценки 3.6,3.1, 3.1, 2.6 предпочтительнее, чем все 3.1.

Не обязательно становиться лучшим на каждом со-беседовании, телефонное собеседование тоже не яв-ляется решающим фактором. Если комитет по подбо-ру персонала принял положительное решение, вашпакет документов будет направлен в комитет, за-нимающийся назначением заработной платы, затемв исполнительный управляющий комитет. Принятиеокончательного решения затягивается на нескольконедель, поскольку Google имеет множество разныхуровней и комитетов.

Подготовиться!Google – веб-ориентированная компания,

заинтересованная в разработке наращиваемыхмодульных систем. Поэтому убедитесь, что выизучили вопросы из главы «Масштабируемостьи ограничения памяти». Интервьюеры Googleлюбят задавать вопросы из раздела«Поразрядная обработка», поэтому убедитесь,что вы разобрались в этой теме.

ОсобенностиВаши интервьюеры не принимают решение

о найме, их оценки передаются в комитет поподбору персонала, который дает рекомендации(принять или отказать) исполнительномукомитету Google.

Apple

Apple – наименее бюрократичная компания. Интер-

вьюеры будут оценивать не только технические на-выки, для них очень важно ваше отношение к компа-нии. Желательно, чтобы соискатель был пользовате-лем Мака или, по крайней мере, был знаком с этойсистемой.

Интервью обычно начинается с телефонного звон-ка рекрутера – он должен оценить ваши базовые на-выки, затем происходит серия технических интервьюс членами команды.

После приглашения в кампус рекрутер вкратце рас-скажет вам о процедуре собеседования. Затем васждет 6–8 собеседований с членами команды. Это поз-волит вам познакомиться с будущими коллегами.

Вам предстоит смесь собеседований 1-на-1 и 2-на-1. Будьте готовы писать программный код и убе-дитесь, что умеете четко формулировать свои мыс-ли. Обед с возможным будущим начальником можетпоказаться случайностью, но все это – продолжениесобеседования. Каждый интервьюер занимается соб-ственной областью и обычно не обсуждает ваши ре-зультаты с другими.

Подготовиться!

Если вы знаете, какая команда будетпроводить собеседование, убедитесь, чтознакомы с продуктом этой команды. Нравитсяли он вам? Что вы хотели бы улучшить?Продемонстрируйте свою заинтересованность.

ОсобенностиИнтервью часто проводятся в режиме 2-на-1,

не беспокойтесь, он не отличается от режима 1-на-1. Не забывайте, что сотрудники Apple должныбыть фанатами своей продукции, поэтомупродемонстрируйте заинтересованность.

В конце дня интервьюеры обмениваются мнения-ми. Если они чувствуют, что вы – потенциальный кан-дидат, то дальше вас ждет интервью с директором ивице-президентом компании. Хотя такое собеседова-ние еще ничего не гарантирует, но это хороший знак.Решение принимается за кулисами, и даже если выне подходите, то просто покинете здание, думая, чтовы самый лучший.

После окончания собеседования с директором ивице-президентом интервьюеры уединяются в конфе-ренц-зале, чтобы принять окончательное решение.Обычно вице-президент не присутствует на таком со-вещании, но у него есть право вето, если вы не произ-вели на него должного впечатления. Через несколькодней вы узнаете об окончательном решении от рекру-тера, но не стесняйтесь спросить его пораньше.

Facebook

Хотя при решении онлайновых инженерных голо-

воломок существует много способов сжульничать, этоеще один способ обратить на себя внимание. Простопродолжайте решать задачки, не забывая подать тра-диционное заявление о приеме на работу через он-лайн-службу или ярмарку вакансий.

Перед тем как вас пригласят на очное собеседова-ние, вы пройдете как минимум два телефонных ин-тервью; они будут носить технический характер, и вампридется написать программный код в Etherpad илианалогичном онлайн-редакторе.

Чаще всего интервью проводят разработчики про-граммного обеспечения, но в нем мгут принимать уча-стие и менеджеры по подбору персонала. Каждомуинтервьюеру отводится строго определенная роль,это позволяет гарантировать, что вопросы не будутдублироваться, и в итоге представление о кандидатеполучится более разносторонним. Вопросы разбива-ются на группы: алгоритмы, навыки программирова-ния, архитектура/навыки проектирования, кроме того,оцениваются ваши возможности оперативно реагиро-вать на быстро изменяющуюся среду Facebook.

Интервьюеры пишут отзывы и обсуждают ваши

достижения только после окончания собеседования.Это гарантирует, что успех (или, наоборот, неудача)на одном из собеседований никак не повлияет на ре-зультаты следующего.

Как только отзыв составлен, интересующаяся в васкоманда и менеджер по подбору персонала собира-ются, чтобы принять окончательное решение. Затемрекомендации передаются в комитет по подбору пер-сонала.

В Facebook ищут настоящих «камикадзе», способ-ных докапываться до истины и разрабатывать мас-штабируемые решения на любом языке программи-рования. Знание PHP не играет ключевой роли, по-скольку Facebook также требуются программисты наC++, Python, Erlang и других языках программирова-ния.

Подготовиться!Самой молодой из элитных IT-компаний нужны

инициативные разработчики. Покажите, что выинициативны и можете быстро работать.

ОсобенностиВ Facebook собеседование организуется в

целом для всей компании, а не для какой-то конкретной команды. Если вас взяли наработу, вам предстоит пройти 6-недельный курсмолодого бойца, цель которого – улучшить вашинавыки программирования. Вы получите задания

от старших разработчиков, изучите новые методыи, в конечном счете, подниметесь на уровеньвыше, чем были до собеседования.

Yahoo!

Yahoo! набирает претендентов из двадцати веду-

щих учебных заведений, остальные кандидаты могутпопытать счастья через доску вакансий Yahoo! (или,что еще лучше, по знакомству). Если вас отобрали насобеседование, оно начнется с телефонного звонка.С вами будет беседовать ведущий разработчик илименеджер.

На протяжении собеседования вам предстоитпройти 6–7 интервью длительностью около 45 минуткаждое. Интервьюеры специализируются на конкрет-ных областях. Например, один экзаменатор специа-лизируется на базах данных, другой – на компьютер-ной архитектуре и т. д. Обычно распорядок интервьюследующий:

• 5 минут – общее знакомство, вы рассказываете осебе, о своих проектах и т. д.

• 20 минут – вопросы по кодингу. Вас могут попро-сить, например, реализовать сортировку слиянием.

• 20 минут – системное проектирование. Вам пред-ложат спроектировать большой распределенный кэш.Эти вопросы часто строятся на вашем предыдущемопыте.

В конце дня вы, скорее всего, встретитесь с веду-

щим разработчиком (руководителем). Разговор можетбыть о чем угодно. Вы можете просматривать демо-версии продуктов, рассуждать о развитии компанииили вашей роли в ней. Обычно такая беседа не явля-ется решающим фактором.

Тем временем интервьюеры обсудят ваши резуль-таты и попытаются прийти к решению. Окончательноерешение принимает менеджер по подбору персонала,взвесив ваши сильные и слабые стороны.

Если вы подходите, то вы чаще всего (но не всегда)узнаете об этом в тот же день. Существует множествопричин, по которым на принятие решения понадобит-ся несколько дней. Например, есть еще несколькокандидатов, которые должны пройти собеседование.

Подготовиться!Как правило, в Yahoo! задают вопросы,

связанные с системным проектированием, такчто подготовьтесь к ним. Вы должны уметьне только написать код, но и разработатьпрограммное обеспечение.

ОсобенностиИнтервью проводится не рядовыми

менеджерами по набору персонала. Для Yahoo!характерно то, что решение (приняты вы илинет) обычно принимается в день собеседования.Ваши интервьюеры обсуждают результаты, покавы встречаетесь с последним экзаменатором.

Часть III. Нестандартные случаи

Кандидат-профессионал

Если вы внимательно прочитали предыдущую гла-ву, то следующая информация вас не удивит: канди-датам, имеющим профессиональный опыт, задаютсяте же вопросы, что и их неопытным коллегам, – под-ход меняется незначительно.

Большинство вопросов, как вы уже знаете, по-священы структурам данных и алгоритмам. Крупныекомпании считают, что это хорошая проверка вашихвозможностей. Некоторые интервьюеры оцениваютопытных кандидатов более строго. Если у человекабольшой опыт работы, он должен лучше справитьсяс заданием, не правда ли?

Однако другие интервьюеры имеют противополож-ное мнение. Опытные кандидаты давно окончили уни-верситет, поэтому успели многое забыть, таким обра-зом, их нужно оценивать по более низкому стандарту.

В среднем же подходы различных интервьюеровболее менее сбалансированы. Так что, даже если выопытный кандидат, вам, скорее всего, будут предло-жены те же вопросы, что и прочим.

Исключением из этого правила являются вопросыпо системному дизайну и архитек

туре, а также вопросы по резюме. Обычно студен-ты не любят заниматься системной архитектурой, по-этому знания они получают только во время работы.Следовательно, ваш результат на собеседовании поэтой теме прямо пропорционален вашему опыту. Од-нако эти же вопросы задают и более опытным канди-датам, поэтому вы должны быть готовы решить их так,как можете.

Интервьюеры ожидают, что опыт кандидата позво-лит ему дать более развернутый ответ на поставлен-ный вопрос. Ответ более опытного претендента на во-прос «Какая ошибка, допущенная вами, была самойсерьезной?» будет более интересным и глубоким.

Тестеры и SDET

О вакансии SDET (Software Design Engineer in Test,

программист-тестер) следует поговорить отдельно.Специалисты в этой области должны быть не толькопрекрасными программистами, но и прекрасными те-стерами.

Если вы претендуете на должность тест-програм-миста:

• Подготовьтесь к базовым задачам тестирования.Как вы будете тестировать лампочку? Ручку? Кэш-ре-гистр? Microsoft Word? Глава 12 «Тестирование» по-может ответить на эти вопросы.

• Подготовьтесь к заданиям, связанным с програм-мированием, – тестер обязан уметь программиро-вать. Хотя требования к SDET ниже, чем для SDE(Software Design Engineer, разработчик программно-го обеспечения), вам необходимо разбираться в ал-горитмах. Убедитесь, что вы можете справиться с за-даниями по алгоритмизации и программированию, ко-торые даются обычным разработчикам программногообеспечения.

• Совершенствуйте навыки тестера и программи-ста. В качестве примера возьмем очень популярноезадание: «Какой код нужно написать, чтобы полу-

чить X?» Далее обычно следует: «Ок, а теперь про-тестируйте его». Даже если вас об этом не спросили,уточните: «Как именно нужно протестировать код?»Помните: любое задание может превратиться в тест-задачу.

Для тестеров программного обеспечения оченьважны коммуникативные навыки, поскольку им при-ходится работать с людьми. Не игнорируйте часть V«Подготовка к поведенческим вопросам».

СоветВ завершении этого раздела хочу дать вам

небольшой совет, способствующий карьерномуросту. Если вы, как и многие другиекандидаты, расцениваете должность тестеракак стартовую должность в компании, необольщайтесь. Для многих кандидатов переходс этой должности на должность разработчикапрограммного обеспечения оказался труднымиспытанием. Если вы все-таки решились на этотшаг, убедитесь в том, что сохранили все своинавыки программирования и алгоритмизации,и попробуйте осуществить переход в течениеодного-двух лет – чем больше пройдет времени,тем сложнее это сделать.

Не позволяйте атрофироваться навыкам програм-мирования.

Менеджеры программи менеджеры продукта

PM5 – общая аббревиатура, которой обозначают

как менеджеров программ, так и менеджеров продук-та. Но роли и задачи этих двух PM сильно различают-ся даже в пределах одной компании. В Microsoft, на-пример, некоторые PM, по сути, выполняют функциимаркетологов, то есть больше общаются с клиентами,нежели программируют. А вот в других компаниях PMмогут провести большую часть своего рабочего дня,занимаясь программированием.

Когда интервьюеры ищут кандидата на должностьPM, они ищут человека, способного продемонстриро-вать следующие навыки:

• Обработка неоднозначностей. Это не самаяглавная часть собеседования, но вы должны знать,что интервьюеры приветствуют подобные навыки. Имважно понять, что вы будете делать, когда столкне-

5 В крупных компаниях над одним и тем же продуктом, помимо рядо-вых программистов и тестировщиков, работают менеджеры. Менеджеруправления программой (Program Manager) отвечает за архитектуру ре-шения. А вот менеджер управления продуктом (Product Manager) зани-мается маркетингом и представляет интересы заказчика. Получается,что первый – программист, а второй – маркетолог. – Примеч. перев.

тесь с неоднозначной ситуацией. Поэтому постарай-тесь продемонстрировать, что вы не остановитесь,займетесь поиском новой информации, расстановкойприоритетов и решите задачу. Обычно кандидатов непросят решать конкретную задачу (хотя и такое можетбыть), достаточно рассказать, что вы будете делать втакой необычной ситуации.

• Потребительский фокус. Интервьюеры хотят ви-деть, что вам хорошо знакома целевая аудитория. Вытвердо уверены, что все потенциальный потребителибудут использовать программный продукт точно также, как и вы? Или вы способны взглянуть на продукт сточки зрения клиента и попытаетесь понять, как он бу-дет пользоваться программой? Ожидайте заданий ти-па «Разработайте будильник для слепого». Вы долж-ны понимать, кто является вашей целевой аудитори-ей и как он будет использовать продукт. Необходимыенавыки описаны в главе 12 «Тестирование».

• Потребительский фокус (технические навыки).Некоторые команды, работающие со сложными про-дуктами, хотят убедиться, что их PM понимают сампродукт. Трудно быть эффективным менеджером про-дукта или программы, если не знаешь, как это работа-ет. Близкое знакомство со всеми существующими кли-ентами мгновенного обмена сообщениями, вероятно,окажется бесполезным для работы в команде MSN

Messenger, но понимание задач безопасности явля-ется необходимым условием для работы в WindowsSecurity.

• Коммуникативные способности. PM долженуметь общаться с сотрудниками компании всех уров-ней подготовки и любого статуса. Ваш интервьюерзахочет убедиться, что вы обладаете подобной спо-собностью. Это легко проверяется, например, с по-мощью простого задания «Объясните, что такое TCP/IP, своей бабушке». Ваши коммуникативные способ-ности легко оцениваются по рассказу о вашей преды-дущей работе.

• Страсть к новым технологиям. Счастливые со-трудники – это продуктивные сотрудники, поэтомукомпания должна убедиться, что вы будете получатьудовольствие от работы. В ваших ответах должнопрозвучать, что вы увлекаетесь новыми технология-ми и можете работать в команде. Вас могут спросить:«Чем вам привлекает Microsoft?» Интервьюеры ожи-дают увидеть энтузиазм в вашем рассказе о предше-ствующем опыте и задачах команды. Они хотят ви-деть, что вы стремитесь решать сложные задачи.

• Работа в команде/лидерство. Это может статьрешающим моментом собеседования – ведь это иесть ваша работа. Все интервьюеры пытаются оце-нить то, как хорошо вы работаете с другими людьми.

Интервьюер будет рад видеть, что вы способны спра-виться с конфликтами, берете на себя инициативу, выпонимаете коллектив, и людям нравится работать свами. Вам следует уделить должное внимание пове-денческим вопросам.

Все перечисленные навыки важны для PM и яв-ляются ключевыми для собеседования. Значимостькаждой области примерно одинакова.

Ведущие разработчики и менеджеры

Отличные навыки программирования являются

необходимым условием для ведущих разработчикови очень часто требуются и от «управленцев». Есливаша работа будет связана с программированием,убедитесь, что ваши познания в алгоритмизации ипрограммировании находятся на достаточно высокомуровне. Например, требования Google к менеджерамсущественно выше, чем к обычным программистам.

Дополнительно вас будут оценивать по следующимкритериям:

• Работа в команде/лидерство. Претендент на лю-бую руководящую должность обязан быть лидером иуметь работать с людьми. На интервью вас будут оце-нивать явно и неявно. При открытой оценке вам зада-ют вопрос: «Что вы будете делать, если не согласны

с менеджером?» Неявная оценка проводится по ре-зультатам вашего общения с интервьюерами. Интер-вьюер сразу увидит, что вы высокомерны или, наобо-рот, слишком мягки, чтобы стать лидером (руководи-телем).

• Расстановка приоритетов. Менеджеры частосталкиваются со щекотливыми вопросами, напримеркак убедиться, что команда укладывается в сроки. Ва-ши интервьюеры хотят видеть, что вы способны пра-вильно разложить все «по полочкам» и расставитьприоритеты.

• Коммуникативные навыки. Менеджерам прихо-дится много общаться с людьми, стоящими как выше,так и ниже их по карьерной лестнице. Они должны об-щаться с потенциальными клиентами и менее техни-чески подкованными людьми. Интервьюеры хотят ви-деть, что вы способны общаться с разными людьми,оставаясь дружелюбными и доброжелательными. Посути, на собеседовании делается слепок вашей лич-ности.

• Доведение дела до конца. Менеджер должен бытьчеловеком, который всегда добивается своей цели.Вам необходимо найти баланс между подготовкой кпроекту и его реализацией. Менеджер должен знать,как структурировать проект и как мотивировать лю-дей, только так можно достичь цели.

В конечном счете, все эти критерии относятся к ва-шему предыдущему опыту и к вашей личности. Убе-дитесь, что хорошо подготовились, и проверьте таб-лицу подготовки к собеседованию (см. с. 40).

Стартап

В стартапах6 процессы подачи заявления и собе-

седования имеют существенные различия в зависи-мости от конкретной фирмы. Мы не можем рассмот-реть каждый стартап, но можем обсудить некоторыеобщие черты. Но не забывайте, что у каждого старта-па есть особенности.

Процесс подачи заявления

Стартапы не только публикуют списки вакансий, но

и могут самостоятельно заниматься подбором кад-ров. Приглашающий не обязательно будет вашим кол-легой или другом. Достаточно разместить свое резю-ме на соответствующем сайте, а стартапы найдутсясами.

6 Что же такое стартап (start-up)? Английский язык довольно изворот-лив, и у понятия startup есть множество вариантов перевода: запуск, на-чинание, начало, старт и т. д. Все зависит от контекста. Здесь речь идето компании начального уровня. Итак, стартап – недавно созданная ком-пания – обладает ограниченным набором ресурсов и возможностей. –Примеч. перев.

Виза и разрешение на работу

К сожалению, небольшие стартапы в США не спо-

собны предоставить рабочую визу для своих сотруд-ников. Поверьте, они недовольны подобной ситуаци-ей, но ничем не могут помочь. Если вам нужна рабо-чая виза, лучше всего обратиться к профессиональ-ному вербовщику, который работает со многими стар-тапами, или поискать более серьезную компанию.

Резюме

Стартаперы – это не только программисты. Это лю-

ди, которые способны быть предпринимателями. Ввашем резюме должны быть отражены инициатив-ность и возможность сразу взяться за работу. Ониищут людей, знакомых с языком программирования,который используется в данной компании.

Процесс собеседования

В отличие от крупных компаний, которые оцени-

вают вашу способность к разработке программногообеспечения, стартапы в основном смотрят на вашиперсональные навыки и предшествующий опыт:

• Подгонка личности. Установите дружеские отно-шения с интервьюерами – это залог получения вакан-сии.

• Набор навыков. Поскольку стартапам нужны лю-ди, которые сразу могут приступить к работе, онибудут оценивать ваши навыки программирования наконкретном языке. Если вы знакомы с языком, на ко-тором работает стартап, повторите его основы.

• Предыдущий опыт. Стартапперы задают многовопросов о предыдущем опыте.

Уделите особое внимание части V «Подготовка кповеденческим вопросам».

В дополнение к перечисленным критериям на собе-седовании часто задаются вопросы по программиро-ванию и алгоритмизации, которые вы найдете в этойкниге.

Часть IV. Перед собеседованием

Получаем «правильный» опыт

Хотя решение о найме принимается по результа-там собеседования, огромную роль играют резюме ипредыдущий опыт работы – это ваш пропуск на собе-седование. Вы должны постоянно накапливать техни-ческий (и нетехнический) опыт. Повышая навыки про-граммирования, вы неизменно остаетесь в выигрыше– и неважно, кто вы – студент или профессионал.

Для студентов могут быть полезны следующие ре-комендации:

• Принимайте участие в больших проектах. Да-же если вы еще учитесь, не отказывайтесь от участияв больших проектах. Такой опыт можно будет упомя-нуть в резюме, а это повысит ваши шансы на собесе-дованиях в крупных компаниях. Чем больше проектсвязан с реальными задачами, тем лучше.

• Повышайте квалификацию. Даже на ранних ста-диях обучения вы можете получить профессиональ-ный опыт. Первокурсники (и второкурсники) могут,например, принимать участие в программах Google

Summer of Code7. Если вы не можете принять участиев подобной программе, найдите стартап и попробуйтесвои силы.

• Попробуйте начать какой-либо проект. Соб-ственные проекты производят впечатление на любуюкомпанию. Такая работа не только увеличивает ваштехнический опыт, но и показывает, что вы инициатив-ны и можете достичь поставленной цели. Используй-те выходные дни для разработки собственного про-граммного обеспечения. Если у вас есть научный ру-ководитель, можно попытаться получить грант под ва-шу работу.

Профессионалы тоже должны обладать правиль-ным опытом, который позволит попасть в компаниюих мечты. Вы можете работать в Google, но мечтаетео Facebook. А может, вы работаете тестером, но стре-митесь попасть в более крупную компанию или хоти-те заниматься разработкой программ. В этом случаевам пригодятся следующие советы:

• Сделайте так, чтобы ваши рабочие обязанно-сти максимально приблизились к задачам програм-мирования. Не показывайте своему руководству, что

7 Google Summer of Code (GSoC) – программа компании Google, в рам-ках которой ежегодно проводится отбор проектов с открытым исходнымкодом, в которых могут принять участие студенты. Победителям выпла-чиваются денежные гранты. – Примеч. ред.

вы думаете об уходе, но уделите больше вниманияпрограммированию. Стремитесь к участию в крупныхпроектах – это дополнительный плюс для вашего ре-зюме.

• Используйте все свободное время – ночи и вы-ходные дни. Если у вас появилось несколько минутили часов, займитесь разработкой любого приложе-ния – мобильного, настольного или веб-приложения –все пойдет вам в плюс. Выполняя такие проекты, выполучаете опыт. Старайтесь использовать новые тех-нологии, чтобы идти в ногу со временем. Обязательноупомяните эти проекты в резюме: люди, разрабатыва-ющие программы «ради собственного удовольствия»,производят хорошее впечатление на интервьюеров.

Компании хотят увидеть, что вы умны и что вы уме-ете программировать. Если вы можете это доказать,у вас больше шансов пройти собеседование.

Нужно заранее думать о развитии вашей карьеры– какой дорогой она должна пойти? Если вы собира-етесь идти по пути менеджмента, то, даже если в на-стоящий момент вы ищете вакансию разработчика,стремитесь развивать качества лидера.

Налаживаем связи

Наверняка вы слышали, что многие люди получают

работу «по знакомству». Скажу даже больше – неко-торые устраиваются на работу через друзей своихдрузей. И это просто прекрасно. Если у вас N друзей,то друзей друзей будет уже N2, то есть ваши шансыполучить работу существенно повышаются.

Это означает, что не только вы сами, но и ваш кругзнакомств оказывает влияние на ваш шанс найти ра-боту.

Правильный круг знакомств

Правильный круг знакомств должен быть достаточ-

но широк и в то же время он должен быть закрытым.Кажется, что эти два понятия не совместимы, поэто-му сначала рассмотрим, что такое «широкий и закры-тый» круг знакомств.

• Широкий круг знакомств означает, что все вашизнакомые и друзья имеют отношение не только к уз-кой области ваших интересов. Например, бухгалтерможет помочь вашей карьере, поскольку в его органи-зации (или у его знакомых) вполне может найтись ме-сто и для вас. Будьте открыты для общения с любым

человеком.• Закрытый – намного проще достучаться до чело-

века, который дружит с вашим близким другом, чемчерез абстрактное «шапочное» знакомство. Некото-рые люди даже коллекционируют визитные карточки– у них очень много контактов, но навряд ли они мо-гут назвать этих людей своими друзьями и знакомы-ми. Такой подход не поможет при поиске работы. Сде-лайте ваши связи более глубокими.

Постарайтесь найти баланс, не нужно «собиратькарточки» – этим вы ничего не добьетесь.

Как построить сильный

круг знакомств

Некоторые люди утверждают, что для знакомствадостаточно выйти и встретить человека. В какой-томере это правда. Но где такая встреча должна про-изойти? И как вы перейдете от простого знакомства кобщению?

Вам помогут несколько простых советов:1. Используйте Интернет. Сайты вроде

Meetup.com или социальные сети помогут вам отсле-живать события, связанные с областью ваших инте-ресов и вашими целями. Если у вас до сих пор нетсвоей визитной карточки – вы студент или безработ-

ный, – срочно решите эту задачу.2. Не бойтесь знакомиться с людьми. Вы волнуе-

тесь или стесняетесь? Не переживайте, от простого«здравствуйте!» хуже вам не станет. Что может про-изойти? Если человеку вы не понравитесь, он простоне станет с вами знакомиться, и вы его больше не уви-дите.

3. Будьте открыты, говорите о своих интересах.Если кто-то создает стартап или рассказывает что-тоинтересное для вас, пригласите его на чашечку кофе.

4. Отслеживайте события на LinkedIn или пригла-сите человека на чашку кофе, если его стартап пока-жется вам интересным.

5. Будьте доброжелательны – и это главное. Людизахотят помочь вам, если вы по

могли им. Помните: круг знакомств – это не тольколюди, с которыми вы знакомы лично. В наши дни кругзнакомств можно существенно расширить благодаряИнтернету – вам помогут блоги, Facebook и электрон-ная почта. Но не забывайте – если общение происхо-дит только онлайн, сложнее установить связь и полу-чить желаемое.

Идеальное резюме

Рекрутеры, просматривающие резюме, обращают

внимание на те же самые детали, что и интервьюеры.Они хотят понять, насколько вы умны и обладаете ливы навыками, необходимыми для желаемой должно-сти.

Это означает, что вам нужно сделать акцент в ре-зюме на «правильных» данных, и это будет не вашеувлечение теннисом, путешествиями или гаданием накофейной гуще. Подумайте, стоит ли сокращать ин-формацию технического характера, заменяя ее опи-санием разнообразных хобби.

Правильный размер

Обычно советуют не выходить за рамки одной стра-

ницы, если ваш опыт работы не превышает десятилет, или двух страниц, если вы более опытны. Почемутак? Вот основные причины:

• Рекрутеры тратят на одно резюме в среднем неболее 20 секунд. Если вы сократите размер и укаже-те в резюме только главные детали, их заметят. Боль-шое резюме – бессмысленная вещь, никто его не бу-дет внимательно читать.

• Некоторые люди просто отказываются чи-тать длинные резюме. Вы же не хотите, чтобы вашерезюме было отклонено?

Если вы думаете, что ваш обширный опыт невоз-можно описать на одной странице, поверьте мне, выпросто не пробовали уложиться на страницу. Огром-ное резюме еще не является доказательством опыт-ности претендента. Оно говорит лишь о том, что выне можете правильно расставить приоритеты при егонаписании.

Трудовой стаж

Ваше резюме не должно включать полную историю

вашей трудовой деятельности. То, что вы продавалимороженое, не характеризует ваш интеллект или та-ланты в написании программ. В резюме нужно вклю-чать только значимые позиции.

Указывайте толькозначимые позиции

Для каждой занимаемой вами должности необ-

ходимо добавить описание достижений: «При осу-ществлении X я добился Y, что привело к Z». Вотнесколько примеров:

• «Благодаря моей реализации распределенногокэша было достигнуто сокращение времени прори-совки на 75 %, что в свою очередь привело к сокра-щению времени входа в систему» на 10 %.

• «Благодаря использованию windiff при реализа-ции нового алгоритма сравнения средняя точностьсовпадений выросла с 1,2 до 1,5».

Конечно, не нужно пытаться формализовать все ва-ши достижения, но принцип, думаю, ясен. Нужно по-казать, что вы сделали, как вы сделали и какие ре-зультаты получены. В идеале вы должны сделать ва-ши достижения «измеряемыми».

Проекты

Раздел «Проекты» в вашем резюме – это лучший

способ продемонстрировать свойопыт. Наиболее важно это для учащихся или недав-

них выпускников. В список нужно включать по два-че-тыре самых существенных проекта. Опишите проект:на каком языке он был реализован, какие технологиибыли использованы. Необходимо упомянуть, был липроект индивидуальным или над ним работала целаякоманда. Все эти детали необязательны, но вы пред-станете в лучшем свете.

Не добавляйте слишком много проектов. Многие

кандидаты делают ошибку, перечисляя всё, чем ко-гда-либо занимались, забивая свое резюме неболь-шими, невпечатляющими проектами.

Языки программированияи программные продукты

Программные продуктыВообще-то говоря, я не рекомендую указывать в ре-

зюме умение работать с продуктами вроде MicrosoftOffice, – это должен знать каждый. Навыки работыс высокотехнологичными продуктами (Visual Studio,Linux) могут оказаться полезными, но, по большомусчету, и они не имеют решающего значения.

Языки программированияЗнание языков программирования – хитрая шту-

ка. Что перечислять? Все языки, на которых когда-ли-бо вам приходилось программировать, или только те,которые часто используете? Я советую перечислитьбольшинство языков, которыми вы владеете, но обя-зательно укажите свой уровень опыта, например:

• Языки программирования: Java (эксперт), C++(опытный), JavaScript (новичок).

Если английский – не ваш родной язык

Некоторые компании не станут рассматривать ва-ше резюме, если в нем будет много грамматическихошибок. Попросите кого-нибудь проверить ваше ре-зюме.

В резюме, отправляемом в американскую компа-нию, не нужно указывать возраст, семейное поло-жение и национальность. Это личная информация,которая создает трудности для компании, возлагаетна нее юридическую ответственность за конфиденци-альное хранение и обработку ваших данных.

Часть V. Подготовка к

поведенческим вопросам

Поведенческие вопросы

Поведенческие вопросы задают, чтобы оценить васкак личность, уточнить резюме или даже освободитьвас от собеседования. Так или иначе, эти вопросыважны и к ним следует подготовиться.

Как подготовиться

Поведенческие вопросы чаще всего формулируют-

ся в виде «Расскажите мне о времени, когда вы…»и могут затрагивать период жизни, когда вы работа-ли над определенным проектом или занимали опре-деленную должность. Я рекомендую подготовить и за-полнить специальную таблицу.

В шапке таблицы перечислите основные пункты ва-шего резюме: проекты, задания или другую деятель-ность. Перечислите общие вопросы: что вам большевсего нравилось или не нравилось, что вы посчиталиважным, чему научились, какая была самая серьез-ная ошибка и т. д. В каждой ячейке запишите соответ-ствующую историю.

На собеседовании, когда вас будут спрашивать окаком-либо проекте, вы без труда вспомните соответ-ствующий сюжет. Не забудьте взглянуть на эту табли-цу перед собеседованием.

Я рекомендую сократить каждую историю до парыслов, которые можно легко вписать в ячейку, это упро-стит вашу подготовку. Если вы проходите собеседова-ние по телефону, таблица должна быть перед вашимиглазами. Пары ключевых слов, записанных в каждойячейке, хватит, чтобы активировать вашу память, вы

легко и непринужденно сможете рассказать о любомпроекте, что существенно лучше, чем пытаться про-читать вслух написанный ранее абзац.

Иногда полезно расширить таблицу «мягкими» те-мами – конфликты в команде, сбои в работе или труд-ные моменты, когда вам нужно было кого-либо пере-убедить. Такие темы выходят за пределы обязанно-стей рядового программиста, но если вы претендуе-те на позицию ведущего программиста, PM или тесте-ра, я советую подготовить дополнительную таблицу,охватывающую эти темы.

Когда вы отвечаете на поведенческие вопросы, непытайтесь найти в памяти подходящую под вопрос си-туацию. Просто расскажите о себе, порассуждайте,как каждая история касалась лично вас.

Ваши слабые места

Когда вас спросят о слабых местах, расскажите о

самом слабом месте. Ответы «Мое самое слабое ме-сто – я трудоголик», заставят интервьюера думать,что вы слишком высокого мнения о себе или не хо-тите признаваться в своих слабостях. Никто не захо-чет работать с таким человеком. Лучший ответ – ска-зать правду, указать ваше настоящее слабое место,но продемонстрировать, что вы работаете и в скором

времени преодолеете свои недостатки. Например: «Ябываю не очень внимателен к деталям. В этом естьи хорошая сторона – я быстро выполняю задания, ноиногда все-таки делаю ошибки из-за невнимательно-сти. Именно поэтому я по нескольку раз проверяю по-лученный результат».

Что заставляет вас работать

Когда вам задают подобный вопрос, не нужно гово-

рить: «Я хотел выучить много новых языков програм-мирования и технологий». Этот ответ подойдет, толь-ко если вы действительно не знаете, что сказать. Ин-тервьюер сразу решит, что проект был не слишкомсложный.

Какие вопросы нужнозадавать интервьюеру

Большинство интервьюеров дают вам шанс задать

вопрос. Качество ваших вопросов,сознательно или подсознательно, повлияет на их

решение. Некоторые вопросы могут возникнуть вовремя собеседования, но некоторые вы должны (иможете) подготовить заранее. Изучите историю и об-ласть деятельности компании или команды – это по-

может вам подготовить свои вопросы.Вопросы можно разделить на несколько категорий.

Настоящие вопросыНа эти вопросы вы, скорее всего, хотите получить

ответы. Вот несколько вариантов, которые интереснымногим кандидатам:

1. Сколько времени ежедневно вы тратите на про-граммирование?

2. Сколько встреч вы проводите каждую неделю?3. Какое количественное соотношение между те-

стерами, разработчиками и менеджерами программ?Как они взаимодействуют? Как происходит планиро-вание проекта?

Эти вопросы помогут вам понять, как происходитежедневная работа в компании.

Проницательные вопросыЭти вопросы предназначены для демонстрации ва-

ших знаний программирования и технологий, а такжеговорят о вашем отношении к компании или продукту:

1. Я заметил, что вы используете технологию X. Каквы решаете проблему Y?

2. Почему продукт использует протокол X, а не Y? Язнаю, что такое решение обладает преимуществамиA, B, C, но много компаний отказываются от него из-

за проблемы D.Чтобы задать такие вопросы, нужно заранее иссле-

довать продукты компании.

«Фанатские» вопросыЭта категория вопросов позволяет продемонстри-

ровать ваше отношение к конкретной технологии. Онипоказывают, что вы заинтересованы в обучении и ком-пании:

1. Я очень интересуюсь темой масштабируемости.Посоветуйте, где можно узнать об этом?

2. Я не знаком с технологией X, но слышал, что этоочень интересное решение. Не могли бы вы мне рас-сказать, как она работает?

Ответы на поведенческие вопросы

Собеседования обычно начинаются и заканчивают-

ся непринужденной беседой. Это время, когда интер-вьюер может задать вопросы о вашем резюме, а выможете задать вопросы интервьюеру. Данная частьсобеседования позволяет лучше узнать вас, а вам да-ет возможность расслабиться.

Запомните несколько советов, они пригодятся, ко-гда вы отвечаете на вопросы.

Отвечайте четко, но без высокомерия

Высокомерие – это красная карточка, но вы же хо-

тите выглядеть достаточно внушительно. Как этогодобиться и не показаться высокомерным? Четко фор-мулируйте свои мысли! Рассмотрим пример:

• Кандидат 1: «Именно я делал всю самую слож-ную работу для команды».

• Кандидат 2: «Я занимался реализацией файло-вой системы – наиболее важный компонент, посколь-ку…» Кандидат 2 выглядит не только более внуши-тельным, но и менее высокомерным.

Сократите подробности до минимума

Когда кандидат много и долго рассказывает о про-

екте, интервьюеру, который, может быть, не оченьразбирается в предмете, трудно понять, о чем говориткандидат. Ограничьте подробности, оставьте толькоключевые пункты, сделайте рассказ легким для вос-приятия. Вот небольшой пример: «При исследованиинаиболее типичного поведения пользователей я при-менял алгоритм Рабина-Карпа и самостоятельно раз-работал новый алгоритм, который позволил сокра-тить время поиска с O(n) до O(log n) в 90 % случаев. Ямогу рассказать подробнее, если вам это интересно».Это демонстрирует ключевые моменты, но не утом-ляет интервьюера.

Структурируйте ответ

Существует два способа дать структурированный

ответ на поведенческий вопрос: «золотой самородок»и SAR. Эти две техники можно использовать как по-отдельности, так и вместе.

«Золотой самородок»

Техника «золотой самородок» предполагает, что высразу выкладываете перед интервьюером «саморо-док», который кратко описывает, о чем будет ваш от-вет. Например:

• Интервьюер: «Расскажите, был ли в вашей ка-рьере случай, когда вам приходилось убеждать лю-дей внести значительные изменения?»

• Кандидат: «Несомненно. Позвольте мне расска-зать, как я убедил администрацию колледжа разре-шить студентам вести собственные курсы. Изначаль-но в моей школе было правило, которое…»

Эта техника позволяет вам захватить внимание ин-тервьюера, а ему – мгновенно понять, о чем будетваш рассказ. Вы сразу демонстрируете свои коммуни-кативные навыки.

SARТехника SAR (Situation, Action, Result – ситуация,

действие, результат) подразумевает, что вы должнысначала обрисовать ситуацию, затем объяснить своидействия и, наконец, описать результат.

Пример: «Расскажите мне о взаимодействии с кол-легами по команде».

Ситуация: При работе над операционной системоймне довелось работать вместе с тремя коллегами.Два человека были превосходны, а вот о третьем я та-

кого сказать не могу. Он был замкнутым, редко участ-вовал в обсуждениях и изо всех сил пытался избежатьдискуссий.

Действие: Однажды после лекции я отвел его всторону, чтобы поговорить о курсе, а потом плавно пе-решел к разговору о проекте. Сразу выяснилось, чтоон – стеснительный человек и ему не хватает уверен-ности в своих силах. При дальнейшей совместной ра-боте я учел этот факт и стал его хвалить, чтобы под-нять его самооценку.

Результат: Хотя этот человек оставался слабымзвеном в команде, но он стал работать намного луч-ше. Он делал всю возложенную на него работу и при-нимал участие в обсуждениях проекта. Я считаю, чтоу нас получилась настоящая командная работа надпроектом.

Описания ситуации и результата должны бытьочень краткими. Ваш интервьюер не нуждается в из-быточных подробностях. При использовании моделиSAR интервьюер легко понимает, какой была ситуа-ция, каковы ваши действия и что получилось в резуль-тате.

Часть VI. Технические вопросы

Подготовка

Если вы купили эту книгу, то, скорее всего, уже про-делали достаточно долгий путь к вершине отличнойтехнической подготовки. Поздравляю, прекрасная ра-бота! Но существуют как лучшие, так и худшие спо-собы подготовки. Многие кандидаты считают, что до-статочно просмотреть задачи и готовые решения. Этов чем-то похоже на попытку научиться считать, читаякниги. Но если вы хотите научиться решать задачи,запоминание готовых решений не поможет.

Как организовать подготовку

Для каждой задачи из этой книги:• Попытайтесь решить задачу самостоятельно .

Я имею в виду действительно попытаться решить за-дачу. Вам встретится множество сложных заданий –и это нормально. Когда вы решите задачу, подумайтеоб эффективности использования пространства (па-мяти) и времени выполнения. Задайтесь вопросом,можно ли ускорить выполнение программы, оптими-

зируя использование памяти, и наоборот.• Запишите код алгоритма на бумаге. Вы всю

жизнь программировали на компьютере, и это, без-условно, хорошо. Но на собеседовании вам не помо-жет ни подсветка синтаксиса, ни автозавершение ко-да, ни компиляция. Сымитируйте условия собеседо-вания, записывая код на бумаге.

• Протестируйте свой код. Представьте, что вы –компилятор, проверьте код на наличие ошибок. Вампридется это делать на собеседовании, поэтому луч-ше подготовиться заранее.

• Введите написанный код в компьютер «какесть», возможно, вы обнаружите множество ошибок.Проанализируйте все ошибки и сделайте все, чтобына настоящем собеседовании их не допустить.

Очень полезны псевдоинтервью. НаCareerCup.com вы найдете примеры псевдоинтервьюс сотрудниками Microsoft, Google, Amazon – исполь-зуйте их, когда будете практиковаться с друзьями. Хо-тя ваши друзья не являются профессиональными ин-тервьюерами, они в состоянии проверить решения за-дач на программирование и алгоритмизацию.

Что нужно знать

Большинство интервьюеров не будут задавать во-

просы о конкретных алгоритмах балансировки двоич-ного дерева или других сложных алгоритмах. Честноговоря, они сами их уже забыли, ведь такие вещи за-бываются сразу после окончания учебы.

Вам нужно знать основы.

18

Убедитесь, что вы понимаете, как использовать иреализовывать каждую из задач, знаете их областьприменения, эффективность использования памяти ивремя выполнения. Вам могут задать вопрос по темеиз таблицы или попросить реализовать какую-либо еемодификацию.

8 Про «О-большое» можно прочитать в Википедии http://ru.wikipedia.org/wiki/ «O»_большое_и_ «o»_малое. – Примеч. ред.

Обратите внимание на хэш-таблицы – это наибо-лее важная тема. Она часто встречается на собесе-дованиях.

Таблица степеней двойки

Некоторые люди помнят ее как таблицу умножения,

если вы не относитесь к их числу, вам нужно подго-товиться. Таблица степеней двойки пригодится в за-дачах масштабируемости – в расчетах необходимогообъема памяти для набора данных.

Используя эту таблицу, вы можете легко рассчи-тать, например, хватит ли имеющегося объема памя-ти для хэш-таблицы, отображающей каждое 32-бит-ное число в булевое значение.

Если вы проходите телефонное собеседование в

веб-ориентированной компании, полезно держать этутаблицу перед глазами.

Нужно ли знать все о

программировании на C++, Java или других языках

Хотя я лично никогда не любила вопросы такого ро-

да (например: «Что такое vtable?»), многие интервью-еры действительно их задают. В крупных компаниях– Microsoft, Google, Amazon и других – таким вопро-сам не уделяется слишком много внимания. Вы долж-ны понимать основные концепции языка, которым вывладеете, но лучше сфокусироваться на структурахданных и алгоритмах.

В то же время для небольших компаний вопросы,связанные с языками программирования, могут бытьочень важны. Поищите компанию, в которой собира-етесь проходить собеседование, на CareerCup.com.Если вашей компании там нет, поищите аналогичнуюкомпанию. Большинство стартапов проверяют навы-ки именно «их» языка программирования.

Ответы на технические вопросы

Собеседование не может быть простым. Если вам

не удается дать ответ «с ходу» – это нормально! Толь-ко десять из более чем ста двадцати человек смоглибыстро разобраться в моих любимых задачах.

Если вам достался сложный вопрос, не нужно пани-ковать. Начните с планирования решения – покажитеинтервьюеру, что вы не застряли.

Запомните еще одно правило – вы не должны оста-навливаться, пока интервьюер не скажет, что реше-ние закончено. Что я имею в виду? Если вы уже при-думали алгоритм, продолжите рассуждать о возмож-ных ошибках в его работе. Если вы пишете программ-ный код, попытайтесь найти в нем ошибки. Если выотноситесь к числу тех самых 110 кандидатов, у вас,вероятно, будут ошибки.

Пять шагов к решению

Любую техническую задачу на собеседовании мож-

но решить за пять шагов:1. Задайте интервьюеру вопросы, чтобы снять

неоднозначности.2. Разработайте алгоритм.3. Запишите псевдокод, но сообщите интервьюеру,

что вы намерены написать решение на конкретномязыке программирования.

4. В умеренном темпе начните писать программныйкод.

5. Проверьте написанную программу и вниматель-но исправьте ошибки. Остановимся на каждом шагепоподробнее.

Шаг 1. Задайте вопросы

Технические задачи более неоднозначны, чем мо-

жет показаться на первый взгляд, убедитесь, что вамясна суть вопроса. Задача может оказаться намногопроще, чем казалась в начале. Некоторые интервью-еры (в частности, в Microsoft) специально проверяют,поняли ли вы задачу.

Вот несколько примеров хороших вопросов: какие

типы данных используются? Какие объемы данныхбудут использоваться? Какие исходные предположе-ния нужны для решения? Кто будет пользователем?

Задача: «Разработайте алгоритм сортировкисписка»

Вопрос: Какой список нужно сортировать? Массив?Связный список?

Ответ: Массив.Вопрос: Что будет в массиве? Числа? Символы?

Строки?Ответ: Числа.Вопрос: Числа будут целыми?Ответ: Да.Вопрос: Что представляют собой эти числа? Это

идентификаторы? Значение чего-либо?Ответ: Это возраст клиентов.Вопрос: Сколько будет клиентов?Ответ: Миллион.

Теперь постановка задачи изменилась: нужно от-сортировать массив из миллиона целых чисел в диа-пазоне от 0 до 130 (максимально возможный возраст).Как ее решить?

Достаточно создать массив из 130 элементов и по-считать количество значений для каждого возраста.

Шаг 2. Разработайте алгоритм

Разработайте алгоритм, но при этом помните о пя-

ти подходах алгоритмизации (см. следующий раздел).Пока вы обдумываете алгоритм, не забудьте ответитьна вопросы:

• Сколько памяти и времени понадобится для реа-лизации этого алгоритма?

• Что произойдет, если данных будет больше, чемзапланировано?

• Какие проблемы могут возникнуть в процессе ра-боты вашего алгоритма? Например, если вы создае-те модификацию бинарного дерева поиска, как вашалгоритм повлияет на время вставки, поиска и удале-ния?

• Какие компромиссные решения возможны с уче-том существующих ограничений? Для каких сцена-риев компромиссное решение будет наименее опти-мальным?

• Нужна ли дополнительная исходная информация(в нашем случае – возраст клиентов или порядок сор-тировки) для реализации алгоритма? Обычно интер-вьюер специально предоставляет вам дополнитель-ную информацию.

Метод грубой силы – вполне приемлемый и даже

рекомендованный путь. После его разработки вы мо-жете провести оптимизацию. Рано или поздно вы при-дете к оптимальному решению, но это не означает,что оно будет первым пришедшим в голову.

Шаг 3. Псевдокод

Псевдокод поможет в общих чертах набросать ва-

ши соображения и избежать большей части ошибок.Но не забудьте сообщить интервьюеру, что сейчас выпишете псевдокод, а затем перейдете к языку про-граммирования. Много кандидатов используют псев-докод, чтобы избежать написания программы, но выже не хотите быть одним из них?

Шаг 4. Код

Не нужно торопиться, чтобы потом не было мучи-

тельно больно. Пишите программный код спокойно иаккуратно. Запомните советы:

• Используйте структуры данных везде, где этовозможно; выберите подходящую структуру данныхили разработайте собственную. Например, если васпросят определить минимальный возраст группы лю-дей, можно создать специальную структуру данных –Person. Этим вы покажете интервьюеру, что способны

создать хороший объектно-ориентированный проект.• Не создавайте очень длинные программы. Когда

вы записываете свой код на доске, начинайте с верх-него левого угла, а не с середины, чтобы ответ поме-стился целиком.

Шаг 5. Проверка

Вам нужно протестировать код. В первую очередь

обратите внимание на следующие моменты:• экстремальные случаи – 0, отрицательное значе-

ние, null, максимумы, минимумы;• ошибки пользователя – что случится, если поль-

зователь передаст null или отрицательное значение;• общие случаи – протестируйте типовое поведение

программы.Если алгоритм сложный или исключительно чис-

ленный (смещение, булева алгебра и т. д.), тестируй-те код по мере написания, а не по завершении рабо-ты.

Если вы находите ошибки (а они будут), не торопи-тесь их исправлять – попытайтесь найти причину ихвозникновения. Вы же не хотите стать одним из канди-датов, который, обнаруживая, что функция возвраща-ет trueвместо false, просто инвертирует ее значение.Это устранит ошибку в конкретном случае, но неиз-

бежно породит новые.Работая над ошибками, задумайтесь, почему код

перестал работать. Это поможет написать красивыйи чистый код намного быстрее.

Пять подходов к алгоритмизации

Не существует универсального суперспособа, ре-

шающего любую задачу алгоритмизации, но приве-денные далее подходы могут оказаться полезны.Помните: чем больше задач вы решите, тем прощебудет выбрать подходящий способ.

Пять способов, приведенных далее, можно исполь-зовать по отдельности или вместе.

Попробуйте подход «Упростить и обобщить», а за-тем перейдите к «Сопоставлению с образцом».

Подход 1. Приводим пример

Мы начнем со способа, с которым вы, вероятно,

знакомы, даже если никогда не обращали на него вни-мания. Напишите несколько примеров задачи, и выувидите, можно ли получить общее правило из них.

Пример: задано время, нужно рассчитать уголмежду часовой и минутной стрелками.

Давайте начнем, пусть исходное время – 3:27. Мыможем нарисовать циферблат, установить часовуюстрелку на 3 часа, а минутную – на 27 минут.

Введем следующие обозначения: h – это часы, m– минуты. Предположим, что h может принимать зна-чения в диапазоне от 0 до 23 включительно. Теперьможно сформулировать следующие правила:

• угол между минутной стрелкой и «полуднем»: 360* m / 60;

• угол между часовой стрелкой и «полуднем»: 360 *(h % 12) / 12 + 360 * (m / 60) * (1 / 12);

• угол между часовой стрелкой и минутной: (угол ча-совой стрелки – угол минутной стрелки) % 360.

Окончательное выражение можно упростить до 30h– 5.5m.

Подход 2. Сопоставление с образцом

«Сопоставление с образцом» подразумевает, что

мы сравниваем задачу с подобной и пытаемся при-способить алгоритм для нашего случая.

Пример. Отсортированный массив был цикличе-

ски сдвинут так, что элементы оказались в следу-ющем порядке: 3 4 5 6 7 1 2. Как найти минимальныйэлемент? Вы можете исходить только из предпо-ложения, что элементы в массиве не повторяются.

Существуют две задачи, которые можно рассмат-ривать как аналог:

• Поиск минимального элемента в массиве.• Поиск определенного элемента в сортированном

массиве (бинарный поиск).Поиск минимального элемента в массиве не самый

интересный алгоритм – нужно пройтись по всем эле-ментам. Вряд ли он будет полезен.

А вот бинарный поиск можно использовать. Вы зна-ете, что массив был отсортирован, а затем цикличе-ски сдвинут. Поэтому значения увеличиваются, а за-тем сбрасываются в исходную точку и снова растут.Минимальный элемент оказывается в точке сброса.

Если вы сравните средний и последний элементы(6 и 2), то узнаете, что точка сброса должна находить-ся между этими значениями (MID > RIGHT). Но это мо-жет произойти, только если массив сбрасывался меж-ду данными значениями.

Если MID меньше, чем RIGHT, значит, точка сбросанаходится в левой части массива, либо точки сбросане существует (массив отсортирован). Так или иначе,минимальный элемент находится там.

Мы можем использовать этот подход, деля массивпополам, подобно алгоритму бинарного поиска, и, вконечном счете, найдем минимальный элемент (илиточку сброса).

Подход 3. Упростить и обобщить

Этот алгоритм подразумевает многошаговый под-

ход. Во-первых, мы изменяем ограничение (тип дан-ных или количество исходных данных), чтобы упро-стить задачу. Затем мы решаем упрощенную версиюзадачи. Как только алгоритм для упрощенной задачиполучен, мы обобщаем ее и пытаемся приспособитьполученное решение к более сложной версии.

Пример. Требование о выкупе было склеено извырезанных из газеты отдельных слов. Как прове-рить, что требование о выкупе (представленное ввиде строки) было сделано с использованием кон-кретной газеты (строки)?

Для упрощения задачи предположим, что из газетывырезались отдельные буквы, а не слова.

Чтобы решить упрощенную задачу, создадим мас-сив и подсчитаем символы. Каждый элемент массивасоответствует одной букве. Сначала мы подсчитыва-ем, сколько раз повторяется каждый знак в требова-нии о выкупе, а затем проверяем, есть ли в газете все

эти символы.При обобщении алгоритма используется тот же

подход. Только вместо создания массива с количе-ством символов можно создать хэш-таблицу, котораясопоставляет слова с частотой их использования.

Подход 4. Базовый

случай и сборка решения

Данный метод идеально подходит для решения це-лого ряда задач. Мы можем решить задачу для базо-вого случая (n = 1). Это обычно означает запись кор-ректного результата. Затем решить задачу для n=2,учитывая, что ответ для n=1 уже найден. Затем за-няться случаем n=3, учитывая, что ответы для n=1 иn=2 известны.

В итоге мы можем построить решение, которое поз-волит найти результат для N, если известен правиль-ный результат для N– 1. Каждый раз наше решениеосновывается на предыдущем результате.

Пример. Разработайте алгоритм для выводавсех возможных перестановок символов в строке(считайте, что все символы используются толькоодин раз).

Дана тестовая строка – abcdefg.

Случай "a" – > {"a"}Случай "ab" – > {"ab", "ba"}Случай "abc" – >?Вот и первый «интересный» случай. Можем ли мы

сгенерировать P("abc"), если у нас есть ответ P("ab")?Итак, у нас появляется дополнительная буква («c») инам нужно вставить ее во все возможные позиции.

P("abc") = вставить "c" во все позиции для всехстрок

P("ab") P("abc") = вставить "c" во все позиции длявсех строк {"ab","ba"}

P("abc") = соединить ({"cab", "acb", "abc"}, {"cba","bca", bac"})

P("abc") = {"cab", "acb", "abc", "cba", "bca", bac"}Мы разобрались с шаблоном и можем разработать

общий рекурсивный алгоритм. Сгенерируйте все пе-рестановки строки s1…sn, удалив последний символ(для s1…sn-1).

Получив список всех перестановок s1…sn-1, после-довательно пройдитесь по каждому элементу-строкесписка, добавляя символ sn в каждую позицию строки.

Данный подход позволяет создавать рекурсивныеалгоритмы.

Подход 5. Мозговой

штурм структур данных

Данный способ трудно назвать идеальным, но за-частую он срабатывает. Мы просто проходим по спис-ку структур данных и пытаемся использовать каждуюиз них. Данный подход может оказаться полезным,поскольку в некоторых случаях решение задачи, чтоназывается, «появится на поверхности», как толькобудет выбрана правильная структура данных (напри-мер, дерево).

Пример. Была сгенерирована и сохранена в мас-сив последовательность случайных чисел. Как най-ти медиану?

Пытаемся устроить мозговой штурм и подобратьадекватную структуру данных:

• Связный список? Вероятно, нет. Связные спискиплохо подходят для сортировки.

• Массив? Может быть, но у нас уже есть мас-сив. Как хранить в нем отсортированные элементы?Это довольно сложно. Давайте отложим эту структуруданных и вернемся к ней при необходимости.

• Бинарное дерево? Вполне возможно, бинарныедеревья подходят для задач сортировки. Мы можем

попробовать усовершенствовать дерево бинарногопоиска, а вершина будет медианой. Но будьте осто-рожны: число элементов может оказаться четным, амедиана окажется между двумя средними элемента-ми. Два средних элемента не могут оказаться на вер-шине одновременно. Возможно, этот алгоритм подой-дет, мы вернемся к нему позже.

• Куча? Куча – отличный способ для сортировки иотслеживания максимальных и минимальных значе-ний. Это интересный выбор. Если у вас будет две ку-чи, можно следить за «большими» и «меньшими» ча-стями элементов. «Большая» половина находится вmin-куче, так что самый маленький элемент оказыва-ется в вершине, а «меньшая» половина – в max-ку-че, так что в вершине – наибольший элемент. Такиеструктуры данных позволяют вам найти потенциаль-ные медианы. Если размер куч изменился, можно по-вторно провести балансировку, выталкивая элементыиз одной кучи в другую.

Обратите внимание, что множество задач легко ре-шаются, если правильно выбрать структуры для ис-пользуемых данных. Теперь вам нужно понять, какойподход более применим к той или иной задаче.

Как выглядит хороший код

Вы, возможно, неоднократно слышали, что работо-

датели хотят видеть «хороший» и «чистый» код. Ночто это такое и как продемонстрировать его на собе-седовании? О хорошем коде всегда можно сказать,что он:

• правильный: код корректно обрабатывает всекорректные и некорректные входные данные;

• эффективный: код максимально эффективен сточки зрения времени и пространства (памяти). Эф-фективность включает асимптотическую («О-боль-шое») и практическую (реальную) эффективность.При расчете зависимости времени выполнения про-граммы от ее сложности постоянный коэффициентможно отбросить, но в реальной жизни он может ока-зать влияние на эффективность;

• простой: если вы можете реализовать алгоритмв десяти строках, не пишите сто. Создайте код макси-мально быстро;

• читаемый: другой разработчик должен прочитатьваш код и понять, что и как делается. Для читаемогокода необходимы комментарии, они делают код болеепонятным. Сдвига строк недостаточно;

• обслуживаемый: код должен легко адаптиро-

ваться к изменениям, которые возникают на протяже-нии жизненного цикла продукта, он должен обслужи-ваться другими программистами так же легко, как иразработчиком.

Следование всем этим правилам требует опреде-ленных компромиссов. Например, стоит принести вжертву немного эффективности, но сделать код болееудобным в сопровождении и наоборот.

Вы должны думать обо всех этих аспектах, когда пи-шете программный код на собеседовании.

Структуры данных

Предположим, что вас попросили написать функ-

цию, выполняющую сложение двух простых полино-мов, представленных в виде Axa+Bxb+…. Интервьюерне хочет, чтобы вы делали парсинг строк, ему нужно,чтобы вы использовали структуру данных, способнуюхранить полином.

Есть много разных способов решить такую задачу.

Неудачная реализацияПлохая реализация подразумевает хранение поли-

нома в виде массива чисел с двойной точностью, гдеk-й элемент соответствует элементу xk. Такая струк-тура может стать причиной ошибок при необходимо-

сти представить полином, содержащий отрицатель-ные или дробные степени. Кроме того, для храненияполинома, содержащего только один член x1000, по-требуется массив из 1000 элементов.

1 int[] sum(double[] poly1, double[] poly2) {2…3 }

Чуть лучшая реализацияЧуть лучшая реализация подразумевает хранение

полинома в двух массивах – coefficients и exponents.Полином в этом случае может храниться в любомпорядке, но i-й член полинома должен иметь видcoefficients[i] *xexponents[i].

Таким образом, если coefficients[p] =k и exponents[p]=m, то p-й член будет равен kxm.

Хотя данная реализация не имеет таких ограниче-ний, как предыдущее решение, она все еще далека отидеала. Мы должны использовать пару массивов длякаждого полинома. Если массивы будут разной дли-ны, то в полиноме оказываются «неопределенные»значения. Да и результат будет не очень удобным, таккак при вызове функция будет возвращать два масси-ва.

1??? sum(double[] coeffs1, double[] expon1,

2 double[] coeffs2, double[] expon2) {3…4 }

Хорошая реализацияХорошая реализация – разработка собственной

структуры данных для хранения полинома.1 class PolyTerm {2 double coefficient; 3 double exponent;4 }56 PolyTerm[] sum(PolyTerm[] poly1, PolyTerm[] poly) {7…8 }Кое-кто будет утверждать, что это «сверхоптимиза-

ция». Возможно, да, а возможно – нет. Независимо отвашего мнения, это решение продемонстрирует, чтовы думаете о коде и не пытаетесь решить задачу са-мым простым (и самым быстрым) способом.

Обоснованное многократное

использование кода

Предположим, что вас попросили написать функ-цию, проверяющую на равенство двоичное и шестна-дцатеричное представление числа, хранимое в виде

строки. Изящная реализация этой задачи подразуме-вает повторное использование кода:

1 public boolean compareBinToHex(String binary,String hex) {

2 int n1 = convertToBase(binary, 2);3 int n2 = convertToBase(hex, 16);4 if (n1 < 0 || n2 < 0) {5 return false;6 } else {7 return n1 == n2;8 }9 }1011 public int digitToValue(char c) {12 if (c >= '0' && c <= '9') return c – '0';13 else if (c >= 'A' && c <= 'F') return 10 + c – 'A';14 else if (c >= 'a' && c <= 'f') return 10 + c – 'a';15 return -1;16 }1718 public int convertToBase(String number, int base) {19 if (base < 2 || (base > 10 && base!= 16)) return -1;20 int value = 0;21 for (int i = number.length() – 1; i >= 0; i-) {22 int digit = digitToValue(number.charAt(i));23 if (digit < 0 || digit >= base) {

24 return -1;25 }26 int exp = number.length() – 1 – i;27 value += digit * Math.pow(base, exp);28 }29 return value;30 }Возможно, вы смогли бы написать отдельный код,

преобразующий двоичное число в шестнадцатерич-ное, но это сделает нашу программу более гро-моздкой и тяжелой в обслуживании. Поэтому мыиспользуем код повторно, вызывая общие методыconvertToBase и digitToValue.

Модульность

Написание модульного кода подразумевает выде-

ление изолированных блоков программы в отдельныеметоды. Это делает код более удобным, читаемым итестируемым.

Допустим, что вам нужно написать код, меняющийместами минимальный и максимальный элементы вцелочисленном массиве. Эту задачу можно реализо-вать в одном методе.

1 public void swapMinMax(int[] array) {2 int minIndex = 0;

3 for (int i = 1; i < array.length; i++) {4 if (array[i] < array[minIndex]) {5 minIndex = i;6 }7 }89 int maxIndex = 0;10 for (int i = 1; i < array.length; i++) {11 if (array[i] > array[maxIndex]) {12 maxIndex = i;13 }14 }1516 int temp = array[minIndex];17 array[minIndex] = array[maxIndex];18 array[maxIndex] = temp;19 }Но эту же задачу можно решить с использованием

модульного кода, выделив относительно изолирован-ные блоки кода в отдельные методы.

1 public static int getMinIndex(int[] array) {2 int minIndex = 0;3 for (int i = 1; i < array.length; i++) {4 if (array[i] < array[minIndex]) {5 minIndex = i;6 }

7 }8 return minIndex;9 }1011 public static int getMaxIndex(int[] array) {12 int maxIndex = 0;13 for (int i = 1; i < array.length; i++) {14 if (array[i] > array[maxIndex]) {15 maxIndex = i;16 } 17 }18 return maxIndex;19 }2021 public static void swap(int[] array, int m, int n) {22 int temp = array[m];23 array[m] = array[n];24 array[n] = temp;25 }2627 public static void swapMinMaxBetter(int[] array) {28 int minIndex = getMinIndex(array);29 int maxIndex = getMaxIndex(array);30 swap(array, minIndex, maxIndex);31 }Немодульный код не так уж и плох, но модульный

код значительно легче протестировать, так как каж-

дый его компонент можно проверить по отдельности.Чем код сложнее, тем оправданнее его модульность.Такой подход облегчит чтение и поддержку кода. Вашинтервьюер хочет увидеть, насколько вы владеетеэтими навыками.

Гибкость и надежность

Когда интервьюер просит написать код для провер-

ки игрового поля для игры в крестики-нолики, это ещене означает, что доска имеет размер 3×3. Почему бысразу не написать универсальный код для доски про-извольного размера N×N?

Гибкий и универсальный код предполагает исполь-зование констант вместо переменных или шабло-нов/обобщений, позволяющих решить задачу. Еслимы можем написать код, решающий задачу в общемвиде, мы должны это сделать.

Конечно, всему есть предел. Если решение для об-щего случая оказывается слишком сложным и гро-моздким, то лучше ограничиться простым случаем,который фигурирует в задании.

Проверка

Отличительной чертой предусмотрительного про-

граммиста является то, что он не делает предполо-жений о входных данных. Вместо этого он проверяетвведенную последовательность с помощью операто-ров ASSERT или if. Вернемся к написанному ранеекоду, преобразующему числа из системы счисленияпо основанию i (двоичной или шестнадцатеричной си-стемы) в целое число (int).

1 public int convertToBase(String number, int base) {2 if (base < 2 || (base > 10 && base!= 16)) return -1;3 int value = 0;4 for (int i = number.length() – 1; i >= 0; i-) {5 int digit = digitToValue(number.charAt(i));6 if (digit < 0 || digit >= base) {7 return -1;8 }9 int exp = number.length() – 1 – i;10 value += digit * Math.pow(base, exp);11 }12 return value;13 }В строке 2 мы проверяем, корректно ли выбрана си-

стема счисления (если основание больше 10, то этошестнадцатеричная система). В строке 6 мы произво-дим еще одну проверку: нужно убедиться, что каждаяцифра находится в пределах допустимого диапазона.

Подобные проверки очень важны в реальных про-

граммах, а значит, их оценят и на собеседовании. Ко-нечно, проверка ошибок – утомительное занятие и насобеседовании отнимает много драгоценного време-ни. Но вам важно продемонстрировать свое умениесделать обработку ошибок. Если требуемая проверкана ошибки оказывается сложнее, чем оператор if, луч-ше оставить свободное место на листке и сказать ин-тервьюеру, что собираетесь заполнить его кодом про-верки ошибок, когда закончите основную часть про-граммы.

Часть VII. Жизнь

после собеседования

Реакция на предложение и на отказ

Стоит только вам подумать, что после собеседо-вания можно расслабиться, как на вас обрушивают-ся новые переживания и волнения. Должны ли вы со-гласиться с предложением? Правилен ли ваш выбор?Как отказаться от работы? Есть ли время для при-нятия решения? Сейчас мы поговорим о некоторыхтонкостях, которые позволят вам оценить и обсудитьпредложение.

Сроки принятия решения

Когда компания делает предложение, практически

всегда оговаривается срок принятия решения, обычноон составляет 4 недели. Если вы ожидаете предложе-ний от других компаний, то можете попросить немно-го увеличить эти временные рамки. Обычно, если этовозможно, компании идут навстречу.

Вы отказываетесь от работы

Форма, в которой вы отказываетесь от предложе-

ния, имеет очень большое значение. Даже если рабо-та в этой компании на данный момент вам не интерес-на, возможно, спустя несколько лет вам захочется по-работать в ней. В ваших интересах сформулироватьотказ так, чтобы остаться с компанией в хороших от-ношениях.

Обязательно объясните причину отказа. Если выотклоняете предложение крупной компании в пользустартапа, то объясните, что на данный момент вы чув-ствуете: стартап для вас более правильный выбор.Большая компания не может превратиться в стартап,поэтому они без обид согласятся с вашей аргумента-цией.

Вам отказали

Крупные IT-компании отклоняют 80 % кандидатов

по причине недостаточного профессионализма оных.Зачастую позднее те же компании инициируют по-вторное собеседование с ранее отклоненным претен-дентом.

Воспринимайте неприятный звонок как временную

неудачу, а не как приговор. Поблагодарите своего ре-крутера за потраченное время, объясните, что выразочарованы, но понимаете их позицию, и поинтере-суйтесь, когда можно будет пройти собеседование по-вторно.

Причины отказа не всегда понятны. Рекрутеры врядли озвучат истинную причину, но наверняка вашишансы могли быть выше, если бы вы лучше подгото-вились, поэтому вместо поиска причины отказа сфо-кусируйтесь на подготовке. Вы можете проанализи-ровать причину, но мой опыт говорит, что кандидатыочень редко могут должным образом оценить свои ре-зультаты. Вы предполагаете, что превосходно отве-тили на вопросы, но все относительно. Помните, чтобольшинство отказов происходит из-за недостаточ-ных навыков программирования и алгоритмизации,поэтому сфокусируйтесь на этом.

Вам сделали предложение

Поздравляю, вы получили предложение о работе!

А если вы счастливчик, то, возможно, даже получилинесколько предложений. Задача вашего рекрутера –убедить вас принять его предложение. Но достойнали вас эта компания? Давайте оценим.

Финансовый пакет

Наибольшая ошибка при оценке компании, которую

допускают люди, заключается в том, что они смотрят впервую очередь на зарплату. Кандидат видит эти ма-гические цифры и принимает предложение, котороеоказывается не самым лучшим в финансовом плане.Зарплата – это только верхушка айсберга вашей фи-нансовой компенсации. Не забудьте, что еще суще-ствуют:

• премии, оплата переезда и всевозможные льго-ты. Многие компании выплачивают премии и предла-гают своим сотрудникам всевозможные льготы. Когдавы оцениваете компанию, не забудьте подсчитать этибонусы, беря в расчет как минимум три года (или срок,который вы планируете работать в этой компании);

• стоимость проживания (местный прожиточный

минимум). Если вы получили несколько предложенийиз разных городов, не упускайте из виду стоимостьпроживания. Например, жизнь в Силиконовой Доли-не обойдется на 20–30 % дороже, чем в Сиэтле (втом числе из-за десятипроцентного Калифорнийскогоналога). Используйте онлайн-ресурсы, чтобы оценитьэтот фактор;

• ежегодная премия. Ежегодная премия в IT-компа-нии может варьироваться от 3 до 30 %. Ваш рекрутерможет сообщить вам такую информацию, но если онотказывается, поищите знакомых, работающих в этойкомпании;

• фондовые опционы и гранты. Акции являютсябольшей частью ежегодной компенсации. Подобнольготам и премиям, расчет фондовой компенсациинужно производить в расчете на три года, затем полу-ченное значение добавлять к вашей зарплате.

Тем не менее помните, что также нужно учитыватьперспективы карьерного роста, а это может иметьбольшее значение для ваших долгосрочных финансо-вых планов, чем зарплата. Думайте прежде, чем де-лать ставку на озвученную заработную плату.

Карьерный рост

Вы несколько взволнованы, поскольку вам только

что сделали заманчивое предложение, но навернякауже через несколько лет вы будете снова готовиться ксобеседованию. Именно поэтому очень важно, чтобывы подумали уже сейчас о том, как это предложениеповлияет на вашу карьеру. Задайте себе следующиевопросы:

• Насколько хорошо будет выглядеть название ком-пании в моем резюме?

• Как я буду учиться? Чему я научусь?• Есть ли у меня перспективы? Как развивается ка-

рьера разработчика?• Если я собираюсь получить управленческую

должность, подходит ли для этого данная компания?• Каковы перспективы роста у этой компании (или

команды)?• Если я захочу уйти из компании – есть ли непода-

леку офисы других интересныхкомпаний или мне опять придется переезжать? По-

следний пункт очень важен, но обычно его упуска-ют из виду. Если вы будете работать на Microsoft вКремниевой долине и захотите уйти, то легко сможетеустроиться

в любую другую компанию. Но если вы будете рабо-тать на Microsoft в Сиэтле, то будете ограничены толь-ко Google, Amazon и немногочисленными небольши-ми компаниями. Если вы работаете в AOL в Далла-

се, ваши возможности по переходу в другую компаниюеще более ограничены. У вас просто не будет выбо-ра – если в городе нет других IT-компаний, вы будетевынуждены или остаться, или готовиться к переезду.

Стабильность компании

Тут все зависит от случая, но я не рекомендую за-

цикливаться на этом аспекте. Если вам придется уй-ти, то вы без проблем найдете работу в аналогичнойкомпании. Ответьте сами себе: что произойдет, есливас уволят? Каковы ваши перспективы найти новуюработу?

Удовольствие от работы

Наконец, вы должны понять, насколько счастливы

вы будете в этой компании. На это могут повлиять сле-дующие факторы:

• Продукт. Если вам нравится разрабатываемыйпродукт – это замечательно, но для инженера суще-ственно важнее другой фактор – команда, в которойприходится работать.

• Руководство и коллеги. Когда люди говорят, чтоим нравится или не нравится работа, их мнение ча-сто формируется под влиянием коллектива и руковод-

ства. Вы встречались с этими людьми? Вы сможете сними работать?

• Корпоративная культура. Культура компанииохватывает всё – от процедуры принятия решений допсихологической атмосферы и структуры компании.Поговорите об этом с будущими коллегами.

• Рабочий график. Ознакомьтесь с рабочим графи-ком и нагрузкой группы, к которой вы собираетесьпримкнуть. Помните, что нагрузка в условиях цейтно-та (deadline) обычно гораздо выше стандартной.

Дополнительно выясните, возможен ли переход изодной команды в другую (как, например, в Google).Сможете ли вы найти команду, в которой вам будеткомфортно?

Переговоры

В конце 2010 года я прошла специальный курс, по-

священный ведению переговоров. В первый день пре-подаватель попросил, чтобы мы представили, что хо-тим купить автомобиль. Дилер А продает автомобильза $20 000, а вот с дилером Б можно поторговаться.Какой должна быть скидка, чтобы вы обратились к ди-леру Б? (Ответьте быстро, не задумываясь.)

Большинство слушателей решили, что их устрои-ла бы скидка в $750. Другими словами, они были со-гласны торговаться час, чтобы сэкономить всего лишь$750. Неудивительно, что большинство студентов немогли вести переговоры с работодателем. Они согла-шались на то, что предлагала компания.

Сделайте себе подарок – поторгуйтесь. Вотнесколько подсказок, которые помогут вам начать пе-реговоры.

1. Просто начните торговаться. Да, я знаю, чтоэто страшно. Но рекрутеры не будут отзывать предло-жение только потому, что вы пытаетесь добиться длясебя некоторых преимуществ, поэтому вам нечего те-рять.

2. Всегда имейте запасной вариант. Рекрутерыохотнее идут на уступки, если знают, что вы можете

не принять предложение, а это возможно, если у васесть выбор.

3. Задавайте конкретные «рамки». Вы скорее до-стигнете цели, если попросите увеличить зарплату на$7000, чем просто просите ее увеличить, – вам могутпредложить $1000, и это будет формальным шагом кудовлетворению ваших требований.

4. Завышайте требования. При переговорах людине всегда получают желаемое. Просите больше, чемнадеетесь получить, может, вам повезет и вы получи-те «компромиссную» прибавку к зарплате.

5. Думайте не только о зарплате. Компании частоготовы пойти на любые уступки, кроме зарплаты, по-скольку если они повысят зарплату вам, то может ока-заться, что ваши коллеги получают меньше. Проситеувеличенную премию или какойнибудь другой бонус.Вы, например, можете добиться выплаты пособия напереезд наличными вместо оплаты счетов. Это выгод-но для студентов, поскольку можно сэкономить и напереезд потратить меньшую сумму.

6. Выбирайте удобный способ ведения перегово-ров. Многие советуют вести переговоры только по те-лефону. В какой-то степени они правы – это оченьудобно. Но если вы волнуетесь – используйте элек-тронную почту. Во время переговоров важно чувство-вать себя комфортно.

Кроме того, если вы ведете переговоры с круп-ной компанией, то в ней могут существовать уровниградации служащих. Всем служащим одного уровняплатят одинаково. В Microsoft, например, существу-ет такая система уровней. Вы можете торговаться впределах зарплаты служащих вашего уровня, но длябольшего требуется повышение уровня. Вам придет-ся убедить нанимателя и будущую команду, что вашопыт соответствует более высокому уровню, – задачатрудная, но выполнимая.

На работе

Вы прошли собеседование и вздохнули с облегче-

нием – всё позади. Наоборот, всё только начинает-ся. Как только вы попали в компанию, пора думать одальнейшей карьере. Куда вы уйдете и чего добье-тесь в другом месте?

Создайте график своего

карьерного роста

Самая обычная история – вы пришли в новую ком-панию и, естественно, переживаете. Все кажется та-ким грандиозным и перспективным, но проходит пятьлет, а вы все еще на том же месте. Только тогда выначинаете понимать, что за последние три года ниче-го не изменилось (ни ваши навыки, ни резюме). Такпочему вы не ушли три года назад?

Когда вы наслаждаетесь работой, очень легко за-быться и перестать понимать, что ваша карьера за-буксовала. Чтобы такого не случилось, представляй-те свою дальнейшую карьеру (хотя бы в общих чер-тах) прежде, чем начнете новую работу. Где вы хотитеоказаться через десять лет? Что для этого нужно сде-лать? Кроме того, продумайте планы на следующий

год и оцените прошедший – какой опыт вы получитев следующем году, как ваша карьера и ваши навыкипродвинулись в прошлом году. Заранее продумывай-те перспективы и регулярно проверяйте свои планы,это позволит вам избежать карьерного застоя.

Устанавливайте прочные отношения

В новой компании очень важен круг знакомств. Он-

лайн-дружба – это хорошо, но очное знакомство все-гда лучше. Установите дружеские отношения со сво-им непосредственным руководителем и коллегами.Даже если вы уйдете из компании, контакты со старойкомандой останутся.

Этот же подход относится и к личной жизни. Вашидрузья, друзья ваших друзей – ценные связи. Будьтеготовы оказать помощь, тогда помогут и вам.

Спросите себя, что вам нужно

Некоторые руководители могут помочь вам про-

двинуться по карьерной лестнице, другие проявляютиной подход, основанный на невмешательстве. Толь-ко вы сами сможете решить задачи, являющиеся клю-чевыми для вашей карьеры.

Будьте откровенны со своим руководством. Если

хотите в первую очередь заниматься программирова-нием, то скажите об этом. Если хотите стать ведущимразработчиком – обсудите с менеджером и этот ас-пект.

Только так вы сможете достигнуть целей согласносвоему личному графику.

Часть VIII. Вопросы

собеседования

Присоединяйтесь к нам наwww.CrackingTheCodingInterview.com и загружайтеполные, совместимые с Java/Eclipse решения, чи-тайте обсуждения задач из этой книги с други-ми пользователями, отправляйте нам свои отзы-вы, просматривайте список ошибок и опечаток, от-правляйте свое резюме и обращайтесь за дополни-тельными советами.

Структуры данных.Вопросы и советы

1. Массивы и строки

Надеюсь, что все читатели знакомы с массивами истроками, поэтому нет необходимости вникать в де-тали, лучше мы сфокусируемся на некоторых общихметодах работы с этими структурами данных.

Обратите внимание, что вопросы, относящиеся кмассивам и к строкам, одинаковы. Таким образом, лю-бой вопрос о массиве можно рассматривать как во-прос о строке и наоборот.

Хэш-таблицы

Хэш-таблица – это структура данных, связывающаяключи со своими значениями для более эффектив-ного поиска. В самом простом случае хэш-таблицапредставляет собой совокупность обычного массиваи хэш-функции. Когда вам нужно вставить объект иего ключ, хэш-функция преобразует ключ в число, ко-торое является индексом массива. Объект хранитсяпо полученному индексу.

Такая реализация, скорее всего, не будет работатьправильно – значение ключа должно быть уникаль-ным, иначе мы можем случайно перезаписать дан-ные. В результате полученный массив окажется гро-мадным: его размер должен превышать суммарныйразмер всех ключей, только так можно избежать «кол-лизий».

Вместо огромного массива, заполняемого индек-сируемыми объектами hash(key), мы можем создатьмассив меньшего размера и хранить объекты в связ-ном списке по индексу hash(key) % array_length. Что-бы получить объект с определенный ключом, нам при-дется произвести поиск по связному списку.

Существует и другой способ реализовать хэш-таб-лицу – бинарное дерево поиска. В этом случае можнообеспечить время поиска O(log N), если дерево будетсбалансированным. Кроме того данный подход позво-лит использовать гораздо меньше пространства (па-мяти), поскольку нет необходимости сразу создаватьогромный массив.

Попрактикуйтесь в реализации хэш-таблиц передсобеседованием. Это одна из наиболее любимых ин-тервьюерами структур данных.

Вот простейший пример работы с хэш-таблицей наязыке Java:

1 public HashMap<Integer, Student>

buildMap(Student[] students) {2 HashMap<Integer, Student> map = new

HashMap<Integer, Student>();3 for (Student s: students) map.put(s.getId(), s);4 return map;5 }Обратите внимание, что хэш-таблицы не всегда яв-

ляются идеальным решением. Использовать их илинет, решать вам – все зависит от поставленной зада-чи.

ArrayList (динамический массив)

ArrayList – это массив, размер которого может из-меняться во время выполнения программы; он обес-печивает время доступа O(1). Типичная реализация– при заполнении массива его размеры увеличивают-ся в два раза. Каждое удвоение занимает O(n) вре-мени, но поскольку данное событие происходит до-вольно редко, считается, что время доступа к массивуостается O(1).

1 public ArrayList<String> merge(String[] words,String[] more) {

2 ArrayList<String> sentence = newArrayList<String>();

3 for (String w: words) sentence.add(w);

4 for (String w: more) sentence.add(w);5 return sentence;6 }

StringBuffer (буфер строк)

Представьте, что вам нужно объединить несколь-ко строк. Каким будет время выполнения программы?Рассмотрим n строк одинаковой длины (x).

1 public String joinWords(String[] words) {2 String sentence = " ";3 for (String w: words) {4 sentence = sentence + w;5 }6 return sentence;7 }При каждой конкатенации создается новая копия

строки, куда копируются посимвольно две строки. Припервой итерации будет скопировано x символов. Вто-рая итерация скопирует 2x символов, третья – 3x. Витоге время выполнения можно оценить как O(x + 2x+ … + nx) = O(xn2).

StringBuffer поможет вам избавиться от этой про-блемы. Мы просто создаем массив всех строк и копи-руем их в строку только в случае необходимости.

1 public String joinWords(String[] words) {

2 StringBuffer sentence = new StringBuffer();3 for (String w: words) {4 sentence.append(w);5 }6 return sentence.toString();7 }Отличным упражнением станет создание собствен-

ной версии StringBuffer с использованием строк, мас-сивов и общих структур данных.

Вопросы интервью

1.1. Реализуйте алгоритм, определяющий, все лисимволы в строке встречаются один раз. При выпол-нении этого задания нельзя использовать дополни-тельные структуры данных.

1.2. Реализуйте функцию void reverse(char* str) на Cили C++. Функция должна циклически сдвигать строку,заканчивающуюся символом null.

1.3. Для двух строк напишите метод, определяю-щий, является ли одна строка перестановкой другой.

1.4. Напишите метод, заменяющий все пробелы встроке символами '%20'. Можно предположить, чтодлина строки позволяет сохранить дополнительныесимволы и «истинная» длина строки известна. (При-мечание: при реализации метода на Java используйте

символьный массив.)Пример:Ввод: "Mr John Smith "Вывод: "Mr%20John%20Smith"1.5. Реализуйте метод, осуществляющий сжатие

строки, на основе счетчика повторяющихся символов.Например, строка aabcccccaaa должна превратитьсяв a2b1c5a3. Если «сжатая» строка оказывается длин-нее исходной, метод должен вернуть исходную стро-ку.

1.6. Дано: изображение в виде матрицы размеромN × N, где каждый пиксель занимает 4 байта. Напиши-те метод, поворачивающий изображение на 90°.

1.7. Напишите алгоритм, реализующий следующееусловие: если элемент матрицы в точке M × N равен0, то весь столбец и вся строка обнуляются.

1.8. Допустим, что существует метод isSubstring,проверяющий, является ли одно слово подстрокойдругого. Для двух строк, s1 и s2, напишите код про-верки, получена ли строка s2 циклическим сдвигом s1,используя только один вызов метода isSubstring (при-мер: слово waterbottleполучено циклическим сдвигомerbottlewat).

Дополнительные вопросы: манипуляция с бита-ми (5.7), объектно-ориентированное проектирова-

ние (7.10), рекурсия (8.3), сортировка и поиск (9.6), C++ (13.10), модерирование (17.7, 17.8, 17.14).

2. Связные списки

Вопросы про связные списки могут показаться

трудными. Но есть и хорошие новости – таких вопро-сов немного, а множество задач являются всего лишьразновидностями типовых вопросов о связных спис-ках.

Задачи на связные списки предполагают, что вы мо-жете реализовать связный список с нуля.

Создание связного списка

Следующий код реализует очень простой односвяз-ный список:

1 class Node {2 Node next = null;3 int data;45 public Node(int d) {6 data = d;7 }89 void appendToTail(int d) {

10 Node end = new Node(d);11 Node n = this;12 while (n.next!= null) {13 n = n.next;14 }15 n.next = end;16 }17 }Обратите внимание: когда вы говорите о связном

списке на собеседовании, вы должны понимать, окаком списке – односвязном или двусвязном – идетречь.

Удаление узла из односвязного списка

Удаление узла из односвязного списка – доста-точно простая задача. Дан узел n, нам нужно найтипредыдущий узел prev и установить prev.next в n.net.Если у нас есть двусвязный список, нам нужно об-новить n.next, чтобы установить n.next.prev в n.prev.Не забудьте сделать проверку на null-указатель и принеобходимости обновить начало и конец списка.

Если вы реализуете код на C/С++ или другом языке,требующем контроля памяти, вам нужно освободитьпамять, которую занимал удаляемый узел.

1 Node deleteNode(Node head, int d) {

2 Node n = head;34 if (n.data == d) {5 return head.next; /* перемещаем голову */6 }78 while (n.next!= null) {9 if (n.next.data == d) {10 n.next = n.next.next;11 return head; /* голова списка не изменяется */12 }13 n = n.next;14 }15 return head;16 }

Метод бегунка

Метод бегунка (или второго указателя) использует-ся во многих задачах по связным спискам. Вы «про-бегаетесь» по связному списку двумя указателями од-новременно.

При этом один указатель называется «быстрым», адругой – «медленным».

Лучше всего продемонстрировать этот метод напримере. Существует связный список a1->a2->…->an-

>b1->b2->…->bn и его необходимо преобразовать ввид: a1->b1->a2->b2->… ->an->bn. Вы не знаете длинусвязного списка, но вы точно знаете, что длина – чет-ное число.

У вас есть два указателя – p1 (быстрый) и p2 (мед-ленный). За одну итерацию p1 перемещается на дваэлемента, а p2 – на один. Когда p1 достигнет конца,p2 будет находиться в середине списка. Переместивp1 обратно (в начало списка), можно провести реор-ганизацию. На каждой итерации p2 выбирает элементи вставляет его после p1.

Рекурсия и связные списки

Много задач о связных списка решаются с помо-щью рекурсии. Получив задание, вы должны прове-рить, можно ли использовать рекурсивный подход.Сейчас мы не будем подробно говорить о рекурсии,этой теме будет посвящен отдельный раздел.

Вы должны помнить, что рекурсивные алгоритмызанимают как минимум O(n) пространства, где n – глу-бина рекурсии. Все рекурсивные алгоритмы можнозаменить на итерационные, но более сложные алго-ритмы.

Вопросы собеседования

2.1. Напишите код, удаляющий дубликаты из несор-тированного связного списка.

ДополнительноКак вы будете решать задачу, если запрещается ис-

пользовать временный буфер?2.2. Реализуйте алгоритм для поиска в односвяз-

ном списке k-го элемента с конца.2.3. Реализуйте алгоритм, удаляющий узел из сере-

дины односвязного списка (доступ дан только к этомуузлу).

ПримерВвод: узел c из списка a->b->c->d->eВывод: ничего не возвращается, но новый список

имеет вид: a->b->d->e2.4. Напишите код, разбивающий связный список

вокруг значения x, так чтобы все узлы, меньшие x, ока-зались перед узлами, большими или равными x.

2.5. Два числа хранятся в виде связных списков,в которых каждый узел содержит один разряд. Всецифры хранятся в обратном порядке, при этом перваяцифра числа находится в начале списка. Напишитефункцию, которая суммирует два числа и возвращаетрезультат в виде связного списка.

ПримерВвод: (7->1->6) + (5->9->2). Это означает 617 + 295.Вывод: 2->1->9, что означает 912.ДополнительноРешите задачу, предполагая, что цифры записаны

в прямом порядке.Ввод: (6 – > 1 – > 7)+ (2 – > 9 – > 5). Это означает

617 + 295.Вывод: 9 – > 1 – > 2, что означает 912.2.6. Для кольцевого связного списка реализуйте ал-

горитм, возвращающий начальный узел петли.ОпределениеКольцевой связный список – это связный список, в

котором указатель последующего узла связан с болееранним узлом, образуя петлю.

ПримерВвод: A->B->C->D->E->C (предыдущий узел C)Вывод: C2.7. Реализуйте функцию, проверяющую, является

ли связный список палиндромом.

Дополнительные вопросы: деревья и графы (4.4),объектно-ориентированное проектирование (7.10),масштабируемость и лимиты памяти (11.7), моде-рирование (17.13).

3. Стек и очередь

Как и в случае связных списков, на вопросы по сте-

кам и очередям проще отвечать, когда известны вход-ные и выходные структуры данных. Некоторые зада-чи являются небольшими модификациями исходнойструктуры данных, но вам может достаться и болеесложное задание.

Реализация стека

Стек использует порядок LIFO (последним вошел,первым вышел). Стек подобен

стопке тарелок – последнюю добавленную в стоп-ку тарелку возьмут первой. Давайте рассмотрим про-стой код для демонстрации работы стека. Стек можнореализовать с помощью связного списка. Фактически,стек – это связный список, не позволяющий пользова-телю получить доступ к элементам ниже главного уз-ла.

1 class Stack {2 Node top;34 Object pop() {5 if (top!= null) {

6 Node item = top.data;7 top = top.next;8 return item;9 }10 return null;11 }1213 void push(Object item) {14 Node t = new Node(item);15 t.next = top;16 top = t;17 }1819 Object peek() {20 return top.data;21 } 22 }

Реализация очереди

Очередь использует порядок FIFO (первым вошел,первым вышел). Элементы удаляются из очереди втом же порядке, в котором были добавлены.

Очередь может также быть реализована в видесвязного списка с добавлением новых пунктов в егоконец.

1 class Queue {

2 Node first, last;34 void enqueue(Object item) {5 if (!first) {6 last = new Node(item);7 first = last;8 } else {9 last.next = new Node(item);10 last = last.next;11 }12 }1314 Node dequeue(Node n) {15 if (first!= null) {16 Object item = first.data;17 first = first.next;18 return item;19 }20 return null;21 }22 }

Вопросы собеседования

3.1. Опишите, как можно использовать один одно-мерный массив для реализации трех стеков.

3.2. Как реализовать стек, в котором кроме стан-дартных функций push и pop будет использоватьсяфункция min, возвращающая минимальный элемент?Оценка времени работы функций push, pop и min –O(1).

3.3. Представьте стопку тарелок. Если стопкаслишком высокая, она может развалиться. В ре-альной жизни, когда высота стопки превысила бынекоторое значение, мы начали бы складывать та-релки в новую стопку. Реализуйте структуру дан-ных SetOfStacks, имитирующую реальную ситуацию.Структура SetOfStack должна состоять из несколькихстеков, новый стек создается, как только предыдущийдостигнет порогового значения. Методы SetOfStacks.push() и SetOfStacks.pop() должны работать с общимстеком (со всей структурой) и должны возвращать теже значения, как если бы у нас был один большойстек.

ДополнительноРеализуйте функцию popAt(int index), которая осу-

ществляет операцию pop в указанный под-стек.3.4. В задаче про Ханойскую башню задействованы

3 башни и Nдисков разных размеров, которые нужнопереместить, (больший диск нельзя класть на мень-ший). Имеются следующие ограничения:

1) за один раз можно переместить только один диск;

2) диски перемещаются только с вершины однойбашни на другую башню;

3) диск можно положить только поверх большегодиска.

Напишите программу перемещения дисков (с пер-вой башни на последнюю) с использованием стеков.

3.5. Создайте класс MyQueue, который реализуеточередь с использованием двух стеков.

3.6. Напишите программу сортировки стека по воз-растанию. Можно использовать дополнительные сте-ки для хранения элементов, но нельзя копироватьэлементы в другие структуры данных (например, вмассив). Стек поддерживает следующие операции:push, pop, peek, isEmpty.

3.7. В приюте для животных есть только собакии кошки, а работа осуществляется в порядке очере-ди. Люди должны каждый раз забирать «самое ста-рое» (по времени пребывания в питомнике) животное,но могут выбрать кошку или собаку (животное в лю-бом случае будет «самым старым»). Нельзя выбратьлюбое понравившееся животное. Создайте структу-ру данных, обслуживающую эту систему и реализу-ющую операции enqueue, dequeueAny, dequeueDogи dequeueCat. Вы должны использовать встроеннуюструктуру данных LinkedList.

Дополнительные вопросы: связные списки (2.7),математика и вероятность (10.7).

4. Деревья и графы

Очень часто кандидаты уверены, что задачи о де-

ревьях и графах содержат больше всего подвохов.Вариант поиска структуры данных сложнее, чем ва-риант с линейно-организованной структурой (массивили связный список). Кроме того, время выполнения внаихудшем случае и среднее время могут существен-но различаться, а вы должны оценить оба аспекта лю-бого алгоритма. Скорость, с которой вы реализуетедерево или граф «с нуля», также играет важную роль.

Потенциальные ловушки

Деревья и графы – рассадник неоднозначностей инеправильных предположений. Убедитесь, что не упу-стили из виду какие-либо аспекты и сможете обосно-вать ваше решение в случае необходимости.

Бинарное дерево vs

бинарное дерево поиска

Когда задан вопрос о бинарном дереве, многие кан-дидаты считают, что речь идет о бинарном дереве по-

иска. Уточните, что имел в виду интервьюер. Бинар-ное дерево поиска предполагает, что для всех узловлевые дети меньше или равны текущему узлу, а пра-вые – больше текущего узла.

Сбалансировано vs несбалансировано

В большинстве случаев предполагается, что дере-вья сбалансированы, но не всегда. Попросите интер-вьюера уточнить задачу. Если дерево несбаланси-ровано, вам придется создавать алгоритм, учитываяоптимизацию. Существует множество способов сба-лансировать дерево так, чтобы глубина поддеревьевоставалась в пределах заданного диапазона. Но этоне означает, что левое и правое поддеревья будутодинакового размера.

Полнота дерева

Полные деревья – это деревья, в которых все ли-стья находятся внизу, а все остальные узлы, не яв-ляющиеся листьями, имеют по два потомка. Нужноотметить, что полные деревья – чрезвычайная ред-кость, так как дерево должно содержать 2n узлов, что-бы удовлетворять этому условию.

Обход бинарного дерева

Перед собеседованием попробуйте разобраться вреализации обхода дерева в прямом и обратном по-рядке. Наиболее часто используется обход в прямомпорядке, левое поддерево – вершина – правое под-дерево.

Балансировка: красно-черные и АВЛ-деревья

Хотя знание способов балансировки дерева помо-жет продемонстрировать, что вы являетесь велико-лепным разработчиком программного обеспечения,эти вопросы очень редко возникают во время собесе-дования. Вы должны знать время выполнения опера-ций на сбалансированных деревьях и быть знакомы сосновными способами балансировки, но подробностимало кого заинтересуют.

Префиксное дерево

Префиксное (нагруженное) дерево (trie) – это раз-новидность обычного n-арного дерева, в узлах кото-рого хранятся не ключи, а символьные метки. Каждыйпуть по такому дереву является словом. Простое пре-

фиксное дерево имеет следующий вид:

Обход графа

Большинство кандидатов неплохо разбираются вбинарных деревьях, но обход графа требует несколь-ко иного подхода. Особенно сложным является по-иск в ширину. Не забудьте, что поиск в ширину (BFS,Breadth First Search) и поиск в глубину (DFS, DepthFirst Search) предназначены для разных сценариев.DFS – это самый простой способ посетить все узлы вграфе, или, по крайней мере, посетить каждый узел,пока не найдется искомый. Однако при работе с очень

большими деревьями DFS не подходит. В этих случа-ях лучше воспользоваться BFS.

Поиск в глубину

При DFS мы посещаем узел r и затем проходимсяпо всем ближайшим к r узлам. При попадании в узел n(соседний с r) мы посещаем всех его соседей. Такимобразом, перед перемещением к следующему потом-ку узла r полностью обследуется узел n.

Обратите внимание, что прямой порядок и дру-гие формы обхода дерева являются разновидностя-ми DFS. Основное отличие состоит в том, что при ре-ализации алгоритма в случае графа необходимо про-верить, был ли посещен узел. Если этого не сделать,то можно застрять в бесконечном цикле.

Приведенный псевдокод реализует DFS:1 void search(Node root) {2 if (root!= null) return;3 visit(root);4 root.visited = true;5 foreach (Node n in root.adjacent) {6 if (n.visited == false)7 search(n);8 }9 }

10 }

Поиск в ширину

Поиск в ширину (BFS) не так прост, у большинствакандидатов при первом знакомстве он вызывает за-труднения. При BFS перед посещением любого из«внуков» r мы должны посетить всех соседей с узла r.Оптимальным решением в этом случае будет реали-зация с циклом и очередью:

1 void search(Node root) {2 Queue queue = new Queue();3 root.visited = true;4 visit(root);5 queue.enqueue(root); // Добавление в конец оче-

реди67 while (!queue.isEmpty()) {8 Node r = queue.dequeue(); // Удаление из головы

очереди9 foreach (Node n in r.adjacent) {10 if (n.visited == false) {11 visit(n);12 n.visited = true;13 queue.enqueue(n);14 }15 }

16 }17 }

Если вас попросят реализовать BFS, вспомни-те, что ключевым моментом является использованиеочереди. Остальную часть алгоритма можно постро-ить исходя из этого факта.

Вопросы собеседования

4.1. Реализуйте функцию, проверяющую сбаланси-рованность бинарного дерева. Предположим, что де-рево считается сбалансированным, если разница вы-сот двух поддеревьев любого узла не превышает 1.

4.2. Разработайте алгоритм поиска маршрута меж-ду двумя узлами для направленного графа.

4.3. Напишите алгоритм создания бинарного дере-ва поиска с минимальной высотой для отсортирован-ного (по возрастанию) массива.

4.4. Для бинарного дерева поиска разработайтеалгоритм, создающий связный список, состоящий извсех узлов заданной глубины (для дерева с глубинойD должно получиться D связных списков).

4.5. Реализуйте функцию проверки, является ли би-нарное дерево бинарным деревом поиска.

4.6. Напишите алгоритм поиска «следующего» узла

для заданного узла в бинарном дереве поиска. Мож-но считать, что у каждого узла есть ссылка на его ро-дителя.

4.7. Создайте алгоритм и напишите код поиска пер-вого общего предка двух узлов бинарного дерева. По-старайтесь избежать хранения дополнительных уз-лов в структуре данных. Примечание: необязательноиспользовать бинарное дерево поиска.

4.8. Дано: два очень больших бинарных дерева: T1– с миллионами узлов и T2 – с сотнями узлов. Создай-те алгоритм, проверяющий, является ли T2 поддере-вом T1. Дерево T2 считается поддеревом T1, если су-ществует такой узел n в T1, что поддерево, «расту-щее» из n, идентично дереву T2. (Если вы выреже-те дерево в узле n и сравните его с T2, они окажутсяидентичны.)

4.9. Дано бинарное дерево, в котором каждый узелсодержит число. Разработайте алгоритм, выводящийна печать все пути, сумма значений которых соответ-ствует заданной величине. Обратите внимание, чтопуть может начинаться и заканчиваться в любом ме-сте дерева.

Дополнительные вопросы: сортировка и поиск(9.8), масштабируемость и лимиты памяти (11.2,11.5), модерирование (17.13, 17.14), тяжелые вычис-

ления (18.6, 18.8, 18.9, 18.10, 18.13).

Концепции и алгоритмы.

Вопросы и советы

5. Поразрядная обработка

Поразрядная обработка используется при решениисамых разных задач. Иногда в задании явно указыва-ется, что нужно произвести побитовую обработку, но,скорее всего, она вам понадобится для оптимизациикода. Вы должны ориентироваться в этой методике,как при вычислениях, так и при написании кода. Нобудьте осторожны: при битовой обработке очень лег-ко совершить ошибку. Обязательно протестируйте по-лучившийся код или проверяйте его непосредственново время написания.

Расчеты на бумаге

Ниже приведены практические задания, которыепомогут вам преодолеть боязнь поразрядной обра-ботки. Если вы «застряли», взгляните на эти операциикак на операции с обычными числами в десятичнойсистеме счисления, а затем примените этот же под-ход к бинарной арифметике.

Не забудьте некоторые обозначения: ̂ соответству-ет операции XOR, а ~ – операции NOT. Предположим,что мы работаем с четырехбитными числами. Зада-ния из третьей колонки можно решить или использо-вать некоторые приведенные ниже «хитрости».

Решение: строка 1 (1θθθ, 1111, 11θθ); строка 2(θ1θ1, 1θθ1, 11θθ); строка 3 (θθ11, θθ11, 1111); строка4 (θθ1θ, 1θθθ, 1θθθ).

Трюки для третьей колонки:• 0110+0110 = 0110*2, что эквивалентно смешению

0110 влево на 1.• Поскольку 0100=4, можно умножить θθ11 на 4.

Умножение на 2n сдвигает разряды числа на n. Мысмещаем θθ11 влево на 2 и получаем 11θθ.

• Взгляните на эту операцию с точки зрения битов.Операция XOR для бита и его инверсии всегда дает 1.Поэтому a^(~a) всегда дает последовательность еди-ниц.

• Операция вида x && (~θ << n) очищает n пра-вых битов числа x. Значение ~θ – это последователь-ность единиц. При сдвиге числа влево на n позициймы получаем последовательность единиц, за которы-ми следуют n нулей. Операция AND полученного чис-ла с числом x очищает правые n битов числа x.

Чтобы решить остальные задачи, воспользуйтеськалькулятором Windows в режиме Вид ▸ Програм-мист. Так вам будет проще выполнять бинарные опе-рации, включая AND, XOR и сдвиги.

Биты: трюки и факты

При решении задач на битовые операции полезнознать некоторые факты. Их нужно не запомнить, а по-нять. Записи 1sи 0sиспользуются для обозначения по-следовательностей единиц или нулей соответствен-но.

Основные задачи: получение,

установка, очистка и обновление бита

Приведенные далее операции очень важны, вамнужно понимать, как они работают. Зубрежка обяза-тельно приведет к ошибкам. Вместо этого разбери-тесь, как можно реализовать эти методы, тогда высможете решить любые задачи, связанные с битами.

Извлечение бита

Метод getBit сдвигает 1 на i битов, создавая значе-ние, например 00010000. Операция AND над числомnum очищает все биты, кроме бита i. Затем этот битсравнивается с 0. Если результат не равен 0, значит,бит i равен 1, иначе бит i равен 0.

1 boolean getBit(int num, int i) {2 return ((num & (1 << i))!= 0);3 }

Установка бита

Метод setBit сдвигает 1 на i бит, создавая значение,например 00010000. Операция OR над числом numизменяет только значение бита i. Все остальные битыостаются неизменными.

1 int setBit(int num, int i) {2 return num | (1 << i);3 }

Очистка бита

Этот метод – противоположность метода setBit.Сначала создается число 11101111 (инверсия числа00010000). Затем производится операция ANDс чис-лом num. Таким образом, очищается только i-й бит, авсе остальные биты не изменяются.

1 int clearBit(int num, int i) {2 int mask = ~(1 << i); 3 return num & mask;4 }Для очистки всех битов до бита i (включительно):1 int clearBitsMSBthroughI(int num, int i) { 2 int mask

= (1 << (i+1)) – 1;3 return num & mask;4 }Для очистки всех битов от i до 0 (включительно):1 public static int clearBitsIthrough0(int num, int i) {2 int mask = ~((1 << (i+1)) – 1);3 return num & mask;4 }

Обновление бита

Этот метод является объединением методов setBitи clearBit. Сначала с помощью маски, например11101111, очищается бит на позиции i. Затем значениеv сдвигается вправо на i битов. В результате создает-ся число, у которого i-й бит равен v, а все остальныебиты нулевые. Операция OR для этих двух чисел об-новляет i-й бит, если бит v равен 1, и оставляет егонулевым в противном случае.

1 int updateBit(int num, int i, int v) {2 int mask = ~(1 << i);3 return (num & mask) | (v << i);4 }

Вопросы собеседования

5.1. Дано: два 32-битных числа Nи Mи две позициибитов iи j. Напишите метод для вставки M в N так, что-бы число M занимало позицию с бита j по бит i. Мож-но считать, что j и i имеют такие значения, что числоM обязательно поместится в этот промежуток. ЕслиM = 10011, для его размещения понадобится 5 битовмежду j и i. Если j=3 и i=2, число M не поместится вуказанный промежуток.

Пример

Ввод: N = 10000000000, M = 10011, i = 2, j = 6Вывод: N = 100010011005.2. Дано: вещественное число в интервале меж-

ду 0 и 1 (например, 0,72), которое было передано какdouble. Запишите его двоичное представление. Еслидля представления числа не хватает 32 разрядов, вы-ведите сообщение об ошибке.

5.3. Дано: положительное число. Выведите ближай-шие наименьшее и наибольшее числа, которые име-ют такое же количество единичных битов в двоичномпредставлении.

5.4. Объясните, что делает код: ((n& (n-1)) ==0).5.5. Напишите функцию, определяющую количе-

ство битов, которые необходимо изменить, чтобы изцелого числа A получить целое число B.

ПримерВвод: 31, 14 Вывод: 25.6. Напишите программу, меняющую местами чет-

ные и нечетные биты числа. Количество инструкцийдолжно быть наименьшим (нужно поменять местамибиты 0 и 1, 2 и 3 и т. д.).

5.7. Массив A[1…n] содержит целые числа от 0 доn, но одно число отсутствует. В этой задаче мы не мо-жем получить доступ к любому числу в массиве A спомощью одной операции. Элементы массива A хра-нятся в двоичном виде, а доступ к ним осуществля-

ется только при помощи команды извлечь j-й бит изA[i], имеющей фиксированное время выполнения. На-пишите код, обнаруживающий отсутствующее целоечисло. Можно ли выполнить эту задачу за время O(n)?

5.8. Изображение с монохромного экрана сохране-но как одномерный массив байтов, так что в одномбайте хранится информация о восьми соседних пик-селах. Ширина изображения w кратна 8 (байты соот-ветствуют столбцам). Высоту экрана можно рассчи-тать, зная длину массива и ширину экрана. Реализуй-те функцию drawHorizontalLine(byte[]screen, intwidth,intx1, intx2, inty), которая рисует горизонтальную ли-нию из точки (x1, y) в точку (x2, y).

Дополнительные вопросы: массивы и строки (1.1,1.7), рекурсия (8.4, 8.11), масштабируемость и ли-миты памяти (11.3, 11.4), C++ (13.9), модерирование(17.1, 17.4), задачи повышенной сложности (#18.1).

6. Головоломки

Задачи-головоломки являются очень спорной те-

мой, многие компании запрещают использовать их насобеседованиях. Но даже если такие вопросы запре-щены, это не означает, что они не могут вам достать-ся. Почему? Да потому что единого подхода к тому,

какую задачу можно отнести к головоломкам, не су-ществует.

Если вам досталась головоломка, то наверняка онаинтересная и наверняка ее можно решить логически.Корни большинства головоломок лежат в математикеили информатике.

Давайте рассмотрим основные подходы к решениюголоволомок.

Начните говорить

Если вам дали головоломку, не паникуйте. Как и вслучае с задачами на алгоритмы, интервьюеры хотятвидеть, что вы пытаетесь решить задачу. Они не ожи-дают, что вы сразу дадите ответ. Начните рассуждатьвслух, покажите интервьюеру, как вы решаете задачу.

Правила и шаблоны

В большинстве случаев попробуйте найти и запи-сать правила или шаблоны, которые помогут вам ре-шить задачу. Да-да, именно записать – это поможетзапомнить их и использовать при решении задачи. Да-вайте рассмотрим простой пример.

У вас две веревки и каждая из них горит ровно одинчас. Как их можно использовать, чтобы определить,что прошло 15 минут? Более того, плотность веревок

не является константой, поэтому необязательно, чтополовина веревки будет гореть ровно полчаса.

Совет: остановитесь и попытайтесь решить задачусамостоятельно. В крайнем случае, прочитайте этотраздел медленно и вдумчиво. Каждый абзац будетприближать вас к решению.

Из постановки задачи ясно, что у нас есть один час.Можно получить двухчасовой интервал, если поджечьвторую веревку после того, как догорит первая. Такимобразом, мы получаем правило.

Правило 1: если одна веревка горит x минут, а дру-гая горит y минут, то общее время горения составитx+y.

Что еще мы можем сделать с веревкой? Попыткаподжечь веревку в любом другом месте, кроме какс концов, не даст нам дополнительной информации.Мы понятия не имеем, сколько времени она будет го-реть.

Но мы можем поджечь веревку с двух концов одно-временно. Огонь должен будет встретиться через 30минут.

Правило 2: если веревка горит x минут, мы можемотсчитать интервал времени, равный x/2 минут.

Мы знаем, что можем отсчитать 30 минут, исполь-зуя одну веревку. Это также означает, что мы можемвычесть 30 минут из времени горения второй веревки,

если одновременно подожжем первую веревку с двухконцов, а вторую только с одного.

Правило 3: если первая веревка горит x минут, авторая веревка горит y минут, мы можем заставитьвторую веревку гореть (y-x) минут или (y-x/2) минут.Теперь давайте соединим все части воедино. Мы мо-жем превратить вторую веревку в веревку, которая го-рит 30 минут. Если мы теперь подожжем вторую ве-ревку с другого конца (см. правило 2), то она будет го-реть 15 минут.

Запишем получившийся алгоритм:• Поджигаем веревку 1 с двух сторон, веревку 2 –

только с одного.• Веревка 1 сгорела, значит, прошло 30 минут, ве-

ревке 2 осталось гореть 30 минут.• В этот момент времени поджигаем веревку 2 с дру-

гого конца.• Чтобы веревка 2 сгорела полностью, понадобится

15 минут.Обратите внимание, как записанные правила об-

легчили решение этой задачи.

Балансировка худшего случая

Большинство головоломок относятся к задачам ми-нимизации, когда требуется уменьшить количество

действий или выполнить что-либо определенное ко-личество раз. Можно попробовать «сбалансировать»худший случай. Таким образом, если решение приве-дет к смещению худшего случая, можно выполнитьбалансировку худшего случая. Рассмотрим конкрет-ный пример.

Задача о «девяти шарах» – классика собеседова-ния. У вас есть 9 шаров – восемь имеют одинаковыйвес, а один более тяжелый. Вы можете воспользо-ваться весами, позволяющими узнать, какой шар тя-желее. Требуется найти тяжелый шар за два взвеши-вания.

Разделите шары на две группы (по четыре шара),оставшийся (девятый) шар можно пока отложить всторону. Если одна из групп тяжелее, значит, шар на-ходится в ней. Если обе группы имеют одинаковыйвес, тогда девятый шар – самый тяжелый. Если вос-пользоваться этим же методом еще раз, то в худшемслучае вы получите результат за три взвешивания –одно лишнее!

Это пример несбалансированного худшего случая.Чтобы определить, является ли девятый шар самымтяжелым, нужно одно взвешивание, а чтобы выяс-нить, где он, – три. Если мы «оштрафуем» девятыйшар, отложив большее количество шаров, то можемснизить нагрузку на другие. Классический пример ба-

лансировки худшего случая.Если мы раздели шары на группы по три шара в

каждой, то достаточно одного взвешивания, чтобы по-нять, в какой группе находится тяжелый шар. Мы мо-жем даже сформулировать правило: дано N шаров,где N кратно трем, за одно взвешивание можно найтигруппу шаров N/3, в которой находится самый тяже-лый шар.

Для оставшейся группы из трех шаров нужно повто-рить ту же операцию: отложить один шар, а осталь-ные взвесить. Если шары весят одинаково, значит,оставшийся шар – самый тяжелый, иначе весы «пока-жут» тяжелый шар.

Алгоритмический подход

Если вы не можете сразу найти решение, попро-буйте использовать один из методов алгоритмизации.Головоломки – это те же задачи алгоритмизации, изкоторых убраны технические нюансы. Думайте, упро-щайте, обобщайте, сопоставляйте с шаблоном, ис-пользуйте базовый случай – все это может пригодить-ся.

Вопросы собеседования

6.1. Дано: 20 баночек с таблетками. В 19 баночках

лежат таблетки весом 1 г, а в одной – весом 1,1 г. Данывесы, показывающие точный вес. Как за одно взвеши-вание найти банку с тяжелыми таблетками?

6.2. Дано: шахматная доска размером 8×8, из кото-рой были вырезаны два противоположных по диаго-нали угла, и 31 кость домино; каждая кость доминоможет закрыть два квадратика на поле. Можно ли вы-мостить костями всю доску? Обоснуйте свой ответ.

6.3. У вас есть пятилитровый и трехлитровый кув-шины и неограниченное количество воды. Как отме-рить ровно 4 литра воды? Кувшины имеют неправиль-ную форму, поэтому точно отмерить «половину» кув-шина невозможно.

6.4. На острове существует правило – голубоглазыелюди не могут там находиться. Самолет улетает каж-дый вечер в 20:00. Каждый человек может видеть цветглаз других людей, но не знает цвет собственных, ни-кто не имеет права сказать человеку, какой у него цветглаз. На острове находится не менее одного голубо-глазого человека. Сколько дней потребуется, чтобывсе голубоглазые уехали?

6.5. Дано 100-этажное здание. Если яйцо сброситьс высоты N-го этажа (или с большей высоты), оноразобьется. Если его бросить с меньшего этажа, ононе разобьется. У вас есть два яйца, найдите N за ми-нимальное количество бросков.

6.6. Дано: 100 закрытых замков расположены вдлинном коридоре. Человек сначала открывает всесто. Затем он закрывает каждый второй замок. Затемон делает еще один проход – «переключает» каждыйтретий замок (если замок был открыт, то он его закры-вает, и наоборот). На 100-м проходе человек должен«переключить» только замок № 100. Сколько замковостались открытыми?

7. Математика и теория вероятностей

Хотя значительное количество математических за-

дач, которые приходится решать во время собеседо-вания, похожи на головоломки, для их решения мож-но использовать логический подход. Они базируютсяна основных законах математики и логики, и знаниеэтого факта облегчит как само решение, так и его про-верку. Сейчас мы поговорим об основных математи-ческих понятиях, которые могут вам пригодиться.

Простые числа

Любое число может быть представлено как произ-ведение простых чисел. Например: 84 = 22 × 31 × 50 ×71 × 110 × 130 × 170 ×…

Делимость

Из закона простых чисел следует, что если xделит-ся на y(будем записывать это условие как x\y илиmod(y, x) = 0), то все простые числа, входящие в раз-ложение на множители числа x, должны присутство-вать в разложении на множители числа y. Рассмотримпример:

Пусть x = 2j0 * 3j1 * 5j2 * 7j3 * 11j4 *…Пусть y = 2k0 * 3k1 * 5k2 * 7k3 * 11k4 *…Если x\y, тогда для всех i выполняется неравенство

ji <= ki.Наибольший общий делитель x и y:gcd(x, y) = 2min(j0, k0) * 3min(j1, k1) * 5min(j2, k2) *…Наименьшее общее кратное x и y:lcm(x, y) = 2max(j0, k0) * 3max(j1, k1) * 5max(j2, k2) *…Попробуйте сами решить забавную задачку: найди-

те произведение НОД и НОК (gcd *lcm):gcd * lcm = 2min(j0, k0) * 2max(j0, k0) * 3min(j1, k1) * 3max(j1,

k1) *…= 2min(j0, k0) + max(j0, k0) * 3min(j1, k1) + max(j1, k1) *…= 2min(j0,, k1) *…= 2j0 + k0 * 3j1 + k1 *…

= 2j0 * 2k0 * 3j1 * 3k1 *…= xy

Является ли число простым

Этот вопрос настолько часто встречается, что о немнеобходимо упомянуть. Для этого достаточно прове-рить делимость в цикле от 2 до n-1:

1 boolean primeNaive(int n) {2 if (n < 2) {3 return false;4 }5 for (int i = 2; i < n; i++) {6 if (n % i == 0) {7 return false;8 }9 }10 return true;11 }Небольшое, но немаловажное улучшение – цикл

можно ограничить квадратным корнем из n.1 boolean primeSlightlyBetter(int n) {2 if (n < 2) {3 return false;4 }5 int sqrt = (int) Math.sqrt(n);

6 for (int i = 2; i <= sqrt; i++) {7 if (n % i == 0) return false;8 }9 return true;10 }Квадратного корня достаточно, поскольку для каж-

дого числа, которое делится на n без остатка, есть до-полнение b, такое что a*b=n. Если a>sqrt, то b<sqrt (по-скольку sqrt * sqrt = n). a нам не понадобится, так какдля проверки n на простоту мы уже сверились с b.

На самом деле все, что нужно сделать, – это про-верить, делится ли n на простые числа. И тут появля-ется решето Эратосфена.

Список простых чисел: решето Эратосфена

Решето Эратосфена – эффективный способ гене-рации списка простых чисел. Он работает, распозна-вая все составные числа, которые делятся на про-стые числа.

Начнем с генерации списка всех чисел, не превы-шающих заданного значения max. Можно сразу вы-черкнуть четные числа. Затем найти ближайшее про-стое число и вычеркнуть все числа, кратные ему. По-следовательно исключая все числа, кратные 2, 3, 5, 7,11 и т. д., мы получим список простых чисел, лежащихв диапазоне от 2 до max.

Представленный далее код реализует решето Эра-тосфена:

1 boolean[] sieveOfEratosthenes(int max) {2 boolean[] flags = new boolean[max + 1];3 int count = 0;45 init(flags); // Устанавливаем все флаги в true (кро-

ме 0 и 1)6 int prime = 2;78 while (prime <= max) {9 /* Вычеркиваем оставшуюся часть произведений

простых чисел */10 crossOff(flags, prime);1112 /* Находим следующее истинное значение */13 prime = getNextPrime(flags, prime);1415 if (prime >= flags.length) {16 break;17 } 18 }19 20 return flags;21 }2223 void crossOff(boolean[] flags, int prime) {24 /* Вычеркиваем оставшуюся часть произведений

простых чисел. Мы начинаем25 * с (prime*prime), потому что, если существует k

* prime,26 * где k < prime, это значение должно быть вы-

черкнуто27 * на предыдущей итерации. */28 for (int i = prime * prime; i < flags.length; i += prime) {29 flags[i] = false;30 }31 }3233 int getNextPrime(boolean[] flags, int prime) {34 int next = prime + 1;35 while (next < flags.length &&!flags[next]) {36 next++;37 }38 return next;39 }Конечно, данную программу можно дополнительно

оптимизировать. Простейший способ – использоватьмассив нечетных чисел, который сократит использо-вание памяти в два раза.

Теория вероятностей

Теория вероятностей – довольно сложная тема, но

она основана на нескольких достаточно логичных за-конах. Посмотрите на диаграмму Венна, визуализиру-ющую два события – A и B. Области двух кругов со-ответствуют относительным вероятностям событий, аобласть пересечения – вероятности события {A andB}.

Вероятность события {A and B}

Представьте, что вы бросили стрелку дартса в диа-грамму Венна. Какова вероятность, что вы попадетев пересечение кругов А и B? Если вы знаете вероят-ность попадания в область А и знаете, какой проценткруга А перекрывается кругом B (то есть вероятностьтого, что вы попадете в B, если попали в А), то веро-ятность события P{A and B} можно записать как:

P(A and B) = P(B given A) P(A)Например, предположим, что мы выбрали число из

интервала от 1 до 10 (включительно). Какова вероят-

ность того, что выбранное число окажется четным ибудет принадлежать интервалу от 1 до 5. Вероятностьтого, что выбранное число принадлежит диапазону от1 до 5, составляет 50 %, а вероятность того, что эточисло окажется четным, – 40 %. Так, подсчитаем ве-роятность данного события:

P(x is even and x <= 5)= P(x is even given x <= 5) P(x <= 5)= (2/5) * (1/2)= 1/5

Вероятность события {A or B}

Рассмотрим другой случай – вероятность попада-ния в область A или B – P{A or B}. Если вы знаете ве-роятности попадания в каждую область и вероятностьпопадания в пересечение областей, тогда

P(A or B) = P(A) + P(B) – P(A and B)С точки зрения логики все корректно – нам нужно

только сложить площади обоих кругов и избавиться отдвойного наложения в области пересечения. Давай-те визуализируем эту задачу с помощью диаграммыВенна:

Например, предположим, что мы выбрали число изинтервала от 1 до 10 (включи тельно). Какова веро-ятность того, что число окажется четным или будетпринадлежать диапазону от 1 до 5? Вероятность того,что число является четным, – 50 %. Вероятность то-го, что число принадлежит интервалу от 1 до 5, такжесоставляет 50 %. Вероятность того, что число четноеи принадлежит заданному интервалу, мы уже вычис-лили в предыдущем примере, она составляет 20 %.

P(x is even or x <=5)= P(x is even) + P(x <= 5) – P(x is even and x <= 5)= (1/2) + (1/2) – (1/5)= 4/5Теперь сформулировать правила для независимых

и взаимоисключающих событий не составит труда.

Независимость событий

Если A и B независимы (наступление одного собы-тия не изменяет вероятность наступления другого), тоP(A and B) =P(A)P(B). Это правило с очевидностьюследует из того, что P(B given A) =P(B), при условии,что событие A никак не связано с B.

Взаимоисключающие события

Если A и B являются взаимоисключающими (еслиодно событие произошло, то другое произойти не мо-жет), то P(Aor B) =P(A)+ P(B) (поскольку P(AandB) = 0).

Многие путают независимые и взаимоисключаю-щие события. На самом деле два события не могутбыть одновременно независимыми и взаимоисклю-чающими (конечно, если вероятность событий боль-ше 0). Почему? Для взаимоисключающих событийфакт свершения одного события означает, что второеневозможно. Независимость означает, что реализа-ция одного события никак не влияет на другое. Такимобразом, два события с ненулевыми вероятностямине могут быть и взаимоисключающими, и независи-мыми.

Если одно или оба события имеют нулевую веро-ятность (то есть события невозможны), то события

являются и независимыми, и взаимоисключающими.Это следует из определений независимых и взаимо-исключающих событий.

Обратите внимание!

Будьте осторожны, работая с типами float иdouble, – у них разное количество разрядов.

Не предполагайте, что речь идет о целых числах,если это не указано явно.

Не предполагайте, что события являются независи-мыми (или взаимоисключающими), если это явно неуказано. Будьте внимательны, боритесь с искушени-ем слепого умножения или сложения вероятностей.

Вопросы собеседования

7.1. Вам предлагают бросить мяч в баскетбольноекольцо. Существует два варианта игры:

Вариант 1: попасть в кольцо с одного броска.Вариант 2: у вас есть три попытки, и нужно попасть

в кольцо два раза из трех. Если p – вероятность попа-дания, то как, в зависимости от значения p, выбратьболее выигрышный вариант игры?

7.2. Три муравья находятся в вершинах треуголь-ника. Какова вероятность столкновения между каки-ми-либо двумя или всеми тремя муравьями, если му-

равьи начинают двигаться вдоль сторон треугольни-ка? (Муравей выбирает любое направление с равнойвероятностью, скорость движения муравьев одинако-ва.)

Найдите вероятность столкновения для случая, ко-гда n муравьев находятся в вершинах n-угольника.

7.3. Какова вероятность пересечения двух прямых,лежащих в одной плоскости?

7.4. Используя только оператор суммирования, на-пишите методы, реализующие операции умножения,вычитания и деления целых чисел.

7.5. Для двух квадратов, лежащих в одной плоско-сти, найдите прямую, которая делила бы эти квадра-ты пополам. (Стороны квадратов параллельны осямкоординат.)

7.6. Дано: набор точек на плоскости. Найдите пря-мую линию, которая проходит через большинство то-чек.

7.7. Разработайте алгоритм, позволяющий найти k-е число из упорядоченного числового ряда, в раз-ложении элементов которого на простые множителиприсутствуют только числа 3, 5 и 7.

Дополнительные вопросы: модерирование (17.11),задания повышенной сложности (18.2).

8. Объектно-ориентированное

проектирование

Задания по объектно-ориентированному проекти-рованию (ООП) предполагают, что кандидат может со-ставить схему из классов и методов, позволяющуюреализовать техническую задачу или имитировать ре-альный объект. Эти задачи дают интервьюеру воз-можность составить представление о стиле програм-мирования кандидата.

Вы должны показать, что понимаете, как создатьизящный и удобный объектно-ориентированный код.Так что провал при выполнении этих заданий можетпревратиться в «красную карточку» для всего собесе-дования.

Как подготовиться к заданиям по ООП

Независимо от того, о чем идет речь – о матери-альном объекте или технической задаче, – решениеООП-задания может идти по стандартному пути. При-веденный далее подход пригодится для решения мно-гих задач.

Шаг 1. Избавьтесь от неоднозначностей

Вопросы по ООП иногда содержат специально до-бавленные неопределенности. Это делается для то-го, чтобы проверить, будете ли вы высказывать пред-положения или будете задавать уточняющие вопро-сы. В конце концов, разработчик, который пишет про-граммы, должен сознавать, что его действия могут нетолько привести к потере времени и денег компании,но и создать более серьезные проблемы.

Задавая уточняющие вопросы по задачам ООП, вывыясняете, кто и как будет использовать ваш про-граммный продукт. В этом диалоге вам следует руко-водствоваться правилом шести W (who, what, where,when, how, why) – кто, что, где, когда, как, почему.

Например, предположим, что вас попросили напи-сать ООП-модель кофеварки. Задание выглядит од-нозначным? Увы, это не так.

Кофеварка может стоять в большом ресторане, об-служивающем сотни клиентов в час, и варить десят-ки разновидностей кофе. Или это может быть оченьпростое устройство на кухне пожилой семейной пары,способное без проблем сварить только чашечку чер-ного кофе. Как видите, целевая аудитория и условияиспользования устройства влияют на ваш проект.

Шаг 2. Определите основные объектыТеперь, когда мы понимаем, что будем проектиро-

вать, необходимо выделить основные объекты систе-мы. Если мы будет разрабатывать кофеварку для ре-сторана, основными объектами будут Table, Guest,Party, Order, Meal, Employee, Server и Host.

Шаг 3. Анализируем связиОсновные объекты выделены, теперь нужно про-

анализировать связи между ними. Какие члены долж-ны присутствовать в наших объектах? Есть ли объек-ты, которые наследуют от каких-либо других объек-тов? Какая связь используется – «многие-комногим»или «один-ко-многим»?

В случае с ресторанной кофеваркой, проект будетиметь вид:

• в Party присутствует массив Guests;• Server и Hosts наследуются от Employee;• у каждого Table есть один Party, но у каждого Party

может быть несколько Table;• один Host для Restaurant.Будьте очень осторожны – вы можете сде-

лать неправильные предположения. Например, стол(Table) может быть общим для нескольких Party, – такназываемый «общий стол» в некоторых модных тусо-вочных местах. Вы должны обсудить со своим интер-вьюером цель проекта.

Шаг 4. Исследуйте действияК этому моменту у вас должна быть готова схема

объектно-ориентированного проекта. Остается рас-смотреть основные действия, которые могут быть вы-полнены объектами, и их взаимосвязи. Вы можете об-наружить, что забыли какие-либо объекты, и вам при-дется обновить проект.

Например, компания (Party) идет в ресторан(Restaurant) и гости (Guests) интересуются свобод-ным столиком (Table) у официанта (Host). Официантпросматривает список резервирования (Reservation)и, если есть свободные места, компания (Party) зани-мает столик (Table). Если свободных мест нет, компа-ния становится в очередь (в конец списка). Когда ком-пания уходит, стол освобождается и его занимает сле-дующая по порядку в очереди компания.

Разработка шаблонов

Поскольку интервьюеры пытаются протестироватьваши возможности, а не ваши знания, разработкашаблонов чаще всего остается за рамками собеседо-вания. Однако шаблоны Singleton (одиночка) и FactoryMethod (фабричный метод) могут пригодиться, и мыостановимся на них поподробнее.

Существует множество шаблонов, но в этой книге

мы не можем рассмотреть их все. Так что, если вы хо-тите улучшить навыки программирования, постарай-тесь раздобыть книгу по этой теме.

Singleton

Шаблон Singletonгарантирует, что класс имееттолько один экземпляр и обеспечивает доступ к эк-земпляру через приложение. Он может быть полезенв том случае, когда у вас есть «глобальный» объектс одним экземпляром. Например, мы можем реализо-вать класс Restaurant так, чтобы существовал един-ственный экземпляр Restaurant.

1 public class Restaurant {2 private Restaurant _instance = null;3 public static Restaurant getInstance() {4 if (_instance == null) {5 _instance = new Restaurant();6 }7 return _instance;8 } 9 }

Factory Method

Фабричный метод предлагает интерфейс, позволя-ющий подклассам создавать экземпляры некоторогокласса. Вам может понадобиться реализовать эту за-

дачу с классом Creator, который является абстракт-ным, не способным обеспечить реализацию фабрич-ного метода. Или же класс Creator может оказать-ся реальным классом, обеспечивающим реализациюэтого метода. Тогда фабричный метод будет прини-мать параметр, определяющий, какой класс нужноинициализировать.

1 public class CardGame {2 public static CardGame

createCardGame(GameType type) {3 if (type == GameType.Poker) {4 return new PokerGame();5 } else if (type == GameType.BlackJack) {6 return new BlackJackGame();7 }8 return null;9 } 10 }

Вопросы собеседования

8.1. Разработайте структуры данных для универ-сальной колоды карт. Объясните, как разделить струк-туры данных на подклассы, чтобы реализовать игру вблэкджек.

8.2. Предположим, что существует Call-центр стремя уровнями сотрудников: оператор, менеджер и

директор. Входящий телефонный звонок адресует-ся свободному оператору. Если оператор не можетобработать звонок, он автоматически перенаправля-ется менеджеру. Если менеджер занят, звонок пе-ренаправляется директору. Разработайте классы иструктуры данных для этой задачи. Реализуйте методdispatchCall(), который перенаправляет звонок перво-му свободному сотруднику.

8.3. Разработайте музыкальный автомат, используяпринципы ООП.

8.4. Разработайте паркинг, используя принципыООП.

8.5. Разработайте структуры данных для он-лайн-библиотеки.

8.6. Запрограммируйте игру в пазл. Разработайтеструктуры данных и объясните алгоритм, позволяю-щий решить задачу. Вы можете предположить, чтосуществует метод fitsWith, возвращающий значениеtrue в том случае, если два переданных кусочка пазладолжны располагаться рядом.

8.7. Как вы будете разрабатывать чат-сервер?Предоставьте информацию о компонентах бэкэнда,классах и методах. Перечислите самые трудные за-дачи, которые необходимо решить.

8.8. Правила игры «реверси» следующие. Каждаяфишка в игре с одной стороны белая, а с другой – чер-

ная. Когда ряд фишек оказывается ограничен фишка-ми противника (слева и справа или сверху и снизу),его цвет меняется на противоположный. Цель – захва-тить по крайней мере одну из фишек противника. Иг-ра заканчивается, когда у игрока не остается ходов.Побеждает тот, у которого больше фишек на поле. Ре-ализуйте ООП-модель для этой игры.

8.9. Объясните, какие структуры данных и алгорит-мы необходимо использовать для разработки файло-вой системы, хранящейся в оперативной памяти. На-пишите программный код, иллюстрирующий исполь-зование этих алгоритмов.

8.10. Спроектируйте и реализуйте хэш-таблицу, ис-пользующую связные списки для обработки коллизий.

Дополнительные вопросы: потоки и блокировки(16.3).

9. Рекурсия и динамическое

программирование

Существует огромное множество разнообразныхрекурсивных задач, но большинство из них укладыва-ются в определенные шаблоны. Подсказка – если за-дача рекурсивна, то она может быть разбита на под-задачи.

Когда вы получаете задание «Разработайте алго-ритм для вычисления N-го…», или «Напишите коддля вывода первых n…», или «Реализуйте метод длявычисления всех…» – скорее всего, речь пойдет о ре-курсии.

Практика – путь к совершенству! Чем больше задачвы решите, тем легче будет распознавать рекурсив-ные задачи.

С чего начать

Рекурсивные решения, по определению, основыва-ются на решении подзадач. Очень часто придется вы-числять f(n), добавляя, вычитая или еще как-либо из-меняя f(n-1). Следует принимать во внимание оба ти-па рекурсии: восходящую и нисходящую.

Восходящая рекурсияВосходящая рекурсия обычно более понятна. Мы

знаем, как решить задачу для самого простого случая,например как вывести один элемент, затем решаемзадачу для двух элементов, затем для трех и т. д. По-думайте о том, как создать решение для конкретногослучая, основываясь на предыдущем решении.

Нисходящая рекурсияНисходящая рекурсия выглядит чуть более слож-

ной, но она так же может понадобиться для решения

задач. В этом случае мы должны решить, как разде-лить задачу на N подзадач. Не забывайте про пере-крывающиеся случаи.

Динамическое программирование

Динамическое программирование (ДП) не оченьпопулярно на собеседованиях, поскольку задачи поэтой теме слишком сложны для 45-минутного интер-вью. Даже если хорошо подготовленные кандидатысмогут их решить, эти задачи – не самый удачный ме-тод оценки кандидата.

Если вам не повезло и вы получили задачу по ДП,подход будет аналогичен подходу к решению рекур-сивной задачи. Различие заключается в том, что про-межуточные результаты «кэшируются» для будущихвызовов.

Простой пример динамического

программирования: числа Фибоначчи

В качестве очень простого примера динамическогопрограммирования рассмотрим программу, генериру-ющую N-е число Фибоначчи. Просто, не так ли?

1 int fibonacci(int i) {2 if (i == 0) return 0;3 if (i == 1) return 1;

4 return fibonacci(i – 1) + fibonacci(i – 2);5 }Каково время выполнения этой функции? Вычисле-

ние N-го числа Фибоначчи зависит от предыдущих n–1 чисел. Но каждый вызов делает два рекурсивныхвызова. Это означает, что время выполнения соста-вит O(2n). График, приведенный ниже, показывает этоэкспоненциальное увеличение.

Время, потраченное на вычисление N-го числа Фи-боначчи в секундах

Всего одно небольшое изменение – и время, необ-ходимое на выполнение этой функции, уменьшитсядо O(N). Нужно всего лишь «кэшировать» результатыфункции fibonacci(i) между вызовами:

1 int[] fib = new int[max];

2 int fibonacci(int i) {3 if (i == 0) return 0;4 if (i == 1) return 1;5 if (fib[i]!= 0) return fib[i]; // Возвращаем кэширован-

ный результат.6 fib[i] = fibonacci(i – 1) + fibonacci(i – 2); // Кэшируем

результат7 return fib[i];8 }Генерирование 50-го числа Фибоначчи на стан-

дартном компьютере с помощью рекурсивной функ-ции займет более одной минуты. Метод динамическо-го программирования позволит сгенерировать 10 000-е число Фибоначчи за доли миллисекунды (но не за-бывайте, что размера типа int может оказаться недо-статочно).

В динамическом программировании нет ничегосложного – это все та же рекурсия, но с кэшировани-ем результатов. Так что реализуйте обычное рекур-сивное решение, а потом добавьте кэширование.

Рекурсивные и итерационные решения

Рекурсивные алгоритмы очень требовательны к па-мяти. Каждый рекурсивный вызов добавляет новыйслой в стек. Если ваш алгоритм использует O(n) ре-

курсивных вызовов, то для его работы понадобитсяO(n) памяти. Много!

Любой рекурсивный алгоритм можно превратить витерационный, хотя от этого код становится сложнее.Прежде чем написать рекурсивный код, задайте се-бе вопрос, как его можно преобразовать в итерацион-ный, и не забудьте поговорить на эту тему с интервью-ером.

Вопросы собеседования

9.1. Ребенок поднимается по лестнице из n ступе-нек, он может переместиться на одну, две или три сту-пеньки за один шаг. Реализуйте метод, рассчитываю-щий количество возможных вариантов прохожденияребенка по лестнице.

9.2. Представьте робота, сидящего в левом верх-нем углу сетки с координатами X, Y. Робот может пере-мещаться в двух направлениях: вправо и вниз. Сколь-ко существует маршрутов, проходящих от точки (0,0)до точки (X,Y).

ДополнительноПредположите, что на сетке существуют области,

которые робот не может пересекать. Разработайтеалгоритм построения маршрута от левого верхнего доправого нижнего угла.

9.3. В массиве A[0…n-1] задан «волшебный» ин-декс – A[i]=i. Учитывая, что массив отсортирован, на-пишите метод, чтобы найти этот «волшебный» ин-декс, если он существует в массиве A.

ДополнительноЧто произойдет, если значения окажутся одинако-

выми?9.4. Напишите метод, возвращающий все подмно-

жества одного множества.9.5. Напишите метод, возвращающий все переста-

новки строки.9.6. Реализуйте алгоритм, выводящий все коррект-

ные (правильно открытые и закрытые) комбинациипар круглых скобок.

Пример:Ввод: 3Вывод: ((())), (()()), (())(), ()(()), ()()()9.7. Реализуйте функцию заливки краской, кото-

рая используется во многих графических редакторах.Дана плоскость (двумерный массив цветов), точка ицвет, которым нужно заполнить все окружающее про-странство, окрашенное в другой цвет.

9.8. Дано неограниченное количество монет досто-инством 25, 10, 5 и 1 цент. Напишите код, определяю-щий количество способов представления n центов.

9.9. Дана шахматная доска размером 8×8. Напи-

шите алгоритм, находящий все варианты расстанов-ки восьми ферзей так, чтобы никакие две фигуры непопадали на одну горизонталь, вертикаль или диа-гональ. Учитываются не только главные, но и всеостальные диагонали.

9.10. Дан штабель из n ящиков шириной wi, высо-той hi и глубиной di. Ящики нельзя поворачивать, до-бавлять ящики можно только наверх штабеля. Каж-дый нижний ящик в стопке по высоте, ширине и глу-бине больше ящика, который находится на нем. Ре-ализуйте метод, позволяющий построить самый вы-сокий штабель (высота штабеля равна сумме высотвсех ящиков).

9.11. Дано логическое выражение, построенное изсимволов θ, 1, &, | и ^, и имеющее значение result.Напишите функцию, подсчитывающую количество ва-риантов логических выражений, дающих значениеresult.

Пример:Выражение: 1^θ|θ|1Результат: result=false(θ)Вывод: 2 способа: 1^((θ|θ)|1) и 1^(θ|(θ|1))

Дополнительные вопросы: связные списки (2.2,2.5, 2.7), стеки и очереди (3.3), деревья и графы (4.1,4.3, 4.4, 4.5, 4.7, 4.8, 4.9), головоломки (6.4), сорти-

ровка и поиск (9.5, 9.6, 9.7, 9.8), C++ (13.7), модериро-вание (17.13, 17.14), задачи повышенной сложности(18.4, 18.7, 18.12, 18.13).

10. Сортировка и поиск

Понимание общих принципов поиска и сортиров-

ки очень важно, так как большинство задач поискаи сортировки являются небольшими модификация-ми известных алгоритмов. Самый правильный подход– освоить известные алгоритмы сортировки и разо-браться, какой и когда следует применять.

Предположим, что вас попросили выполнить следу-ющее задание: провести сортировку очень большогомассива Person, упорядочив его элементы в соответ-ствии со значением возраста человека (в возрастаю-щем порядке).

Нам известно два факта:• Массив имеет большие размеры, значит, эффек-

тивность алгоритма очень важна.• Сортировка выполняется по возрасту, то есть зна-

чения имеют ограниченныйдиапазон. Рассмотрев различные алгоритмы, мы

понимаем, что нам идеально подходит блочная сорти-ровка. Если блоки будут достаточно маленькими (на-пример, 1 год), то время выполнения составит O(n).

Общие алгоритмы сортировки

Изучение (или повторение) алгоритмов сортировки– отличный способ повысить свои шансы на собесе-довании. Ниже приведено описание алгоритмов, наи-более популярных у интервьюеров.

Пузырьковая сортировка | Время выполнения вхудшем и среднем случае: O(n2). Память: O(1).

Обработка начинается с первых элементов мас-сива, они меняются местами, если первое значениебольше, чем второе. Затем мы переходим к следую-щей паре и так далее, пока массив не будет отсорти-рован.

Сортировка выбором | Время выполнения в худ-шем и среднем случае: O(n2). Память: O(1).

Сортировка выбором является вариантом преды-дущего алгоритма: просто, но неэффективно. С по-мощью линейного сканирования ищется наименьшийэлемент, а затем меняется местами с первым элемен-том. Затем с помощью линейного сканирования ищет-ся второй наименьший элемент и снова перемещает-ся в начало. Алгоритм продолжает работу, пока мас-сив не будет полностью отсортирован.

Сортировка слиянием | Время выполнения в худ-шем и среднем случае: O(n log(n)).

Память: зависит от задачи.При сортировке слиянием массив делится попо-

лам, каждая половина сортируется по отдельности, изатем делается обратное объединение. К каждой изполовин применяется один и тот же алгоритм сорти-ровки. В итоге вы объединяете два массива, состоя-щие из одного элемента.

Метод слияния копирует все элементы из целевогомассива во вспомогательные, разделяя левую и пра-вую половины (helperLeft и helperRight). Мы «двигаем-ся» по вспомогательному массиву helper, копируя наи-меньший элемент каждой половины в массив. В ито-ге мы копируем оставшиеся элементы в целевой мас-сив.

1 void mergesort(int[] array, int low, int high) {2 if (low < high) {3 int middle = (low + high) / 2;4 mergesort(array, low, middle); // Сортируем левую

половину5 mergesort(array, middle + 1, high); // Сортируем

правую половину6 merge(array, low, middle, high); // Объединяем их7 }8 }910 void merge(int[] array, int low, int middle, int high) {

11 int[] helper = new int[array.length];1213 /* Копируем обе половины во вспомогательный

массив */14 for (int i = low; i <= high; i++) {15 helper[i] = array[i];16 }1718 int helperLeft = low;19 int helperRight = middle + 1;20 int current = low;2122 /* Проходимся по вспомогательному массиву.

Сравниваем левую и правую23 * половины, копируем обратно наименьший эле-

мент из двух половин24 * в исходный массив. */25 while (helperLeft <= middle && helperRight <= high)

{26 if (helper[helperLeft] <= helper[helperRight]) {27 array[current] = helper[helperLeft];28 helperLeft++;29 } else { // Если правый элемент меньше, чем ле-

вый30 array[current] = helper[helperRight];31 helperRight++;

32 }33 current++;34 }3536 /* Копируем оставшуюся часть левой стороны

массива37 * в целевой массив */38 int remaining = middle – helperLeft;39 for (int i = 0; i <= remaining; i++) {40 array[current + i] = helper[helperLeft + i];41 }42 }Обратите внимание, что в целевой массив скопи-

рованы только оставшиеся элементы левой полови-ны вспомогательного массива. Почему не правой по-ловины? Правая половина и не должна копироваться,потому что она уже там.

Рассмотрим для примера массив [1, 4, 5 || 2, 8, 9](знак || указывает точку раздела).

До момента слияния половин оба массива – вспо-могательный и целевой – заканчиваются элементами[8, 9]. Когда мы копируем в целевой массив большечетырех элементов (1, 4, 5, и 2), элементы [8, 9] про-должают оставаться в обоих массивах. Нет никакойнеобходимости копировать их.

Быстрая сортировка | Время выполнения в сред-

нем случае: O(n log(n)), в худшем случае: O(n2). Па-мять: O(log(n)).

При быстрой сортировке из массива выбираетсяслучайный (опорный) элемент, и все элементы масси-ва располагаются по принципу: меньшие – равные –большие относительно выбранного элемента. Такуюдекомпозицию эффективнее всего осуществлять че-рез перестановки (см. далее).

Если мы будем много раз делить массив (и его под-массивы) относительно случайного элемента, то в ре-зультате получим отсортированный массив. Посколь-ку опорный элемент не является медианой (даже при-ближенно), наша сортировка окажется очень медлен-ной – в худшем случае O(n2).

1 void quickSort(int arr[], int left, int right) {2 int index = partition(arr, left, right);3 if (left < index – 1) { // Сортируем левую половину4 quickSort(arr, left, index – 1);5 }6 if (index < right) { // Сортируем правую половину7 quickSort(arr, index, right);8 }9 }1011 int partition(int arr[], int left, int right) {12 int pivot = arr[(left + right) / 2]; // Выбираем цен-

тральную точку13 while (left <= right) {14 // Находим элемент слева, который должен быть

справа15 while (arr[left] < pivot) left++;1617 // Находим элемент справа, который должен

быть слева18 while (arr[right] > pivot) right-;1920 // Меняем местами элементы и перемещаем ле-

вые и правые индексы21 if (left <= right) {22 swap(arr, left, right); // Меняем местами элементы23 left++;24 right-;25 }26 }27 return left;28 }Поразрядная сортировка | Время выполнения в

среднем случае: O(n log(n)), в худшем случае: O(kn).Поразрядная сортировка – это алгоритм сортиров-

ки целых (и некоторых других) чисел, использующийфакт, что целые числа представляются конечным чис-лом битов.

Мы группируем числа по каждому разряду. Напри-мер, массив целых чисел сначала сортируется по пер-вому разряду (чтобы все 0 собрались в группу). Затемкаждая из групп сортируется по следующему разряду.Процесс повторяется, пока весь массив не будет от-сортирован.

В отличие от алгоритмов сортировки с использова-нием сравнения, которые в большинстве случаев немогут выполняться быстрее, чем за O(log(n)), данныйалгоритм в худшем случае дает результат O(kn), где n– количество элементов в массиве, а k – количествопроходов алгоритма сортировки.

Алгоритмы поиска

Когда мы думаем об алгоритмах поиска, мы обычноподразумеваем бинарный поиск. Действительно, этоочень полезный алгоритм. Заметьте, что хотя концеп-ция довольно проста, разобраться во всех нюансахсложнее, чем кажется на первый взгляд. Изучите при-веденный ниже код и обратите внимание на плюс иминус единицы.

1 int binarySearch(int[] a, int x) {2 int low = 0;3 int high = a.length – 1;4 int mid; 5

6 while (low <= high) {7 mid = (low + high) / 2;8 if (a[mid] < x) {9 low = mid + 1;10 } else if (a[mid] > x) { 11 high = mid – 1; 12 } else {13 return mid;14 } 15 } 16 return -1; // Ошибка 17 }1819 int binarySearchRecursive(int[] a, int x, int low, int

high) { 20 if (low > high) return -1; // Ошибка21 22 int mid = (low + high) / 2;23 if (a[mid] < x) { 24 return binarySearchRecursive(a,

x, mid + 1, high); 25 } else if (a[mid] > x) { 26 returnbinarySearchRecursive(a, x, low, mid – 1); 27 } else {

28 return mid;29 } 30 }Множество разновидностей поиска структур дан-

ных не ограничиваются вариациями бинарного поис-ка, поэтому приложите максимум усилий для их изу-чения. Можно, например, искать узел, используя би-нарные деревья или хэш-таблицы. Не ограничивайтесвои возможности!

Вопросы собеседования

10.1. Дано: два отсортированных массива A и B.

Размер массива A (свободное место в конце) позво-ляет поместить в него массив B. Напишите метод сли-яния массивов B и A, сохраняющий сортировку.

10.2. Напишите метод сортировки массива строк,при котором анаграммы группируются друг за другом.

10.3. Дано: отсортированный массив из n целых чи-сел, который был циклически сдвинут произвольноечисло раз. Напишите код для поиска элемента в мас-сиве. Исходите из предположения, что массив изна-чально был отсортирован по возрастанию.

Пример:Ввод: найдите индекс элемента со значением 5в

{15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14} Вывод: 8.10.4. Дано: файл размером 20 Гбайт, содержащий

строки. Как выполнить сортировку такого файла?10.5. Дано: отсортированный массив, состоящий из

строк, разделенных пустыми строками. Напишите ме-тод для обнаружения позиции заданной строки.

Пример:Ввод: найдите индекс элемента "ball" в массиве

{"at", " ", " ", " ","ball", " ", " ","car", " "," ","dad", " "," "}Вывод: 410.6. Дано: матрица размером M×N, строки и колон-

ки которой отсортированы. Напишите метод нахожде-ния элемента.

10.7. Цирк готовит новый аттракцион – пирамида из

людей, стоящих на плечах друг у друга. Простая ло-гика подсказывает, что люди, стоящие выше, должныбыть ниже ростом и легче, чем люди, находящиеся восновании пирамиды. Учитывая информацию о ростеи весе каждого человека, напишите метод, вычисля-ющий наибольшее число человек в пирамиде.

Пример:Ввод (ht, wt): (65, 100) (70, 150)(56, 90)(75, 190)(60,

95) (68, 110)Вывод: максимальная высота пирамиды – 6 чело-

век, сверху вниз: (56, 90)(60, 95) (65, 100)(68, 110)(70,150)(75, 190)

10.8. Вы обрабатываете поток целых чисел. Перио-дически вам нужно находить ранг числа x (количествозначений <= x). Какие структуры данных и алгорит-мы необходимы для поддержки этих операций? Реа-лизуйте метод track(int x), вызываемый при генериро-вании каждого символа, и метод getRankOfNumber(intx), возвращающий количество значений <=x (не вклю-чая x).

Пример:Поток (в порядке появления): 5, 1, 4, 4, 5, 9, 7, 13, 3getRankOfNumber(1)= 0getRankOfNumber(3)= 1getRankOfNumber(4)= 3

Дополнительные вопросы: массивы и строки(1.3), рекурсия (8.3), модерирование (17.6, 17.12), во-просы повышенной сложности (18.5).

11. Масштабируемостьи ограничения памяти

Несмотря на пугающее название, вопросы о мас-

штабируемости чаще всего оказываются самыми лег-кими. Нет никаких ловушек и необычных алгоритмов(по крайней мере обычно их не бывает). Вам не нуж-но посещать спецкурсы по распределенным систе-мам или иметь опыт системного проектирования. Лю-бой умный программист с небольшим опытом можетнепринужденно ответить на все эти вопросы.

Пошаговый подход

Интервьюеры не пытаются проверить ваши знанияв области системного проектирования. Фактически,интервьюеры чаще всего проверяют только знаниеоснов информатики. Приведенная ниже последова-тельность действий отлично помогает при решениимногих задач системного проектирования.

Шаг 1. Абстрагируйтесь от реальности

Представьте, что все данные хранятся на одномкомпьютере и не существует никаких ограничений па-мяти. Как бы вы решили задачу? Ответ на этот вопроспозволит построить общую схему решения.

Шаг 2. Вернитесь к реальностиВернитесь к исходной задаче. Сколько данных мож-

но разместить в одном компьютере? Какие проблемымогут возникнуть, если вы разделите данные? Обыч-но достаточно выяснить, как разделить данные и какдать понять одному из компьютеров, где находитсянедостающая информация.

Шаг 3. Решите задачуПодумайте о том, как избавиться от обнаруженных

проблем. Помните, что решение может полностью ис-ключить проблему или немного улучшить ситуацию.Скорее всего, вам будет достаточно слегка модифи-цировать исходный алгоритм (шаг 1), но иногда еготребуется существенно изменить.

Используйте итерационный подход. Как только про-блемы, появившиеся на втором шаге, будут устране-ны, могут появиться новые, и вам придется занятьсяими.

Ваша цель – не спроектировать сложную систему,на которую компании придется потратить миллионы

долларов, а продемонстрировать, что вы можете ана-лизировать и решать задачи подобного плана.

Что нужно знать: информация,

стратегия и проблема

Типичная система

Хотя суперкомпьютеры еще не канули в Лету,многие веб-ориентированные компании используютогромные распределенные системы. Скорее всего,вам придется работать в такой системе.

Заполните следующую таблицу перед собеседова-нием, она поможет запомнить, сколько данных можетнаходиться на компьютере.

Конец ознакомительного

фрагмента.

Текст предоставлен ООО «ЛитРес».Прочитайте эту книгу целиком, купив полную ле-

гальную версию на ЛитРес.Безопасно оплатить книгу можно банковской кар-

той Visa, MasterCard, Maestro, со счета мобильноготелефона, с платежного терминала, в салоне МТСили Связной, через PayPal, WebMoney, Яндекс.День-ги, QIWI Кошелек, бонусными картами или другимудобным Вам способом.