Карьера программиста, или Cracking Coding Interview

    Для одного из наших первых постов-рецензий мы выбрали замечательную книгу, которую рекомендуем каждому программисту, желающему совершенствоваться и развиваться как профессионалу. Это пятое издание одного из западных бестселлеров среди книг по программированию — Cracking the Coding Interview: 150 Programming Interview Questions and Answers, получившая в русском издании название «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».

    image

    Для книги 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 соответствует номеру строки. В этом месте очень легко допустить ошибку, как на собеседовании, так и при ежедневном программировании.


    Издательский дом «Питер»
    Компания

    Комментарии 32

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

      PHP-шный array_rand() считается за читерство? :-)
        0
        А даже если и не считается, то не является верным ответом, так как при m>n свалится с ошибкой, а условия задачи таких ограничений не налагают.

        Верный ответ, мне кажется, рандом + убирать выбранное число из массива, дабы оно больше не могло быть выбрано (а иначе оно может попасться в следующем рандоме, сломав всю равномерность распределения в полученном результате). Если m>n — возвращать все числа в массив — и начинать заново.
          0
          Неправильно. Для m <= n на выходе вы не сможете получить двух одинаковых чисел. Какая же это выборка с одинаковой вероятностью?
            0
            Правильно. :) Смотрите коммент автора внизу.
              0
              Вот поэтому программы пишут программисты, а не HR.
            +2
            С убиранием вы, по-моему, намудрили. В условии — элементы выбираются с равной вероятностью. Про «распределение результата» речи не идёт. Ну, и вообще, отдельные повторения, вообще говоря, не ломают «равномерности распределения в полученном результате» :). Критерии там совершенно другие.
              0
              А я, между прочим, верно ответил (см. последний коммент). Ну разве что там оптимизировали скорость (заменили убирание на перестановку в начало). А идея та же.
                0
                Тогда автор в каком-то месте перемудрил сам себя. или переводчик. Приведённое решение решает другую задачу.
                  0
                  Там из текста задачи сразу было видно, что или перевод кривой, или задача составлена с каким-то диким подвохом… Причём ни раз не факт, что подвох сделан специально, возможно — просто по незнанию/непониманию каких-то теорий.
                    +1
                    Книгу не читал, но на интервью обязательно попросил бы уточнить условие задачи. Где-то читал, что как раз во всяких гуглах любят давать такие вот незамкнутые в условиях задачи, чтобы посмотреть будет претендент конкретно тупить или попытается получить недостающее. Если это предположение верно, то далее в книге должно быть уточнение. Тогда перемудрил (недомудрил) автор топика. Тем более, как уже замечено, предложенное решение ломается при m > n.

                    Ой, нашёл эту книжку, эту задачу ещё не нашёл, нашёл другую.
                    Формулировка — Какова вероятность пересечения двух прямых, лежащих в одной плоскости?
                    Дальше идёт зачотный трэшак, цитата:
                    «Задача содержит много неопределённостей: В каком формате заданы прямые? Могут ли прямые совпадать? Все эти вопросы надо обсудить с интервьюером»… Дальше полная чушь про структуры данных в которых надо хранить информацию о прямой и как определять факт прересечения и даже какой-то код, который это делает. Прекрасно, конечно, но больше ни слова о вероятности и о решении исходной задачи. То есть опять решается какая-то совершенно другая задача.

                    Вопросы об адекватности перевода, либо об адекватности самого автора встают в полный рост :).
        • НЛО прилетело и опубликовало эту надпись здесь
            +2
            Отлично сказано. Ничто не стимулирует учить английский так, как подобные комменты :)
              0
              Безусловно, но, как и было сказано выше, книга не только и не столько о том, как устроиться на работу. Думаю, что сам факт издания ее на русском позволит большему числу отечественных программистов в принципе узнать о том, что есть такая интересная книга.
                0
                Будьте добры, вставьте цитату из оригинального текста задачи?
                Мне просто интересно, проблема в задаче или проблема в переводе?
                Если проблема в задаче — то без интервьюера задача не имеет смысла (т.к. необходимо что-то уточнять и о чём-то говорить), если в переводе — то перевод явно не позволит книге стать столь интересной, как вам бы хотелось.
                  0
                  Вот оригинальный текст задачи
                  Write a method to randomly generate a set of m integers from an array of size n.
                  Each element must have equal probability of being chosen.
                    0
                    Вот оригинальный текст задачи
                    Write a method to randomly generate a set of m integers from an array of size n.
                    Each element must have equal probability of being chosen.
                      0
                      Что ж, если все задачи в книге такие… Тогда её брать не имеет смысла, т.к. условия поставлены слишком расплывчато. Если точнее — решение не соответствует задаче.
                        0
                        Set как раз и означает, что элементы не должны повторяться, так что это плохой перевод.
                  0
                  Какое вы издание переводили?
                    0
                    Все, нашел на Озоне — 5е.
                    +5
                    отличный пример, если ocolor == ncolor то мы знакомимся с бесконечной рекурсией
                    если там все примеры такие, то я бы рекомендовал не читать книжку, а искать в ней баги
                      +2
                      Автор просто-напросто избавляется от конкурентов с помощью этой книги.
                        0
                        А забавно. Реально же нет выхода. Хотя, я думаю, это опечатка. Но хочется услышать ответ ph_piter
                        0
                        Код, приведенный в данном посте, полностью идентичен тому, что опубликован в оригинальной книге. Нет исправлений по нему и в списке опечаток на авторском сайте. Возможно, стоит вступить в дискуссию с автором книги на том же сайте или сообщить о баге там же.
                          0
                          Оригинальный способ поиска внимательных программистов — написать книгу где напечатан код с багами и брать на работу всех, кто присылает багрепорты
                          0
                          Больно легкая задача для «повышенной сложности». На Perl 6 к примеру это всего лишь (@arr[@arr.rand] for 1..$m) + обернуть в метод и соответственно класс. В чем подвох?
                            +1
                            Какие-то задачки детские. Надеюсь, в книге есть что-то поинтереснее.
                              0
                              А вот и ответ на опубликованное вчера задание, предлагаемый автором книги:

                              Задание
                              Напишите метод, генерирующий случайную последовательность m целых чисел из массива размером n. Все элементы выбираются с одинаковой вероятностью.
                              Решение
                              Первое, что приходит в голову — выбрать случайные элементы из массива и поместить в новый массив. Но, что если мы выберем один и тот же элемент дважды? В идеале, нам нужно «сократить» массив так, чтобы выкинуть выбранный элемент. Но уменьшение массива достаточно трудоемкая операция, поскольку требует смещения элементов.

                              Вместо того чтобы сокращать (сдвигать) массив, можно поставить элемент (поменять элементы местами) в начало массива, и «запомнить», что теперь массив начинается с элемента j. Если элемент subset[0] становится элементом array[k], то мы должны заменить элемент array[k] первым элементом в массиве. Когда мы переходим к элементу subset[1], то подразумеваем, что элемент array[0] «мертв», и выбираем случайный элемент y из интервала от 1 до array.size(). Теперь subset[1] = array[y] и array[y] = array[1]. Элементы 0 и 1 «мертвы», а subset[2] выбирается в диапазоне от array[2] до array[array.size()] и т. д.

                              1 /* Случайное число между lower и higher, включительно */
                              2 public static int rand(int lower, int higher) {
                              3 return lower + (int)(Math.random() * (higher — lower + 1));
                              4 }
                              5
                              6 /* Выбрать M элементов из исходного массива. Клонируем исходный
                              7 * массив так, чтобы не уничтожить ввод */
                              8 public static int[] pickMRandomly(int[] original, int m) {
                              9 int[] subset = new int[m];
                              10 int[] array = original.clone();
                              11 for (int j = 0; j < m; j++) {
                              12 int index = rand(j, array.length — 1);
                              13 subset[j] = array[index];
                              14 array[index] = array[j]; // array[j] теперь «мертв»
                              15 }
                              16 return subset;
                              17 }
                                0
                                Как уже писал пользователь dime с таким условием, какое привели — задача тривиальная и правильное решение — брать случайно элементы из всего массива и записывать их в новый массив. То, что описано в «официальном» решении — похоже на задачу random shuffle и сломается при m > n.

                                Итого с бесконечной рекурсией: 2 / 2 ошибок в легких задачах.
                                  –1
                                  Если задача в том, чтобы сгенерировать массив случайных неповторяющихся целых чисел… Когда-то давным давно, в журнале «Наука и Жизнь», я видел такой такой вариант решения:

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

                                  Но формулировка задачи неоднозначна и ужасна. То ли трудности перевода, то ли девушка-программист задачу составляла.
                                  +1
                                  Электронная версия? Не, не слышал.
                                    0
                                    Листал данный труд (на англ.) перед собеседованием в одну из этих компаний.
                                    Меня больше заинтересовали главы про сопутсвующее (одежда, обед, торги и т.д.).
                                    Спиосок задачек есть в интернете, а если ты их не можешь решить без книжки, то и смысла идти на собеседование нету т.к. все равно дадут совсем другие задачки.

                                    Хотя… знаю товарища, который устраивался в геймдев контору с мировым имененм и рассказывал про сложную задачку на собеседовании, которую он не решил. Дык вот она была в этой книжке. )))

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

                                    Самое читаемое