Интеллектуальные развлечения. Интересные иллюзии, логические игры и загадки.

Добро пожаловать В МИР ЗАГАДОК, ОПТИЧЕСКИХ
ИЛЛЮЗИЙ И ИНТЕЛЛЕКТУАЛЬНЫХ РАЗВЛЕЧЕНИЙ
Стоит ли доверять всему, что вы видите? Можно ли увидеть то, что никто не видел? Правда ли, что неподвижные предметы могут двигаться? Почему взрослые и дети видят один и тот же предмет по разному? На этом сайте вы найдете ответы на эти и многие другие вопросы.

Log-in.ru© - мир необычных и интеллектуальных развлечений. Интересные оптические иллюзии, обманы зрения, логические флеш-игры.

Привет! Хочешь стать одним из нас? Определись…    
Если ты уже один из нас, то вход тут.

 

 

Амнезия?   Я новичок 
Это факт...

Интересно

По-французски «разглядывать витрины» – «faire du leche-vitrines», т. е. «облизывать витрины».

Еще   [X]

 0 

Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию (Макдауэлл Гейл)

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

Год издания: 2012

Цена: 386 руб.



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

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

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

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


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

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

   CRACKING THE CODING INTERVIEW
   5th Edition

   150 Programming Interview Questions and Solutions

   GAYLE LAAKMANN MCDOWELL
   Founder and CEO, CareerCur.com

   CareerCur, LLC
   Palo 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 GPA[1]) в Вашингтонском университете – одной из лучших школ мира по компьютерным дисциплинам, – и он активно занимался OpenSource-проектами. Он был энергичен, креативен, он упорно трудился и был компьютерным фанатом в хорошем смысле этого слова.
   Но, к сожалению, члены комиссии были неумолимы, и я должна была согласиться с их мнением. Даже если бы сыграла свою роль моя рекомендация, моему ученику отказали бы на более поздних этапах отбора. Слишком много было «красных» карточек.
   Интервьюеры ожидали, что он проявит креативность мышления, а он просто изо всех сил решал задачи, поставленные на собеседовании. Более успешные кандидаты быстро разобрались с первым вопросом, который был построен на известной задаче. А у моего студента возникли проблемы с разработкой алгоритма. Когда он наконецто осилил алгоритм, то не смог оптимизировать решения для других сценариев. Когда дело дошло до написания кода, он допустил множество ошибок. Это был не худший кандидат, но все видели, как он далек от победы.
   Пару недель спустя он подошел ко мне, а я не знала, что сказать. Нужно стать еще умнее? Дело было не в этом, я знала, что у него блестящий ум. Научиться лучше программировать? Нет, его навыки были не хуже, чем у других программистов, которых я только знала.
   Он тщательно готовился, как и большинство кандидатов. Он изучил K&R[2] и CLRS[3]. Он может описать в подробностях множество способов балансировки дерева и умеет делать на C такие вещи, которые большинству программистов просто не снились.
   Мне пришлось сказать ему горькую правду – книжного академического образования недостаточно. Книги – это замечательно, но они не помогут вам пройти собеседование. Почему? Подскажу: интервьюеры не встречали «деревьев» со времен обучения в университете.
   Собеседование – не университетский экзамен, там вас ждут реальные вопросы и практические задачи. Книга «Карьера программиста» основана на опыте моего практического участия во множестве собеседований, проводимых лучшими компаниями. Это квинтэссенция сотен интервью с множеством кандидатов, результат ответов на тысячи вопросов, задаваемых кандидатами и интервьюерами в ведущих мировых корпорациях. В эту книгу из тысяч задач и вопросов были отобраны 150 наиболее интересных.

Мой подход

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

Моя страсть

   Мой первый «официальный» преподавательский опыт я получила в колледже Пенсильванского университета на должности ассистента преподавателя, это был курс информатики.
   Как инженеру Google, мне всегда нравилось обучать и воспитывать «нуглеров» (nooglers) – так в Google называют новичков. Я уделяла 20 % времени преподаванию курса информатики в Вашингтонском университете.
   Эта книга и сайт CareerCup.com – отражения моей страсти к преподаванию. Даже сейчас вы можете найти меня на CareerCup.com, где я помогаю пользователям. Присоединяйтесь к нам!
   Гэйл Лакман Макдауэлл

   Зарегистрируйтесь на сайте http://www.crackingthecodinginterview.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.

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

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

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

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

   Для большинства кандидатов собеседование похоже на черный ящик. Вы входите, получаете вопросы и выходите… с предложением работы или без него. Задавались ли вы вопросами:
   • Как принимаются решения?
   • Общаются ли интервьюеры друг с другом?
   • Что интересует компанию?
   Скоро вы узнаете ответы!
   Специально для этой книги мы нашли экспертов-интервьюеров от пяти ведущих компаний – Microsoft, Google, Amazon, Yahoo! и Apple, – чтобы узнать из первых рук, что происходит там, за кулисами.
   Эти эксперты рассказали нам про типичное собеседование и поведали, что происходит после того, как вы уходите.
   От них мы узнали, чем различаются собеседования – от Amazon до Google. У каждой компании есть особенности, знание которых позволит вам избежать ситуации, когда один строгий экзаменатор из Amazon или два из Apple указывают вам на дверь.
   Кроме того, эксперты поведали нам, на что в первую очередь обращают внимание. Компании, занимающиеся разработкой программного обеспечения, фокусируются на алгоритмах и коде. В других компаниях могут быть другие специфические приоритеты. Зная особенности компании, вы сможете лучше подготовиться.
   Поэтому присоединяйтесь к нам, поскольку мы собираемся заглянуть за кулисы Microsoft, Google, Amazon, Yahoo! и Apple.

