Русское издание книги Programming Interviews Exposed

    Добрый день!

    Сегодня мы представляем одну из последних новинок нашего издательства — книгу «Работа мечты для программиста. Тестовые задачи и вопросы при собеседовании в ведущих IT-компаниях». Русское название, возможно, оказалось слишком «маркетинговым», но содержание от этого не страдает — книга переиздается на Западе уже более 10 лет и заслуженно все эти годы возглавляет рейтинги IT-литературы.

    image

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


    О книге

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

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

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

    • Содержание книги вы можете посмотреть здесь.
    • Прочитать отрывок здесь
    • Купить книгу можно на сайте «Питера». К сожалению, западный издатель не отдал в Россию электронные права, поэтому книга доступна только в печатном виде.

    Тестовая задача

    В качестве затравки мы предлагаем вам попробовать выполнить одно из тестовых заданий из книги из раздела «Графические и пространственные головоломки»
    Даны два фитиля и зажигалка. Зажженный фитиль полностью сгорает за 1 час. Но при этом скорость горения неравномерна, причем фитили отличаются друг от друга. Фактически, это означает, что определить соотношение между фрагментом фитиля определенной длины и временем его горения невозможно. Два равных фрагмента фитиля могут гореть разное время. Как при помощи фитилей и зажигалки отмерить 45 минут?

    Ответ из книги будет опубликован в комментариях завтра, 25.09.13, в 18:00.

    Comments 10

      0
      Что тут думать-то: надо поджечь с двух сторон фитиль.
      А планируется ли электронная версия книги?
      • UFO just landed and posted this here
          +1
          Даже надежды не осталось
        +1
        На сколько я знаю, вопросы-головоломки уже практически никто не задает, так что эту главу, видимо, пора бы выкинуть ;)
          0
          Сложить первый фитиль пополам(30 минут?) и второй вчетверо(15 минут?). Приложить конец первого и начало второго. Поджечь с какой-нить стороны. Смущает только непостоянная скорость горения и то, что они «причем фитили отличаются друг от друга», хотя сказано, что фитиль сгорает за 1 час.
            0
            Не сработает. Скорость горения неравномерна. Сложив пополам, половинки будут гореть не по полчаса и фиг знает как.
            Правильный ответ дал Jeket ниже habrahabr.ru/company/piter/blog/195232/#comment_6774116
            +7
            Решение простое — поджигаешь первый фитиль, одновременно с ним с обоих концов поджигаешь второй. Второй сгорит ровно за 30 минут, вэтот момент поджигаешь со второго конца первый фитиль. Тогда, первый догорит ровно за 45 минут.
              0
              Этих книг про собеседования, алгоритмические и логические задачки хоть попой жуй — к примеру: «Карьера программиста», «Достаточно ли вы умны, чтобы работать в Google», «Как передвинуть гору Фудзияма» и т.п.
                0
                Поскольку правильный ответ уже дан, опубликуем цитату из книги с ответом раньше объявленного времени.
                Сложнее всего в данном случае сфокусироваться на том, что длина фрагмента фитиля никак не связана со временем его горения. Хотя это явно указано в условии задачи, мы настолько привыкли к постоянным скоростям и соотношениям между временем и расстоянием, что идея измерения длины фитилей кажется крайне соблазнительной. Но скорость горения нам неизвестна, кроме того, она является непостоянной величиной, поэтому в качестве единицы измерения нам остается только время. Из этого мы и будем исходить при решении.

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

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

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

                Итак, один фитиль позволяет нам отмерить ровно 30 минут. Остается понять, каким образом отмерить при помощи второго фитиля 15-минутный интервал, и задача будет решена. Что нам нужно, чтобы отмерить 15 минут? Нужно либо с одного конца поджечь фитиль, который горит 15 минут, либо с двух концов поджечь фитиль, который горит 30 минут. Так как изначально фитиль горит 60 минут, нужно убрать фрагмент, горение которого занимает 45 или 30 минут. Очевидно, что это нужно сделать при помощи огня, так как для отрезания нужного фрагмента фитиля мы должны правильно отмерить его, а это невозможно. Для удаления 45-минутного фрагмента нужно поджечь фитиль с обоих концов на 22,5 минуты или с одного конца на 45 минут. Отмерить 22,5 минуты еще сложнее, чем решить нашу задачу, значит, этот вариант исключается.

                Альтернативой является удаление 30-минутного фрагмента фитиля. Для этого его нужно поджечь с двух концов на 15 минут или с одного конца на 30 минут. Как отмерить 30 минут, мы уже знаем: ровно это время занимает горение первого фитиля, подожженного с обоих концов. Вам нужно одновременно поджечь один конец одного фитиля и два другого. Как только второй фитиль прогорит, сразу же поджигайте первый с другого конца. Два огонька, горящие на 30-минутном фрагменте фитиля, погаснут ровно через 15 минут, что даст вам искомые 30 + 15 = 45 минут.
                  0
                  Интересно было бы сравнить ее с этой
                  habrahabr.ru/company/piter/blog/151010/

                  Only users with full accounts can post comments. Log in, please.