Для одного из наших первых постов-рецензий мы выбрали замечательную книгу, которую рекомендуем не пропустить пропускать ни одному программисту, желающему совершенствоваться и развиваться как профессионалу. Это пятое издание одного из западных бестселлеров среди книг по программированию — Cracking the Coding Interview: 150 Programming Interview Questions and Answers, получившая в русском издании название «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».
Для книги IT-тематики эта книга имеет совершенно невероятный рейтинг на сайте Amazon’а (на 6 сентября это #388 в общем рейтинге книг и №1 – для раздела «Computers & Technology»), поэтому я как куратор данного проекта был просто счастлив, когда «Питер» получил эксклюзивные права на издание этого бестселлера в России.
Немного об авторе книге. Гейл Лакман – это милая американская IT-girl, которая, правда, за время подготовки русского издания успела выйти замуж и обзавестись второй фамилией Макдауэлл. Гейл на протяжении нескольких лет интервьюировала соискателей в Google, Microsoft и Apple, а потом основала собственную компанию CareerCup, которая помогает программистам подготовиться к прохождению собеседования в крупнейших IT-компаниях. Ну и, конечно, Гейл знаменита и в качестве автора книги Cracking Coding Interview, которая переиздается на Западе уже много лет и не сходит из верхних строк чартов книжных бестселлеров. О предприимчивости Гейл Лакман говорит еще и тот факт, что она лично выступает издателем собственных книг и даже переговоры о лицензировании книги в России мы вели с ней напрямую (в общем-то, нонсенс, для современного издательского бизнеса).
О чем же эта книга?
Из названия может сложиться впечатление, что она посвящена описанию процесса собеседования и приема на работу в крупных корпорациях: как одеться, как себя вести, какова практика проведения интервью в Google или Microsoft и как отказывают неугодным соискателям в каждой компании. На самом деле, НЕТ.
Кстати, интересная история: наших коллег из интернет-магазина Ozon также смутило название книги, и они поставили ее в раздел «Кадровый учет и делопроизводство», и нам стоило некоторых усилий вернуть издание в правильную ветку классификатора.
Так вот, Cracking Coding Interview необходимо ставить в один ряд с классическими книгами по алгоритмам, которые заставляют программистов думать и самосовершенствоваться. Указанным выше темам действительно отведено немного места (а именно – 50 страниц), но основная и самая ценная часть книги — это почти 400 страниц реальных вопросов и тестовых заданий, которые получают соискатели на собеседованиях в самых известных IT-компаниях мира. Безусловно, эта книга поможет вам, если вы действительно собираетесь на собеседование в Google, но и сама по себе она даст любому программисту возможность по-новому взглянуть на свои навыки и свое развитие как профессионала, предлагая не только абстрактные, но и вполне реальные задания и решения, которые могут быть использованы на практике.
Всего в книге – 150 задач (и правильных ответов на них!) по таким темам как ООП, тестирование, рекурсия, деревья и графы, базы данных, потоки и теория вероятности и т.д. Подобное содержание книги вы можете посмотреть по данной ссылке (PDF-файл на сайте издательства).
А в качестве затравки мы предлагаем вам попробовать выполнить одно из тестовых заданий из книги из раздела «Задачи повышенной сложности»
Задание
Напишите метод, генерирующий случайную последовательность m целых чисел из массива размером n. Все элементы выбираются с одинаковой вероятностью.
Ответ из книги будет опубликован в комментариях завтра, 7 сентября, в 18:00. Просьба обладателям книги не давать подсказки.
А ниже, в качестве примера, приводим другое задание, из раздела «Рекурсия и динамическое программирование» с правильным ответом.
Задание.
Реализуйте функцию заливки краской, которая используется во многих графических редакторах. Дана плоскость (двумерный массив цветов), точка и цвет, которым нужно заполнить все окружающее пространство, окрашенное в другой цвет.Решение
Прежде всего, давайте визуализируем работу метода. Когда мы вызываем paintFill («нажимаем» кнопку заливки в графическом редакторе), находясь, например, на зеленом пикселе, то хотим расширить границы. Мы продвигаемся все дальше и дальше, вызывая paintFill для окружающих пикселей. Если цвет пикселя отличается от зеленого, мы останавливаемся.Можно реализовать этот алгоритм рекурсивно:
1 enum Color {
2 Black, White, Red, Yellow, Green
3 }
4
5 boolean paintFill(Color[][] screen, int x, int y, Color ocolor,
6 Color ncolor) {
7 if (x < 0 || x >= screen[0].length ||
8 y < 0 || y >= screen.length) {
9 return false;
10 }
11 if (screen[y][x] == ocolor) {
12 screen[y][x] = ncolor;
13 paintFill(screen, x — 1, y, ocolor, ncolor); // left
14 paintFill(screen, x + 1, y, ocolor, ncolor); // right
15 paintFill(screen, x, y — 1, ocolor, ncolor); // top
16 paintFill(screen, x, y + 1, ocolor, ncolor); // bottom
17 }
18 return true;
19 }
20
21 boolean paintFill(Color[][] screen, int x, int y, Color ncolor){
22 return paintFill(screen, x, y, screen[y][x], ncolor);
23 }Обратите внимание на порядок следования x и y в массиве screen[y][x] и запомните, что, когда вы решаете задачу, связанную с компьютерной графикой нужно использовать именно такой порядок. Поскольку x соответствует горизонтальному направлению, то эта переменная описывает номер столбца, а не номер строки. Значение y соответствует номеру строки. В этом месте очень легко допустить ошибку, как на собеседовании, так и при ежедневном программировании.
С уважением, Андрей Юрченко, издательский дом «Питер»
- Книга на сайте издательства
- Книга на Ozon
Автор: ph_piter