Microsoft

   Итак, типичное собеседование от Microsoft. Однажды утром вы появляетесь в офисе и заполняете предварительные документы. Затем вас ждет короткое собеседование со специалистом по подбору кадров, который задаст ряд несложных вопросов. Задача этого специалиста – подготовить вас к интервью, а не мучить техническими вопросами. Он должен помочь вам собраться, для того чтобы вы меньше нервничали на настоящем собеседовании.
   Будьте вежливы со специалистом по подбору кадров. Он будет вашим адвокатом в том случае, если вы провалитесь на первом собеседовании. Он поможет вам попасть на повторное собеседование. Рекрутеры могут отстаивать ваши интересы вне зависимости от того, будете вы наняты или нет.
   Вам предстоят четыре или пять собеседований, зачастую с разными командами интервьюеров. В отличие от других компаний, где вы встречаетесь с экзаменаторами в конференц-зале, вы будете беседовать с интервьюерами в их офисе. Рассматривайте эти собеседования как возможность прочувствовать командный дух.
   Интервьюеры могут сказать, какое впечатление вы на них произвели (или, наоборот, не сказать). Когда интервью закончено, с вами может побеседовать специалист из отдела кадров, но только если вы успешно прошли собеседование. Знайте, если вы увидели менеджера по кадрам – это хороший знак!
   Решение вам сообщат в течение дня или, максимум, недели. Если неделя прошла, а вы не получили никаких известий от рекрутера, напомните ему о себе по электронной почте.
   Не забывайте, что отсутствие ответа может означать лишь то, что ваш рекрутер рассеянный или очень занятой человек, а не то, что вам отказали.
   Подготовиться!
   Почему вы хотите работать именно в Microsoft?
   В ответе на этот вопрос Microsoft хочет услышать, что вы увлечены их технологиями. Лучший ответ выглядит примерно так: «Я всегда использовал программное обеспечение Microsoft, и действительно впечатлен тем, как Microsoft удается создавать превосходный программный продукт. Например, я использовал Visual Studio для программирования игр, а API просто превосходен». Покажите свое увлечение технологией!
   Особенности
   Вы будете иметь беседу с менеджером по кадрам только в том случае, если вы прошли собеседование. Расценивайте разговор с менеджером как хороший знак.

Amazon

   В Amazon процесс обычно начинается с пары скрининговых интервью по телефону, во время которых кандидат беседует с разными командами. Впрочем, собеседований может быть и больше – это означает, что интервьюеры сомневаются или же вас рассматривают как кандидата в несколько команд. Реже ограничиваются одним скрининговым интервью. Так происходит, если кандидат знаком интервьюерам или недавно проходил собеседование на другую вакансию.
   Затем вас приглашают в Сиэтл. Вам предстоит пройти еще четыре или пять собеседований с одной или двумя командами, которые выбрали вас на основании резюме и телефонного интервью. Вам предложат написать программный код, чтобы другие интервьюеры смогли оценить ваши навыки. У каждого интервьюера свой профиль, поэтому вопросы могут сильно различаться. Интервьюер не может знать решение коллег до тех пор, пока не поставит собственную оценку.
   У собеседования в Amazon есть особенность – главный интервьюер (bar riser). Он проходит специальную подготовку и может общаться с кандидатами вне пределов их группы, чтобы сбалансировать группу в целом. Если вопросы одного из интервьюеров оказываются более сложными, чем у остальных, скорее всего, это главный интервьюер. У него огромный опыт в проведении собеседований, и его решение может быть окончательным. Помните: если в собеседовании с главным интервьюером вы показали себя с хорошей стороны, это еще не означает, что решения других интервьюеров не будут учитываться.
   Как только интервьюеры выставили оценки, они встречаются, чтобы принять окончательное решение. В большинстве случаев HR-менеджеры от Amazon превосходно выполняют свои обязанности, но и у них бывают накладки. Если вы не получили ответ в течение недели, напомните о себе по электронной почте.
   Подготовиться!
   Amazon – веб-ориентированная компания, и она беспокоится о масштабировании. Убедитесь, что вы готовы к вопросам о модульном наращивании систем. Для лучшей подготовки к вопросам интервьюеров прочитайте главу «Масштабируемость и ограничения памяти». В Amazon любят задавать вопросы по объектно-ориентированному программированию. Прочитайте главу 8 «Объектно-ориентированное проектирование».
   Особенности
   Вы должны произвести должное впечатление на главного интервьюера и менеджера по найму, если хотите пройти собеседование и получить должность.

