27.01.2018 08:02
reci 47 4200 Источник
Продолжаем публиковать интересные задачи от ведуших IT-компаний.

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

Вопросы


  1. Total distance travelled by bee
    Two trains are on same track and they are coming toward each other. The speed of first train is 50 KMs/h and the speed of second train is 70 KMs/h. A bee starts flying between the trains when the distance between two trains is 100 KMs. The bee first flies from first train to second train. Once it reaches the second train, it immediately flies back to the second train … and so on until trains collide. Calculate the total distance traveled by the bee. Speed of bee is 40 KMs/h.

    Перевод
    Два поезда на одном пути едут навстречу друг другу. Скорость первого поезда — 50 км/ч, скорость второго — 70 км/ч. Пчела начинает летать между поездами, когда расстояние между ними равно 100 км. Пчела летит от первого поезда ко второму. Когда достигнет второго, немедленно летит обратно к первому… и продолжает так летать, пока поезда не столкнутся.
    Посчитайте дистанцию, пройденную пчелой, если её скорость 40 км/ч.

  2. Poisoned wine
    The King of a small country invites 240 senators to his annual party. As a tradition, each senator brings the King a bottle of wine. Soon after, the Queen discovers that one of the senators is trying to assassinate the King by giving him a bottle of poisoned wine. Unfortunately, they do not know which senator, nor which bottle of wine is poisoned, and the poison is completely indiscernible. However, the King has 5 prisoners he plans to execute. He decides to use them as taste testers to determine which bottle of wine contains the poison. After drinking the poisoned wine, one dies within 24 hours. The King needs to determine which bottle of wine is poisoned in 2 days so that the festivities can continue as planned. How can the King administer the wine to the prisoners to ensure that 48 hours from now he is guaranteed to have found the poisoned wine bottle?

    Перевод
    Король небольшой страны пригласил 240 сенаторов на ежегодное празднование. По традиции, каждый сенатор преподносит королю бутылку вина. Однако, вскоре королева узнала, что один из сенаторов пытается отравить короля, подарив ему отравленную бутылку вина. К несчастью, они не знают, ни кто этот сенатор, ни что за бутыль отравлена, к тому же, яд невозможно обнаружить. В королевской тюрьме есть 5 заключенных, приговоренных к скорой смерти. Король решает с их помощью вычислить отравленную бутылку вина. Яд подействует только через 24 часа — выпивший его умирает. Королю необходимо выявить, какая бутылка отравлена, за 2 дня, чтобы продолжить запланированные мероприятия. Как он может распределить вино между заключенными, чтобы гарантированно найти отравленную бутылку за 48 часов?

Задачи


  1. Largest subarray with equal number of 0s and 1s
    Given an array containing only 0s and 1s, find the largest subarray which contain equal number of 0s and 1s.

    Examples:
    Input: arr[] = {1, 0, 1, 1, 1, 0, 0}
    Output: 1 to 6 (Starting and Ending indexes of output subarray)

    Input: arr[] = {1, 1, 1, 1}
    Output: No such subarray

    Input: arr[] = {0, 0, 1, 1, 0}
    Output: 0 to 3 Or 1 to 4

    Перевод
    Дан массив, содержащий нули и единицы. Необходимо найти наибольший подмассив, содержащий одинаковое количество 0 и 1.

    Примеры:
    Вход: arr[] = {1, 0, 1, 1, 1, 0, 0}
    Выход: 1 to 6 (Индексы входного массива)

    Вход: arr[] = {1, 1, 1, 1}
    Выход: No such subarray

    Вход: arr[] = {0, 0, 1, 1, 0}
    Выход: 0 to 3 Or 1 to 4

  2. Count total set bits
    Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.

    Examples:

    Input: n = 3
    Output: 4

    Input: n = 6
    Output: 9

    Input: n = 7
    Output: 12

    Input: n = 8
    Output: 13

    Перевод
    Дано положительное целое число n, необходимо вычислить сумму битов всех чисел от 1 до n в двоичном представлении.

    Примеры:
    Вход: n=3
    Выход: 4

    Вход: n=6
    Выход: 9

    Вход: n=7
    Выход: 12

    Вход: n=8
    Выход: 13

  3. Find the repeating and the missing
    Given an unsorted n-sized array of integers. Array elements are in range from 1 to n. One number from set {1, 2, …n} is missing and one number occurs twice in array. Find these two numbers.

    Examples:

    arr[] = {3, 1, 3}
    Output: 2, 3 // 2 is missing and 3 occurs twice

    arr[] = {4, 3, 6, 2, 1, 1}
    Output: 1, 5 // 5 is missing and 1 occurs twice


    Перевод
    Дан неотсортированный массив целых чисел размерностью n. Элементы массива — последовательность чисел от 1 до n. Одно число в последовательности пропущено и одно — повторяется. Необходимо найти эти числа.

    Примеры:

    arr[] = {3, 1, 3}
    Output: 2, 3 // 2 пропущено, 3 повторяется

    arr[] = {4, 3, 6, 2, 1, 1}
    Output: 1, 5 // 5 пропущено, 1 повторяется