Google

   Прежде всего инженер Google побеседует с вами по телефону, так что ожидайте технических вопросов. Эти вопросы могут включать в себя написание кода, иногда через совместную работу с документом. Обычно кандидатам задаются одинаковые вопросы и при телефонном собеседовании, и на личной встрече.
   На личном собеседовании с вами будут общаться от четырех до шести интервьюеров, в том числе и главный интервьюер (lunch interviewer). Решение интервьюера является тайной, никто не знает, что думает его коллега. Вы можете быть уверены, что интервьюер дает независимую оценку.
   У интервьюеров нет согласованной «структуры» или «системы» вопросов. Вам могут задать любой вопрос, который посчитают нужным. Затем результаты собеседования передаются в комитет по подбору персонала, инженеры и менеджеры которого принимают решения о приеме на работу. Обычно оцениваются четыре критерия (аналитические способности, навыки программирования, опыт и коммуникативные способности), по каждому из них выставляются оценки от 1.0 до 4.0. Интервьюеры обычно не участвуют в работе комитета по подбору персонала, поэтому они не могут повлиять на решение. Решающую роль играют ваши оценки. Комитет хочет видеть ваши преимущества по отношению к другим кандидатам. Оценки 3.6, 3.1, 3.1, 2.6 предпочтительнее, чем все 3.1.
   Не обязательно становиться лучшим на каждом собеседовании, телефонное собеседование тоже не является решающим фактором. Если комитет по подбору персонала принял положительное решение, ваш пакет документов будет направлен в комитет, занимающийся назначением заработной платы, затем в исполнительный управляющий комитет. Принятие окончательного решения затягивается на несколько недель, поскольку Google имеет множество разных уровней и комитетов.
   Подготовиться!
   Google – веб-ориентированная компания, заинтересованная в разработке наращиваемых модульных систем. Поэтому убедитесь, что вы изучили вопросы из главы «Масштабируемость и ограничения памяти». Интервьюеры Google любят задавать вопросы из раздела «Поразрядная обработка», поэтому убедитесь, что вы разобрались в этой теме.
   Особенности
   Ваши интервьюеры не принимают решение о найме, их оценки передаются в комитет по подбору персонала, который дает рекомендации (принять или отказать) исполнительному комитету Google.

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!

   На протяжении собеседования вам предстоит пройти 6–7 интервью длительностью около 45 минут каждое. Интервьюеры специализируются на конкретных областях. Например, один экзаменатор специализируется на базах данных, другой – на компьютерной архитектуре и т. д. Обычно распорядок интервью следующий:
   • 5 минут – общее знакомство, вы рассказываете о себе, о своих проектах и т. д.
   • 20 минут – вопросы по кодингу. Вас могут попросить, например, реализовать сортировку слиянием.
   • 20 минут – системное проектирование. Вам предложат спроектировать большой распределенный кэш. Эти вопросы часто строятся на вашем предыдущем опыте.
   В конце дня вы, скорее всего, встретитесь с ведущим разработчиком (руководителем). Разговор может быть о чем угодно. Вы можете просматривать демоверсии продуктов, рассуждать о развитии компании или вашей роли в ней. Обычно такая беседа не является решающим фактором.
   Тем временем интервьюеры обсудят ваши результаты и попытаются прийти к решению. Окончательное решение принимает менеджер по подбору персонала, взвесив ваши сильные и слабые стороны.
   Если вы подходите, то вы чаще всего (но не всегда) узнаете об этом в тот же день. Существует множество причин, по которым на принятие решения понадобится несколько дней. Например, есть еще несколько кандидатов, которые должны пройти собеседование.
   Подготовиться!
   Как правило, в Yahoo! задают вопросы, связанные с системным проектированием, так что подготовьтесь к ним. Вы должны уметь не только написать код, но и разработать программное обеспечение.
   Особенности
   Интервью проводится не рядовыми менеджерами по набору персонала. Для Yahoo! характерно то, что решение (приняты вы или нет) обычно принимается в день собеседования. Ваши интервьюеры обсуждают результаты, пока вы встречаетесь с последним экзаменатором.

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

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

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

Тестеры и SDET

   Если вы претендуете на должность тест-программиста:
   • Подготовьтесь к базовым задачам тестирования. Как вы будете тестировать лампочку? Ручку? Кэш-регистр? Microsoft Word? Глава 12 «Тестирование» поможет ответить на эти вопросы.
   • Подготовьтесь к заданиям, связанным с программированием, – тестер обязан уметь программировать. Хотя требования к SDET ниже, чем для SDE (Software Design Engineer, разработчик программного обеспечения), вам необходимо разбираться в алгоритмах. Убедитесь, что вы можете справиться с заданиями по алгоритмизации и программированию, которые даются обычным разработчикам программного обеспечения.
   • Совершенствуйте навыки тестера и программиста. В качестве примера возьмем очень популярное задание: «Какой код нужно написать, чтобы получить X?» Далее обычно следует: «Ок, а теперь протестируйте его». Даже если вас об этом не спросили, уточните: «Как именно нужно протестировать код?» Помните: любое задание может превратиться в тест-задачу.
   Для тестеров программного обеспечения очень важны коммуникативные навыки, поскольку им приходится работать с людьми. Не игнорируйте часть V «Подготовка к поведенческим вопросам».
   Совет
   В завершении этого раздела хочу дать вам небольшой совет, способствующий карьерному росту. Если вы, как и многие другие кандидаты, расцениваете должность тестера как стартовую должность в компании, не обольщайтесь. Для многих кандидатов переход с этой должности на должность разработчика программного обеспечения оказался трудным испытанием. Если вы все-таки решились на этот шаг, убедитесь в том, что сохранили все свои навыки программирования и алгоритмизации, и попробуйте осуществить переход в течение одного-двух лет – чем больше пройдет времени, тем сложнее это сделать.
   Не позволяйте атрофироваться навыкам программирования.

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

   PM[5] – общая аббревиатура, которой обозначают как менеджеров программ, так и менеджеров продукта. Но роли и задачи этих двух PM сильно различаются даже в пределах одной компании. В Microsoft, например, некоторые PM, по сути, выполняют функции маркетологов, то есть больше общаются с клиентами, нежели программируют. А вот в других компаниях PM могут провести большую часть своего рабочего дня, занимаясь программированием.
   Когда интервьюеры ищут кандидата на должность PM, они ищут человека, способного продемонстрировать следующие навыки:
   • Обработка неоднозначностей. Это не самая главная часть собеседования, но вы должны знать, что интервьюеры приветствуют подобные навыки. Им важно понять, что вы будете делать, когда столкнетесь с неоднозначной ситуацией. Поэтому постарайтесь продемонстрировать, что вы не остановитесь, займетесь поиском новой информации, расстановкой приоритетов и решите задачу. Обычно кандидатов не просят решать конкретную задачу (хотя и такое может быть), достаточно рассказать, что вы будете делать в такой необычной ситуации.
   • Потребительский фокус. Интервьюеры хотят видеть, что вам хорошо знакома целевая аудитория. Вы твердо уверены, что все потенциальный потребители будут использовать программный продукт точно так же, как и вы? Или вы способны взглянуть на продукт с точки зрения клиента и попытаетесь понять, как он будет пользоваться программой? Ожидайте заданий типа «Разработайте будильник для слепого». Вы должны понимать, кто является вашей целевой аудиторией и как он будет использовать продукт. Необходимые навыки описаны в главе 12 «Тестирование».
   • Потребительский фокус (технические навыки). Некоторые команды, работающие со сложными продуктами, хотят убедиться, что их PM понимают сам продукт. Трудно быть эффективным менеджером продукта или программы, если не знаешь, как это работает. Близкое знакомство со всеми существующими клиентами мгновенного обмена сообщениями, вероятно, окажется бесполезным для работы в команде MSN Messenger, но понимание задач безопасности является необходимым условием для работы в Windows Security.
   • Коммуникативные способности. PM должен уметь общаться с сотрудниками компании всех уровней подготовки и любого статуса. Ваш интервьюер захочет убедиться, что вы обладаете подобной способностью. Это легко проверяется, например, с помощью простого задания «Объясните, что такое TCP/IP, своей бабушке». Ваши коммуникативные способности легко оцениваются по рассказу о вашей предыдущей работе.
   • Страсть к новым технологиям. Счастливые сотрудники – это продуктивные сотрудники, поэтому компания должна убедиться, что вы будете получать удовольствие от работы. В ваших ответах должно прозвучать, что вы увлекаетесь новыми технологиями и можете работать в команде. Вас могут спросить: «Чем вам привлекает Microsoft?» Интервьюеры ожидают увидеть энтузиазм в вашем рассказе о предшествующем опыте и задачах команды. Они хотят видеть, что вы стремитесь решать сложные задачи.
   • Работа в команде/лидерство. Это может стать решающим моментом собеседования – ведь это и есть ваша работа. Все интервьюеры пытаются оценить то, как хорошо вы работаете с другими людьми. Интервьюер будет рад видеть, что вы способны справиться с конфликтами, берете на себя инициативу, вы понимаете коллектив, и людям нравится работать с вами. Вам следует уделить должное внимание поведенческим вопросам.
   Все перечисленные навыки важны для PM и являются ключевыми для собеседования. Значимость каждой области примерно одинакова.
Ведущие разработчики и менеджеры
   Отличные навыки программирования являются необходимым условием для ведущих разработчиков и очень часто требуются и от «управленцев». Если ваша работа будет связана с программированием, убедитесь, что ваши познания в алгоритмизации и программировании находятся на достаточно высоком уровне. Например, требования Google к менеджерам существенно выше, чем к обычным программистам.
   Дополнительно вас будут оценивать по следующим критериям:
   • Работа в команде/лидерство. Претендент на любую руководящую должность обязан быть лидером и уметь работать с людьми. На интервью вас будут оценивать явно и неявно. При открытой оценке вам задают вопрос: «Что вы будете делать, если не согласны с менеджером?» Неявная оценка проводится по результатам вашего общения с интервьюерами. Интервьюер сразу увидит, что вы высокомерны или, наоборот, слишком мягки, чтобы стать лидером (руководителем).
   • Расстановка приоритетов. Менеджеры часто сталкиваются со щекотливыми вопросами, например как убедиться, что команда укладывается в сроки. Ваши интервьюеры хотят видеть, что вы способны правильно разложить все «по полочкам» и расставить приоритеты.
   • Коммуникативные навыки. Менеджерам приходится много общаться с людьми, стоящими как выше, так и ниже их по карьерной лестнице. Они должны общаться с потенциальными клиентами и менее технически подкованными людьми. Интервьюеры хотят видеть, что вы способны общаться с разными людьми, оставаясь дружелюбными и доброжелательными. По сути, на собеседовании делается слепок вашей личности.
   • Доведение дела до конца. Менеджер должен быть человеком, который всегда добивается своей цели. Вам необходимо найти баланс между подготовкой к проекту и его реализацией. Менеджер должен знать, как структурировать проект и как мотивировать людей, только так можно достичь цели.
   В конечном счете, все эти критерии относятся к вашему предыдущему опыту и к вашей личности. Убедитесь, что хорошо подготовились, и проверьте таблицу подготовки к собеседованию (см. с. 40).

Стартап

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

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

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