Ответы будут даны в течение следующей недели — успейте решить. Удачи!

Комментарии (47)


  1. kardan2
    27.01.2018 14:20
    #10638322
    +1

    Решения пока только вопросов.

    1 Вопрос.
    Как может пчела со скоростью 40 км\ч летать между поездами, когда у обоих скорость больше?
    Это тест на адекватность?
    Если убрать из рассмотрения этот момент, то скорость одного поезда относительно другого — 50+70 = 120 км\ч. 100 км они пройдут за 100\120 = 5\6 часа. За это время пчела пролетит (сама траектория не важна, она сама по себе летает) 5\6часа*40км\ч=100\3км. Т.е. чуть больше 33 км.


    1. reci Автор
      27.01.2018 14:21
      #10638326

      > Жутко не нравится моральная сторона вопроса.
      Согласен, однако, если отрешиться от морали — задача интересная. Завернул в другую обёртку.


      1. kardan2
        27.01.2018 14:45
        #10638350

        Отличный ход про короля и сенаторов.

        1 задача
        Легко решить за 2 прохода, если использовать дополнительный массив длинной 2*n.
        Проходим по массиву. Изначально счетчик с=0. Если встречаем 1, то прибавляем 1, если встречаем 0, то вычитаем 1. Далее по адресу c+n заносим значение текущей позиции.
        Второй проход, делаем тоже самое, но вместо записи во второй массив считываем значение из ячейки c+n и вычитаем текущую позицию. И находим максимум вычисленного значения.
        Можно сократить размер массива до n+1 если номер ячейки вычислять как с%(n+1)


        1. yizraor
          27.01.2018 17:17
          #10638514

          Задачу 2 можно решить и в один цикл :)


          Способ решения за 1 цикл

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


          Если выписать в двоичном виде числа 0,1,2,3,4,5..., то можно увидеть, что:
          0-й бит встречается в каждом втором числе, паттерн: 0,1,0,1,0,1,0,1,…
          1-й бит встречается дважды в каждой четвёрке чисел, паттерн: 0,0,1,1,0,0,1,1,…
          2-й бит встречается четырежды в каждой восьмёрке чисел, паттерн: 0,0,0,0,1,1,1,1,…
          …
          n-й бит встречается (2^n) раз в каждой полной группе из (2^(n+1)) чисел.


          Дополнительно нужно обработать "остатки" от деления числа n на степени 2-ки.
          Допустим, число 14 дало остаток 6 при делении на 8. При этом, в числах от 9 до 14 второй бит встретится в значении 1 трижды (числа 12,13,14), и эти 3 единичных бита тоже добавляем к результату.


          Код на языке C#
          using System;

class Solution
{
    static void Solve(int n)
    {
        int result = 0;

        for (int k = 1; k <= n; k = k << 1)
        {
            result += k * (n / (k << 1));
            result += Math.Max(((n % (k << 1)) + 1) - k, 0);
        }

        Console.WriteLine($"n = {n}, result = {result}");
    }