Резюме

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

   • Подгонка личности. Установите дружеские отношения с интервьюерами – это залог получения вакансии.
   • Набор навыков. Поскольку стартапам нужны люди, которые сразу могут приступить к работе, они будут оценивать ваши навыки программирования на конкретном языке. Если вы знакомы с языком, на котором работает стартап, повторите его основы.
   • Предыдущий опыт. Стартапперы задают много вопросов о предыдущем опыте.
   Уделите особое внимание части V «Подготовка к поведенческим вопросам».
   В дополнение к перечисленным критериям на собеседовании часто задаются вопросы по программированию и алгоритмизации, которые вы найдете в этой книге.

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

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

   Для студентов могут быть полезны следующие рекомендации:
   • Принимайте участие в больших проектах. Даже если вы еще учитесь, не отказывайтесь от участия в больших проектах. Такой опыт можно будет упомянуть в резюме, а это повысит ваши шансы на собеседованиях в крупных компаниях. Чем больше проект связан с реальными задачами, тем лучше.
   • Попробуйте начать какой-либо проект. Собственные проекты производят впечатление на любую компанию. Такая работа не только увеличивает ваш технический опыт, но и показывает, что вы инициативны и можете достичь поставленной цели. Используйте выходные дни для разработки собственного программного обеспечения. Если у вас есть научный руководитель, можно попытаться получить грант под вашу работу.
   Профессионалы тоже должны обладать правильным опытом, который позволит попасть в компанию их мечты. Вы можете работать в Google, но мечтаете о Facebook. А может, вы работаете тестером, но стремитесь попасть в более крупную компанию или хотите заниматься разработкой программ. В этом случае вам пригодятся следующие советы:
   • Сделайте так, чтобы ваши рабочие обязанности максимально приблизились к задачам программирования. Не показывайте своему руководству, что вы думаете об уходе, но уделите больше внимания программированию. Стремитесь к участию в крупных проектах – это дополнительный плюс для вашего резюме.
   • Используйте все свободное время – ночи и выходные дни. Если у вас появилось несколько минут или часов, займитесь разработкой любого приложения – мобильного, настольного или веб-приложения – все пойдет вам в плюс. Выполняя такие проекты, вы получаете опыт. Старайтесь использовать новые технологии, чтобы идти в ногу со временем. Обязательно упомяните эти проекты в резюме: люди, разрабатывающие программы «ради собственного удовольствия», производят хорошее впечатление на интервьюеров.
   Компании хотят увидеть, что вы умны и что вы умеете программировать. Если вы можете это доказать, у вас больше шансов пройти собеседование.
   Нужно заранее думать о развитии вашей карьеры – какой дорогой она должна пойти? Если вы собираетесь идти по пути менеджмента, то, даже если в настоящий момент вы ищете вакансию разработчика, стремитесь развивать качества лидера.

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

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

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

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

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

   Вам помогут несколько простых советов:
   1. Используйте Интернет. Сайты вроде Meetup.com или социальные сети помогут вам отслеживать события, связанные с областью ваших интересов и вашими целями. Если у вас до сих пор нет своей визитной карточки – вы студент или безработный, – срочно решите эту задачу.
   2. Не бойтесь знакомиться с людьми. Вы волнуетесь или стесняетесь? Не переживайте, от простого «здравствуйте!» хуже вам не станет. Что может произойти? Если человеку вы не понравитесь, он просто не станет с вами знакомиться, и вы его больше не увидите.
   3. Будьте открыты, говорите о своих интересах. Если кто-то создает стартап или рассказывает что-то интересное для вас, пригласите его на чашечку кофе.
   4. Отслеживайте события на LinkedIn или пригласите человека на чашку кофе, если его стартап покажется вам интересным.
   5. Будьте доброжелательны – и это главное. Люди захотят помочь вам, если вы по
   могли им. Помните: круг знакомств – это не только люди, с которыми вы знакомы лично. В наши дни круг знакомств можно существенно расширить благодаря Интернету – вам помогут блоги, Facebook и электронная почта. Но не забывайте – если общение происходит только онлайн, сложнее установить связь и получить желаемое.

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

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

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

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

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

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

   • «Благодаря моей реализации распределенного кэша было достигнуто сокращение времени прорисовки на 75 %, что в свою очередь привело к сокращению времени входа в систему» на 10 %.
   • «Благодаря использованию windiff при реализации нового алгоритма сравнения средняя точность совпадений выросла с 1,2 до 1,5».
   Конечно, не нужно пытаться формализовать все ваши достижения, но принцип, думаю, ясен. Нужно показать, что вы сделали, как вы сделали и какие результаты получены. В идеале вы должны сделать ваши достижения «измеряемыми».

Проекты

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

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

   Вообще-то говоря, я не рекомендую указывать в резюме умение работать с продуктами вроде Microsoft Office, – это должен знать каждый. Навыки работы с высокотехнологичными продуктами (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 – используйте их, когда будете практиковаться с друзьями. Хотя ваши друзья не являются профессиональными интервьюерами, они в состоянии проверить решения задач на программирование и алгоритмизацию.

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

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




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

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



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

Нужно ли знать все о программировании на C++, Java или других языках

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

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

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

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

   Любую техническую задачу на собеседовании можно решить за пять шагов:
   1. Задайте интервьюеру вопросы, чтобы снять неоднозначности.
   2. Разработайте алгоритм.
   3. Запишите псевдокод, но сообщите интервьюеру, что вы намерены написать решение на конкретном языке программирования.
   4. В умеренном темпе начните писать программный код.
   5. Проверьте написанную программу и внимательно исправьте ошибки. Остановимся на каждом шаге поподробнее.

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

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

   Задача: «Разработайте алгоритм сортировки списка»
   Вопрос: Какой список нужно сортировать? Массив? Связный список?
   Ответ: Массив.
   Вопрос: Что будет в массиве? Числа? Символы? Строки?
   Ответ: Числа.
   Вопрос: Числа будут целыми?
   Ответ: Да.
   Вопрос: Что представляют собой эти числа? Это идентификаторы? Значение чего-либо?
   Ответ: Это возраст клиентов.
   Вопрос: Сколько будет клиентов?
   Ответ: Миллион.

   Теперь постановка задачи изменилась: нужно отсортировать массив из миллиона целых чисел в диапазоне от 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, если известен правильный результат для 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-куче, так что в вершине – наибольший элемент. Такие структуры данных позволяют вам найти потенциальные медианы. Если размер куч изменился, можно повторно провести балансировку, выталкивая элементы из одной кучи в другую.
   Обратите внимание, что множество задач легко решаются, если правильно выбрать структуры для используемых данных. Теперь вам нужно понять, какой подход более применим к той или иной задаче.

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

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

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

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

   Неудачная реализация
   Плохая реализация подразумевает хранение полинома в виде массива чисел с двойной точностью, где 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 }
   5
   6 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 }
   10
   11 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 }
   17
   18 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 }
   8
   9 int maxIndex = 0;
   10 for (int i = 1; i < array.length; i++) {
   11 if (array[i] > array[maxIndex]) {
   12 maxIndex = i;
   13 }
   14 }
   15
   16 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 }
   10
   11 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 }
   20
   21 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 }
   26
   27 public static void swapMinMaxBetter(int[] array) {
   28 int minIndex = getMinIndex(array);
   29 int maxIndex = getMaxIndex(array);
   30 swap(array, minIndex, maxIndex);
   31 }
   Немодульный код не так уж и плох, но модульный код значительно легче протестировать, так как каждый его компонент можно проверить по отдельности. Чем код сложнее, тем оправданнее его модульность. Такой подход облегчит чтение и поддержку кода. Ваш интервьюер хочет увидеть, насколько вы владеете этими навыками.

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

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

Проверка

   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. Жизнь после собеседования

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

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

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

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

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

Вам отказали

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

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

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

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

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

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

   • Насколько хорошо будет выглядеть название компании в моем резюме?
   • Как я буду учиться? Чему я научусь?
   • Есть ли у меня перспективы? Как развивается карьера разработчика?
   • Если я собираюсь получить управленческую должность, подходит ли для этого данная компания?
   • Каковы перспективы роста у этой компании (или команды)?
   • Если я захочу уйти из компании – есть ли неподалеку офисы других интересных
   компаний или мне опять придется переезжать? Последний пункт очень важен, но обычно его упускают из виду. Если вы будете работать на Microsoft в Кремниевой долине и захотите уйти, то легко сможете устроиться
   в любую другую компанию. Но если вы будете работать на Microsoft в Сиэтле, то будете ограничены только Google, Amazon и немногочисленными небольшими компаниями. Если вы работаете в AOL в Далласе, ваши возможности по переходу в другую компанию еще более ограничены. У вас просто не будет выбора – если в городе нет других IT-компаний, вы будете вынуждены или остаться, или готовиться к переезду.

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

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

   • Продукт. Если вам нравится разрабатываемый продукт – это замечательно, но для инженера существенно важнее другой фактор – команда, в которой приходится работать.
   • Руководство и коллеги. Когда люди говорят, что им нравится или не нравится работа, их мнение часто формируется под влиянием коллектива и руководства. Вы встречались с этими людьми? Вы сможете с ними работать?
   • Корпоративная культура. Культура компании охватывает всё – от процедуры принятия решений до психологической атмосферы и структуры компании. Поговорите об этом с будущими коллегами.
   • Рабочий график. Ознакомьтесь с рабочим графиком и нагрузкой группы, к которой вы собираетесь примкнуть. Помните, что нагрузка в условиях цейтнота (deadline) обычно гораздо выше стандартной.
   Дополнительно выясните, возможен ли переход из одной команды в другую (как, например, в Google). Сможете ли вы найти команду, в которой вам будет комфортно?

Переговоры

   Большинство слушателей решили, что их устроила бы скидка в 0. Другими словами, они были согласны торговаться час, чтобы сэкономить всего лишь 0. Неудивительно, что большинство студентов не могли вести переговоры с работодателем. Они соглашались на то, что предлагала компания.
   Сделайте себе подарок – поторгуйтесь. Вот несколько подсказок, которые помогут вам начать переговоры.
   1. Просто начните торговаться. Да, я знаю, что это страшно. Но рекрутеры не будут отзывать предложение только потому, что вы пытаетесь добиться для себя некоторых преимуществ, поэтому вам нечего терять.
   2. Всегда имейте запасной вариант. Рекрутеры охотнее идут на уступки, если знают, что вы можете не принять предложение, а это возможно, если у вас есть выбор.
   3. Задавайте конкретные «рамки». Вы скорее достигнете цели, если попросите увеличить зарплату на 00, чем просто просите ее увеличить, – вам могут предложить 00, и это будет формальным шагом к удовлетворению ваших требований.
   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 (динамический массив)

   1 public ArrayList<String> merge(String[] words, String[] more) {
   2 ArrayList<String> sentence = new ArrayList<String>();
   3 for (String w: words) sentence.add(w);
   4 for (String w: more) sentence.add(w);
   5 return sentence;
   6 }