    static void Main(string[] args)
    {
        foreach (int n in (new int[] { 3, 6, 7, 8 }))
            Solve(n);
    }
}


          1. kardan2
            27.01.2018 17:55
            #10638576

            Сам понял, что можно за 1 цикл, когда писал решение.


          1. kardan2
            27.01.2018 18:02
            #10638586

            Причем ваш код работает, а в моем ошибка.


        1. kardan2
          27.01.2018 17:53
          #10638574

          Решение в виде кода

          Задача 1
          public static int[] largestSubarray(int[] array){
        final int n = array.length+1;
        int[] secondArray = new int[n];
        int c = 0;
        // Первый проход - заполняем массив
        for(int i=0; i<array.length; i++){
            if(array[i]==1){
                c++;
            }else{
                c--;
            }
            secondArray[c%n]=i;
        }
        // Второй проход - ищем максимальную длинну подмассива
        c = 0;
        int index = -1;
        int maxValue = secondArray[0]+1;
        for(int i=0; i<array.length; i++){
            if(array[i]==1){
                c++;
            }else{
                c--;
            }
            if(secondArray[c%n]-i>maxValue){
                maxValue = secondArray[c%n]-i;
                index = i;
            }
        }
        // Если найден подмассив
        if(maxValue>1){
            int result[] = new int[2];
            result[0] = index+1;
            result[1] = index+maxValue;
            return result;
        }
        return null;
    }


          1. kardan2
            27.01.2018 18:13
            #10638598

            В задаче 2 ошибка

            Правильное решение
                public static int totalBits(int value){
        int count =0;
        int mask = 1;// 0001, 0010, 0100, 1000 ...
        int mask2 =0;// 0000, 0001, 0011, 0111 ...
        while(value>=mask){
            if((value&mask)>0){
                count+=(value&mask2)+1;
            }
            count+=(value -(value&(mask+mask2)) )/2;
            mask2+=mask;
            mask = mask + mask;
        }
        return count;
    }


          1. qw1
            27.01.2018 23:54
            #10638976

            Решение задачи верное, но не содержит объяснения.

            Обозначим Si суммарное кол-во единичек минус суммарное кол-во ноликов от начала последовательности до позиции i (не включая саму i).

            Тогда нужный нам подмассив, начинающийся с позиции i и заканчивающийся на j, обладает свойством Si = Sj+1. Нам нужно найти сами индексы i и j. Можно использовать «жадный» алгоритм, что если Si = Sj+1 для разных i, j, мы берём минимальный i и максимальный j.

            В массив R (secondArray) положим индекс j, такой, что R[Sj] = j.
            Причём, если для разных j1 < j2 одинаковое Sj1 = Sj2, то в массив R положим последний j2 (т.е. больший). Это обеспечивается тем, что первый цикл, который последовательно вычисляет Si, замещает в массиве R ранее записанное значение i на следующее, большее.

            Второй проход снова последовательно считает Si, и сразу для рассчитанного Si из массива R получает индекс j — максимальный индекс, такой, что Si=Sj.

            Извращение с Si mod n нужно, чтобы привести значения Si, которые используются для индекса к X, из диапазона [-n;n] к [0;2*n] (кстати, не очень понял, почему для secondArray достаточно длины n).


            1. kardan2
              28.01.2018 08:06
              #10639096
              +1

              (кстати, не очень понял, почему для secondArray достаточно длины n

              Достаточно длины (n+1), если n — длина исходного массива. Если у нас например все 1, то счетчик дойдет до n, и так как n%(n+1)=n, то последний элемент все равно не совпадет с первым элементом, у которого индекс 0. Также верно и в обратную сторону.


    1. Andy_U
      27.01.2018 14:36
      #10638346

      Вы, вроде бы, не уложились в 48 часов?


      1. kardan2
        27.01.2018 14:46
        #10638352

        Почему? 48 часов — это 2 попытки. И в самом низу решения я указал, как за эти 2 попытки найти бочку. Может я скомкано объяснил. Всё, что выше последнего абзаца — это рассуждения в слух. Последний абзац — это решение.


        1. Andy_U
          27.01.2018 14:55
          #10638364

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


    1. coremirus369
      28.01.2018 13:38
      #10639254

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


      1. alexeykuzmin0
        28.01.2018 20:11
        #10639506

        After drinking the poisoned wine, one dies within 24 hours
        Не «через 24 часа», а «в течение следующих 24 часов».


    1. andyudol
      28.01.2018 15:53
      #10639324
      +1

      Как может пчела со скоростью 40 км\ч летать между поездами, когда у обоих скорость больше?


      Хорошее замечание. Надо было написать «пытается летать» — по тому правилу, которое сформулировано дальше. При этом результат не изменится.


    1. apapacy
      28.01.2018 21:08
      #10639590

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


  1. Mox
    27.01.2018 15:42
    #10638422
    -1

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

    Было бы имхо больше пользы, если бы IT сообщество просто поделилось бы опытом о своих собеседованиях на ресурсах типа Jobingood.


    1. reci Автор
      27.01.2018 15:54
      #10638432

      Я ни разу не собеседовался в компании мирового уровня, однако такие посты и книги вроде «Cracking the coding interview» наводят на мысль, что задачи все-таки спрашивают. Да и похожего плана задачки встречались в менее крупных компаниях.

      Ну и мне лично интересно порешать их после рабочей недели :)


      1. Mox
        27.01.2018 15:59
        #10638438

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

        А интерес порешать — да, интересно. :)


  1. sbnur
    27.01.2018 16:18
    #10638450

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


    1. reci Автор
      27.01.2018 16:35
      #10638468

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


      1. sbnur
        27.01.2018 17:24
        #10638526

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


        1. kardan2
          27.01.2018 18:27
          #10638616

          Вы можете оценивать, как хотите — ваше право.
          Возможно, другая сторона думает совсем иначе.
          Да, есть вакансии, где нужен конкретный спец под конкретное дело с учетом того, что выбранный инструмент — это надолго.
          Но посмотрите с другой стороны, сейчас всё очень быстро меняется, через полгода ваш любимый фреймворк или любимая база данных (в которой вы спец и можете ответить на любой технический вопрос) устареет и будет заменена на другую. И компания получит бесполезного работника в виде вас.
          А вот если человек не знает технических тонкостей, но соображает (хорошо решает подобные задачи), то он быстро разберется в технологии и по ходу разберется что и как.
          Конечно, важно и умение соображать и знание конкретной технологии, но я бы оценивал их как 2 к 1.

          тем более я мог задать подобную задачу задающему ее сотруднику

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

          Вот меня часто просят рассказать «ход рассуждений». Так, что вот вам пример (в виде меня), опровергающий ваше мнение.


          1. sbnur
            27.01.2018 19:33
            #10638712

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


            1. kardan2
              28.01.2018 08:16
              #10639100
              +1

              Задача про муху для меня самого не понятна. Если бы там были корректные условия (муха в 2 раза быстрей), то такие задачи могут даваться, чтобы расслабить кандидата. Очень часто кандидаты волнуются (и этим мешают понять что они такое). А так человек получил простую задачу, решил, увидел, что ничего сверхестественного от него не требуется (как например разводить море подобно Моисею).
              Ещё есть класс задач, которые легко решают дети, но не могут решить взрослые люди. Т.е. будет лучше, если кандидат не сможет решить такую задачу. www.lprobs.ru/prob37solve.html
              Ещё был случай, когда на собеседовании после 9 чисто технических вопросов по языку дали простую задачу по геометрии. Зачем это сделали — не знаю. Видимо я много ещё чего не понимаю в собеседованиях.


              1. sbnur
                28.01.2018 10:47
                #10639146

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


                1. apapacy
                  28.01.2018 18:42
                  #10639420
                  +1

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


                  1. sbnur
                    28.01.2018 20:09
                    #10639504

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


                    1. apapacy
                      28.01.2018 20:53
                      #10639562

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


  1. GrigorGri
    27.01.2018 22:19
    #10638888

    Вопрос 2

    Делим бутылки поровну между заключенными: 48 на каждого. Каждый пьет из новой бутылки раз в 30 минут, закончит через 23 часа 30 минут. Ждем пока умрет заключенный, замеряем сколько минут прошло с момента начала эксперимента. Отравленная бутылка будет иметь номер (время-23.5*60) div 30.
    Уменьшая задержку между бутылками можно увеличить количество бутылок для проверки.


    1. Andy_U
      27.01.2018 22:30
      #10638908

      Нет, известно лишь, что смерть наступит в течение 24 часов, а не ровно через 24 часа.


      1. GrigorGri
        27.01.2018 22:44
        #10638918

        The poison when taken has no effect on the prisoner until exactly 24 hours later when the infected prisoner suddenly dies.
        Как минимум 24 часа. Если больше, а не ровно, то решений уже нет: два раза по больше чем 24 превысит 48


        1. Andy_U
          27.01.2018 22:50
          #10638922

          Опс. В оригинальной формулировке, на которую дал правильный ответ kardan2, было именно так, как я только что написал. А так, как сейчас, конечно, проще.

          Автор?


          1. reci Автор
            27.01.2018 23:22
            #10638952

            Верно, изначально было «в течение», вернул исходный вариант. Решение GrigorGri правильно для варианта «точно через 24 часа».


            1. qw1
              27.01.2018 23:35
              #10638968

              В английском тексте тоже плохая формулировка.
              Русские варианты не читал вообще, но для английского «exact» получается довольно тривиальное решение: один смертник пьёт все 240 бутылок с перевывом в 5 минут. Если смерть наступает ровно через 24 часа, часы нам покажут, какая бутылка сработала.

              Есть формулировка получше: волшебный яд действует ровно в 12:00 (в полдень), поэтому до дедлайна есть только 2 попытки проверить бутылки на каждом смертнике.


  1. reci Автор
    27.01.2018 23:21
    #10638950

    .


  1. VolCh
    28.01.2018 01:19
    #10639006

    В первой задаче имеется ввиду скорость относительно дороги или поезда от которого летит? Если первое, как это по дефолту, то пролетит до столкновения 100/(50+70)*40, отстав от первого поезда и до второго недолетев ни разу.


  1. n_yd
    29.01.2018 10:39
    #10640040

    Задача про биты:
    Помогите довести

    Подсчитаем для каждого 2^n числа сумму всех бит чисел до него включительно:
    Для 0: 0;
    Для 1: 0, 1, s=1
    Для 2^n = s[2^(n-1)] * 2 + 2^n; // так как на порядок ниже все числа повторяются, с 1

    Далее имеем: {0..10100} = {0..10000} + 10{0..100}

    Если это добить, получится решение, которое работает ~за кол-во бит операций


  1. ptyrss
    29.01.2018 10:39
    #10640042
    +1

    Вроде бы никто не писал такое решение задачи 2. Занумеруем бутылки в системе счисления по основанию 3. Дальше думаю все понятно. 3^5=243 как раз.


    Как по мне решение простое и эффективное.


    1. apapacy
      29.01.2018 12:08
      #10640244

      да это решение и предполагалось. Суть задачи это преодолеть стереотип что существует три системы счисления 2 10 и 16


    1. qw1
      29.01.2018 17:27
      #10641138

      Раскройте свою идею полнее.

      У эксперимента 2 исхода: умер или нет.
      Смертнику можно дать N-ю бутылку или нет.
      На этом основано решение с двоичной нумераций.
      Как переложить на троичную нумерацию?


      1. ptyrss
        29.01.2018 21:20
        #10641724
        +1

        3 состояния. не умер, умер в 1 день, умер во 2 день. Дальше не пишу — и так подсказка большая)


        1. qw1
          30.01.2018 11:12
          #10642662

          Под спойлер? :)


    1. Andy_U
      29.01.2018 17:41
      #10641200

      А можно чуть подробнее про алгоритм «дегустации»? Чем он проще, чем деление на 2^5 групп разного размера, чтобы выживших на первом шаге хватило на второй?


  1. apapacy
    29.01.2018 17:59
    #10641268

    Если нумеровать бутылки двично то есть два состояния. Выпить или не выпить и этих состояний не хватает. Для того чтобы 5-ю разрядами занумеровать 240 бутылок.
    Если нумеровать бутылки троично то можно 5-ю разрядами занумеровать. Трактовать следующим образом
    0 — не пить из бутылки
    1 — выпить из бутылки
    2 — *** (пока удалил т.к. возможно кто-то еще захочет решить)


  1. apapacy
    30.01.2018 11:30
    #10642708

    Те кто говорит что такие вопросы не нужны наверное тоже правы. Если компания разрабатывает например несложные сайты и не собирается делать что то другое то такой излишне творческий человек или уйдёт очень но скоро или же начнёт разрабатывать «свою CMS»(ТМ)