StringBuffer (буфер строк)

   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.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;
   4
   5 public Node(int d) {
   6 data = d;
   7 }
   8
   9 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 }
   Обратите внимание: когда вы говорите о связном списке на собеседовании, вы должны понимать, о каком списке – односвязном или двусвязном – идет речь.

Удаление узла из односвязного списка

   Если вы реализуете код на C/С++ или другом языке, требующем контроля памяти, вам нужно освободить память, которую занимал удаляемый узел.
   1 Node deleteNode(Node head, int d) {
   2 Node n = head;
   3
   4 if (n.data == d) {
   5 return head.next; /* перемещаем голову */
   6 }
   7
   8 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.2. Реализуйте алгоритм для поиска в односвязном списке k-го элемента с конца.
   2.3. Реализуйте алгоритм, удаляющий узел из середины односвязного списка (доступ дан только к этому узлу).
   Пример
   Ввод: узел c из списка a->b->c->d->e
   Вывод: ничего не возвращается, но новый список имеет вид: a->b->d->e
   2.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)
   Вывод: C
   2.7. Реализуйте функцию, проверяющую, является ли связный список палиндромом.

   Дополнительные вопросы: деревья и графы (4.4), объектно-ориентированное проектирование (7.10), масштабируемость и лимиты памяти (11.7), модерирование (17.13).

3. Стек и очередь

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

Реализация стека

   стопке тарелок – последнюю добавленную в стопку тарелку возьмут первой. Давайте рассмотрим простой код для демонстрации работы стека. Стек можно реализовать с помощью связного списка. Фактически, стек – это связный список, не позволяющий пользователю получить доступ к элементам ниже главного узла.
   1 class Stack {
   2 Node top;
   3
   4 Object pop() {
   5 if (top!= null) {
   6 Node item = top.data;
   7 top = top.next;
   8 return item;
   9 }
   10 return null;
   11 }
   12
   13 void push(Object item) {
   14 Node t = new Node(item);
   15 t.next = top;
   16 top = t;
   17 }
   18
   19 Object peek() {
   20 return top.data;
   21 } 22 }

Реализация очереди

   Очередь может также быть реализована в виде связного списка с добавлением новых пунктов в его конец.
   1 class Queue {
   2 Node first, last;
   3
   4 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 }
   13
   14 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.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 несбалансировано
Полнота дерева

Обход бинарного дерева

Балансировка: красно-черные и АВЛ-деревья

Префиксное дерево


Обход графа

   Большинство кандидатов неплохо разбираются в бинарных деревьях, но обход графа требует несколько иного подхода. Особенно сложным является поиск в ширину. Не забудьте, что поиск в ширину (BFS, Breadth First Search) и поиск в глубину (DFS, Depth First Search) предназначены для разных сценариев. DFS – это самый простой способ посетить все узлы в графе, или, по крайней мере, посетить каждый узел, пока не найдется искомый. Однако при работе с очень большими деревьями DFS не подходит. В этих случаях лучше воспользоваться BFS.
Поиск в глубину
   Обратите внимание, что прямой порядок и другие формы обхода дерева являются разновидностями 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 }
Поиск в ширину
   1 void search(Node root) {
   2 Queue queue = new Queue();
   3 root.visited = true;
   4 visit(root);
   5 queue.enqueue(root); // Добавление в конец очереди
   6
   7 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.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 и сдвиги.

Биты: трюки и факты


Основные задачи: получение, установка, очистка и обновление бита

   Приведенные далее операции очень важны, вам нужно понимать, как они работают. Зубрежка обязательно приведет к ошибкам. Вместо этого разберитесь, как можно реализовать эти методы, тогда вы сможете решить любые задачи, связанные с битами.
Извлечение бита
   1 boolean getBit(int num, int i) {
   2 return ((num & (1 << i))!= 0);
   3 }
Установка бита
   1 int setBit(int num, int i) {
   2 return num | (1 << i);
   3 }
Очистка бита
   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 }
Обновление бита
   1 int updateBit(int num, int i, int v) {
   2 int mask = ~(1 << i);
   3 return (num & mask) | (v << i);
   4 }

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

   Пример
   Ввод: N = 10000000000, M = 10011, i = 2, j = 6
   Вывод: N = 10001001100
   5.2. Дано: вещественное число в интервале между 0 и 1 (например, 0,72), которое было передано как double. Запишите его двоичное представление. Если для представления числа не хватает 32 разрядов, выведите сообщение об ошибке.
   5.3. Дано: положительное число. Выведите ближайшие наименьшее и наибольшее числа, которые имеют такое же количество единичных битов в двоичном представлении.
   5.4. Объясните, что делает код: ((n& (n-1)) ==0).
   5.5. Напишите функцию, определяющую количество битов, которые необходимо изменить, чтобы из целого числа A получить целое число B.
   Пример
   Ввод: 31, 14 Вывод: 2
   5.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.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 = 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
Является ли число простым
   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;
   4
   5 init(flags); // Устанавливаем все флаги в true (кроме 0 и 1)
   6 int prime = 2;
   7
   8 while (prime <= max) {
   9 /* Вычеркиваем оставшуюся часть произведений простых чисел */
   10 crossOff(flags, prime);
   11
   12 /* Находим следующее истинное значение */
   13 prime = getNextPrime(flags, prime);
   14
   15 if (prime >= flags.length) {
   16 break;
   17 } 18 }
   19 20 return flags;
   21 }
   22
   23 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 }
   32
   33 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 and B}.

Вероятность события {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}
   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
   Теперь сформулировать правила для независимых и взаимоисключающих событий не составит труда.
Независимость событий
Взаимоисключающие события
   Многие путают независимые и взаимоисключающие события. На самом деле два события не могут быть одновременно независимыми и взаимоисключающими (конечно, если вероятность событий больше 0). Почему? Для взаимоисключающих событий факт свершения одного события означает, что второе невозможно. Независимость означает, что реализация одного события никак не влияет на другое. Таким образом, два события с ненулевыми вероятностями не могут быть и взаимоисключающими, и независимыми.
   Если одно или оба события имеют нулевую вероятность (то есть события невозможны), то события являются и независимыми, и взаимоисключающими. Это следует из определений независимых и взаимоисключающих событий.

Обратите внимание!

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

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

   Вариант 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 (одиночка) и Factory Method (фабричный метод) могут пригодиться, и мы остановимся на них поподробнее.
   Существует множество шаблонов, но в этой книге мы не можем рассмотреть их все. Так что, если вы хотите улучшить навыки программирования, постарайтесь раздобыть книгу по этой теме.
Singleton
   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.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…», или «Реализуйте метод для вычисления всех…» – скорее всего, речь пойдет о рекурсии.
   Практика – путь к совершенству! Чем больше задач вы решите, тем легче будет распознавать рекурсивные задачи.

С чего начать

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

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

   Динамическое программирование (ДП) не очень популярно на собеседованиях, поскольку задачи по этой теме слишком сложны для 45-минутного интервью. Даже если хорошо подготовленные кандидаты смогут их решить, эти задачи – не самый удачный метод оценки кандидата.
   Если вам не повезло и вы получили задачу по ДП, подход будет аналогичен подходу к решению рекурсивной задачи. Различие заключается в том, что промежуточные результаты «кэшируются» для будущих вызовов.
Простой пример динамического программирования: числа Фибоначчи
   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 может оказаться недостаточно).
   В динамическом программировании нет ничего сложного – это все та же рекурсия, но с кэшированием результатов. Так что реализуйте обычное рекурсивное решение, а потом добавьте кэширование.

Рекурсивные и итерационные решения

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

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

   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 }
   9
   10 void merge(int[] array, int low, int middle, int high) {
   11 int[] helper = new int[array.length];
   12
   13 /* Копируем обе половины во вспомогательный массив */
   14 for (int i = low; i <= high; i++) {
   15 helper[i] = array[i];
   16 }
   17
   18 int helperLeft = low;
   19 int helperRight = middle + 1;
   20 int current = low;
   21
   22 /* Проходимся по вспомогательному массиву. Сравниваем левую и правую
   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 }
   35
   36 /* Копируем оставшуюся часть левой стороны массива
   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 }
   10
   11 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++;
   16
   17 // Находим элемент справа, который должен быть слева
   18 while (arr[right] > pivot) right-;
   19
   20 // Меняем местами элементы и перемещаем левые и правые индексы
   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 }
   18
   19 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 return binarySearchRecursive(a, x, low, mid – 1); 27 } else {
   28 return mid;
   29 } 30 }
   Множество разновидностей поиска структур данных не ограничиваются вариациями бинарного поиска, поэтому приложите максимум усилий для их изучения. Можно, например, искать узел, используя бинарные деревья или хэш-таблицы. Не ограничивайте свои возможности!

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

   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", " "," "}
   Вывод: 4
   10.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(int x), возвращающий количество значений <=x (не включая x).
   Пример:
   Поток (в порядке появления): 5, 1, 4, 4, 5, 9, 7, 13, 3
   getRankOfNumber(1)= 0
   getRankOfNumber(3)= 1
   getRankOfNumber(4)= 3

   Дополнительные вопросы: массивы и строки (1.3), рекурсия (8.3), модерирование (17.6, 17.12), вопросы повышенной сложности (18.5).

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

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

Пошаговый подход


   Шаг 1. Абстрагируйтесь от реальности
   Представьте, что все данные хранятся на одном компьютере и не существует никаких ограничений памяти. Как бы вы решили задачу? Ответ на этот вопрос позволит построить общую схему решения.

   Шаг 2. Вернитесь к реальности
   Вернитесь к исходной задаче. Сколько данных можно разместить в одном компьютере? Какие проблемы могут возникнуть, если вы разделите данные? Обычно достаточно выяснить, как разделить данные и как дать понять одному из компьютеров, где находится недостающая информация.

   Шаг 3. Решите задачу
   Подумайте о том, как избавиться от обнаруженных проблем. Помните, что решение может полностью исключить проблему или немного улучшить ситуацию. Скорее всего, вам будет достаточно слегка модифицировать исходный алгоритм (шаг 1), но иногда его требуется существенно изменить.
   Используйте итерационный подход. Как только проблемы, появившиеся на втором шаге, будут устранены, могут появиться новые, и вам придется заняться ими.
   Ваша цель – не спроектировать сложную систему, на которую компании придется потратить миллионы долларов, а продемонстрировать, что вы можете анализировать и решать задачи подобного плана.

Что нужно знать: информация, стратегия и проблема

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

notes

Примечания

1

2

3

4

5

6

7

8

комментариев нет  

Отпишись
Ваш лимит — 2000 букв

Включите отображение картинок в браузере  →