20.01.2018 08:23
reci 52 7000 Источник
Мы подготовили новый выпуск ITренировки с вопросами и задачами от ведущих IT-компаний.

КДПВ

В подборку попали вопросы, встречающиеся на собеседованиях в Adobe (да, вопрос про цвет включён в подборку :). Задачи различного уровня сложности, но все решаемые. Особенно, если Вы уже ответили на вопросы из прошлых выпусков.

Надеемся, что приведённые задачи помогут Вам качественно подготовиться к предстоящим собеседованиями.

Вопросы


  1. 8 marbles
    Let’s say you have 8 marbles and a two-pan balance.
    All of the marbles look the same. Each marble weighs 2.0 grams except for one, which is slightly heavier at 2.05 grams.
    How would you find the heaviest marble if you are only allowed to weigh the marbles 2 times using the balance scale?

    Перевод
    Предположим, у вас 8 стеклянных шариков и чашечные весы. Все шарики выглядят одинаково. Каждый весит 2 грамма, за исключением одного, который чуть тяжелее — 2.05 грамма.
    Как найти самый тяжёлый шарик, если разрешено провести всего 2 взвешивания?

  2. Falling bear
    A bear fell from a height of 10m on the ground in v2 seconds. But somehow, it didn’t get hurt. What is the colour of bear?

    Перевод
    Медведь, падая с высоты 10м, достигает земли за v2 seconds и, почему-то, остаётся без повреждений. Какого цвета медведь?

    Прим: Я некоторое время подумал, и всё-таки заглянул в ответ. Вопрос немного с подвохом, но ответить можно. Решил привести здесь, если такое на собеседованиях встречается.

Задачи


  1. Product of max and min in 2 arrays
    Given two arrays of integers, the task is to calculate the product of max element of first array and min element of second array.

    Ex:
    Input: arr1[] = {5, 7, 9, 3, 6, 2},
    arr2[] = {1, 2, 6, -1, 0, 9}
    Output: max element in first array
    is 9 and min element in second array
    is -1. The product of these two is -9.

    Input: arr1[] = {1, 4, 2, 3, 10, 2},
    arr2[] = {4, 2, 6, 5, 2, 9}
    Output: 20.

    Перевод
    Даны 2 массива целых чисел. Задача — вычислить произведение максимального элемента из первого массива и минимального из второго массива.

    Примеры:
    Даны: arr1[] = {5, 7, 9, 3, 6, 2}, arr2[] = {1, 2, 6, -1, 0, 9}
    Ответ: максимальный элемент первого массива — 9, минимальный элемент второго -1. Произведение -9.

    Даны: arr1[] = {1, 4, 2, 3, 10, 2},
    arr2[] = {4, 2, 6, 5, 2, 9}
    Ответ: 20.

  2. Maximum Chocolates
    You have $15 with you. You go to a shop and shopkeeper tells you price as $1 per chocolate. He also tells you that you can get a chocolate in return of 3 wrappers. How many maximum chocolates you can eat?

    Write a program to find solution for variable inputs. Given following three values, the task is to find the total number of maximum chocolates you can eat.

    money: Money you have to buy chocolates
    price: Price of a chocolate
    wrap: Number of wrappers to be returned for getting one extra chocolate.

    It may be assumed that all given values are positive integers and greater than 1.

    Перевод
    У Вас есть $15. В магазине у продавца Вы узнаёте цену за шоколадку — $1. Продавец также сообщает, что за 3 обертки выдаст вам ещё шоколадку. На какой максимум шоколадок Вы можете рассчитывать?

    Напишите программу для переменных входных данных, задачей которой будет найти максимум шоколадок:

    money: Имеющиеся деньги
    price: Цена за шоколадку
    wrap: Количество обёрток нужное, чтобы получить ещё одну шоколадку.

    Можно считать, что все входные данные являются целыми и больше 1.

  3. Sort array larger than RAM
    Given 2 machines, each having 64 GB RAM, containing all integers (8 byte). You need to sort the entire 128 GB data. You may assume a small amount of additional RAM.

    Перевод
    Имеются 2 компьютера, у каждого по 64 Гб ОЗУ, занятых целыми числами (8 байт). Вам необходимо отсортировать все 128 Гб данных. Можно использовать небольшое количество дополнительной памяти ОЗУ.


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

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


  1. renskiy
    20.01.2018 11:39
    #10626344

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


    1. reci Автор
      20.01.2018 11:46
      #10626352

      Это всё-таки три взвешивания :)
      Можно обойтись двумя.


      1. renskiy
        20.01.2018 12:16
        #10626392
        +1

        другой ответ на первый вопрос
        1. берем шесть шариков по 3 на каждую чашу
        2. если чаши равны, то искомый шарик в оставшихся двух
        3. если не равны, то выкидываем три самых легких
        4. взвешиваем 2 из оставшихся трех — задача решена :)


        1. LonelyCruiser
          20.01.2018 12:29
          #10626418

          Правильно. Это старая задачка. Более внушительно выглядит если нужно найти 1 шарик из 27 за 3 взвешивания.


          1. ptyrss
            20.01.2018 12:43
            #10626428

            более внушительно выглядит найти 1 шарик из 13 за 3 взвешивания, если не известно легче он или тяжелее.

            В целом из задач только над 3 можно подумать. Остальные явно на позицию юниора не выше. Ну или во 2 искать точную формулу и пытаться убрать цикл (а возможно ли это?).


            1. Lelushak
              20.01.2018 23:09
              #10626976

              Возможно.
              Для примера из условия:

              Доллар даёт одну шоколадку; шоколадка даёт одну обертку; одна обёртка даёт 1/3 шоколадки.

              Тогда, при условии, что у нас бесконечное количество долларов, мы за каждый доллар получим:

              1 + 1/3 + 1/9 + 1/27… шоколадок. Это убывающая геометрическая прогрессия. Если посчитать её сумму, то получим 1.5 шоколадки за каждый потраченный доллар.

              Однако, у нас не бесконечное количество долларов. Для того, чтобы узнать, сколько шоколадок мы получим за один доллар, достаточно узнать, на каком шаге вычисления прогрессии мы остановимся:

              x<=3: 1
              3<x<=9: 1 + 1/3
              9<x<=27: 1 + 1/3 + 1/9
              …

              Тогда решение задачи для примера из условия выглядит так:

              x = 25
              3^1 = 3 < x
              3^2 = 9 < x
              3^3 = 27 > x => нужно вычислить три шага

              1 + 1/3 + 1/9 = 13/9

              Теперь просто перемножаем: 15 * 13/9 = 21,6666666 ~ 21 (округляем всегда в меньшую сторону). Решение можно представить в обобщенном виде для любых «money, price, wrap».


              1. Lelushak
                21.01.2018 01:14
                #10627056

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


                1. Segrio
                  21.01.2018 09:45
                  #10627200

                  Приведите, пожалуйста, пример, где указанный вами выше подход не работает? Как один пример, когда формула работает: возьмем 14 уе, тогда 14*13/9=20.2(2), в ручную: 14 + 4 (две обертки в остатке) + 2 (2 обертки остатка, 4 обертки от второй партии) = 20.


                  1. Lelushak
                    21.01.2018 17:59
                    #10627564

                    Даже для исходного примера неправильно, как ниже заметил s_suhanov. Вроде удалось обобщить, проверил для 1 <= money <100000, 1 < price < 50, 2 < wrappers < 50— расхождений с итеративным алгоритмом нет. Буду рад, если кто-нибудь опровергнет.

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

                    На первой итерации каждый потраченный доллар гарантированно принесёт нам 1/price шоколадок. На второй: 1/price*wrappers и так далее. Снова получается геометрическая прогрессия. Первый шаг не зависит от wrappers, поэтому в прогрессию мы его не включаем. Теперь нужно посчитать s(n), — где n — это степень, при которой wrappers^n >= workMoney (по-хорошему, здесь должно быть просто «больше», но из-за потери точности даже в Decimal и округления вниз в некоторых ситуациях получается число вроде 47.9999999996 вместо 48), a0 = 1/wrappers * price.

                    Финальный шаг: сложим 1/price и s(n) и умножим на workMoney. Округляем в меньшую сторону.

                    Примеры:

                    money = 15, price = 1, wrappers = 3
                    workMoney = 15
                    n = 3, s(3)=1/3 + 1/9 + 1/27 = 14/27 ~ 0.4815
                    1 + 0.4815 = 1.4815

                    result = 15 * 1.4815 ~ 22.22 = 22

                    money=17, price = 3, wrapers = 5
                    WorkMoney = 15
                    n = 2, s(2) = 1/5*3 + 1/25*3 = 1/15 + 1/75 = 7/75
                    1/3 + 7/75 = 32/75 ~ 0.427

                    result = 15 * 0.427 ~ 6,3 = 6

                    Код:

                    private static int ChocolateCount(int money, int price, int wrappersPerOneChoco)
{
	var workMoney = money - (money % price);

	var stepsCount = 0;
	int wrappers = 1;

	while (wrappers <= workMoney)
	{
		stepsCount++;
		wrappers = wrappers * wrappersPerOneChoco;
	}

	var chokosPerDollar = 1 / (double)price;
	var additionalChokosByCurrentStep = 1 / (double)price;

	for (int i = 0; i < stepsCount; i++)
	{
		additionalChokosByCurrentStep = additionalChokosByCurrentStep / wrappersPerOneChoco;
		chokosPerDollar = chokosPerDollar + additionalChokosByCurrentStep;
	}

	return (int) (workMoney * chokosPerDollar);
}


                    1. Segrio
                      22.01.2018 03:32
                      #10627918

                      Ну получается же, что нужно брать на один шаг глубже, т.е. если более 9 уе (3^2), то глубина 3 шага: 1+1/3+1/9+1/27, если более 27 уе (3^3), то 4 шага итд, в самом принципе я не вижу проблемы.


              1. s_suhanov
                21.01.2018 13:14
                #10627344

                Но ведь ответ не 21, а 22.


                15 долларов == 15 шоколадок.
                15 оберток == 5 шоколадок. (нарастающий итог == 20)
                5 оберток == 1 шоколадка и 2 обертки (нарастающий итог == 21)
                1 обертка от шоколадки и 2 обертки с пред. шага == 1 шоколадка (итог == 22).


                1. Lelushak
                  21.01.2018 18:00
                  #10627568

                  Ответил в ветке выше.


                  1. s_suhanov
                    22.01.2018 12:44
                    #10628376

                    Да, сорри. Был невнимателен. :(


                1. oleg1977
                  21.01.2018 18:23
                  #10627602

                  + одна обёртка, эквивалентная 0.5 шоколадки, итого 22.5


                  1. s_suhanov
                    22.01.2018 12:45
                    #10628378

                    Одна обертка эквивалентна 1/3 шоколадки. :) Итого 22.333333333… :)


            1. kardan2
              22.01.2018 18:24
              #10629070

              Формула проста. Как было сказано, мы меняем 3 обвертки на 1 шоколадку+обвертку. Или по другому, мы получаем новую шоколадку ценой потери 2-х оберток. Но последние 2 обвертки мы поменять на шоколадку не можем, поэтому нужно 1 обвертку вычесть.

                  public static int calcChocoCount(int money, int price, int wrap){
        int chocoByMoney = money/price;
        return chocoByMoney + (chocoByMoney-1)/(wrap-1);
    }


      1. myalenka
        22.01.2018 20:05
        #10629308

        1. по 3 шарика
        или весики уравновесятся или будет перевес
        1.1 если уравновешены — значит тяжелый шарик один из двух оставшихся, просто взвешиваем их, находим нужный
        1.2 если какие-то три перевесили, снова взвешиваем любые 2 из них
        1.2.1 если весы уравновешены — тяжелый третий из этой выборки
        1.2.2 если весы уехали — ниже тяжелый

        Получили за 2 взвешивания


    1. baluevine
      20.01.2018 11:54
      #10626366

      технически это три взвешивания)


  1. renskiy
    20.01.2018 12:10
    #10626382
    +1

    возможный ответ на второй вопрос
    если медведь упал с 10 метров за v2 секунды, то значит ускорение свободного падения в его местности равно 10 м/с^2, что немного расходится со всеми известными значениями для планеты Земля :) Но если брать максимальное значение, то оно находится на полюсе, а значит медведь скорее всего белый, так? :)


    1. XeNum
      20.01.2018 19:00
      #10626736

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


      1. Manitou
        20.01.2018 22:42
        #10626940

        Думается, всё несколько проще
        Это бурый медведь, иначе где вы видели в Арктике деревья?


        1. vsapronov
          21.01.2018 07:22
          #10627146
          +1

          Айсберги же!


      1. x86d0cent
        20.01.2018 22:46
        #10626952

        Так 10 — это больше, чем ускорение свободного падения. Оно 9.8 (различия полюс/экватор во втором знаке после запятой). Думаю, это просто округление до целых.

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


    1. dikhim
      20.01.2018 22:46
      #10626956

      Как-то все сложно…

      Заголовок спойлера
      Думаю, он просто упал в снег. Потому он белый. А свободное падение тут не при чем.


      1. Sohei
        22.01.2018 12:21
        #10628334

        Бурые медведи живут там, где есть зимы и снег. А вот в местах обитания белых медведей деревьев не особо.


        1. x86d0cent
          23.01.2018 10:25
          #10630080

          Деревьев нет, зато есть торосы и скалы. Впрочем, про снег подмечено верно.

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


          1. Sohei
            23.01.2018 12:09
            #10630326

            А еще нигде не сказано, что медведь не игрушечный.

            Но больше всего смущает ускорение свободного падения. При нормальном ускорении он бы 10 метров пролетел за секунду с небольшим. А v2 это 1.414 примерно, так где он по пути задержался? Но опять же не сказано, что он мог по пути что-то задевать.

            А еще можно сказать, что и бурые, и белые медведи с черной кожей, поэтому они черные!

            В любом случае вопрос мне кажется довольно странным.


            1. x86d0cent
              23.01.2018 16:42
              #10631098
              +1

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


              1. Sohei
                23.01.2018 22:00
                #10631740

                Мда, все-таки в арифметических задачах я, мягко говоря, не силен.


  1. baluevine
    20.01.2018 12:17
    #10626394

    Задача 3

    int total_chocolate_count(int money_, int price_, int wrap_) {
    int total_count = money_ \ price_;
    int prev_count = total_count;
    do {
        total_count += prev_count \ wrap_;
        prev_count = prev_count \ wrap_ + prev_count % wrap_;
    }
    while (prev_count \ wrap_ == 0)
    return total_count;
}


    1. pvl_1
      20.01.2018 12:43
      #10626430

      Обычно оператор деления всё же "/". Но по существу с решением согласен.


    1. baluevine
      20.01.2018 17:55
      #10626684

      Конечно же имелась в виду задача №2


  1. oleg1977
    21.01.2018 02:01
    #10627088

    За 1 доллар можно купить 1 1/3=4/3 шоколадки, за 15 долларов — 15*4/3=20 шоколадок. 2 фольги можно превратить в шоколадку: показать их продавцу и попросить шоколадку, которая будет тут же съедена и все 3 фольги отданы продавцу


    1. oleg1977
      21.01.2018 18:16
      #10627582

      исправление: за 3 фольги можно получить то же, что за 1 доллар, значит фольга стоит 1/3 доллара, а шоколадка без фольги — 2/3 доллара. За 15 долларов можно съесть 15/(2/3)=22.5 шоколадки без фольги. если есть фольга, то можно съесть 0.5 шоколадки следующим образом: найти компаньона с 1 фольгой, прийти в магазин, показать 2 фольги продавцу и попросить его шоколадку, отдать 2 фольги плюс фольгу из шоколадки продавцу, фольгу без шоколадки разделить с компаньоном


      1. Sohei
        22.01.2018 20:22
        #10629330

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


  1. erty
    21.01.2018 04:21
    #10627118

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


    1. archimed7592
      21.01.2018 10:08
      #10627222

      Задача решается без массивов :)


    1. alexeykuzmin0
      21.01.2018 12:48
      #10627318

      Эффективнее было бы решить без использования массивов. Например, числа могут быть даны генератором.
      А уж решение с сортировкой 100% будет завернуто как неэффективное.


  1. erty
    21.01.2018 04:22
    #10627120

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


  1. erty
    21.01.2018 04:22
    #10627122

    .


  1. erty
    21.01.2018 04:25
    #10627126

    то ли я лагаю, то ли хабр. Ну пусть буду я. Про C уже посмотрел, что там есть массивы


  1. asdoc
    21.01.2018 12:37
    #10627304

    1. Вопрос.
    Взвешиваем любые 3 и 3. Если они одинаковые, то взвешиваем оставшиеся 2. Находим тяжелый.
    Если одна из троек тяжелее, то взвешиваем два шарика из «тяжелой» тройки. Любые. В результате искомый шар будет или одним из двух, или оставшимся, не взвешенным.


  1. asdoc
    21.01.2018 12:42
    #10627308

    2. Любого или грязного. Например, если медведь игрушечный.


  1. asdoc
    21.01.2018 12:45
    #10627310

    3. 22 шоколадки. Сначала 15, потом 5, потом 1. Потом остается две обертки от 5 и одна от последней. Итого 22.


    1. oleg1977
      21.01.2018 18:21
      #10627598

      остаётся ещё 1 обёртка, на которую можно съесть ещё 0.5 шоколадки, выше написано как. итого 22.5


      1. s_suhanov
        22.01.2018 12:43
        #10628374

        1 обертка == 1/3 шоколадки. :)


        1. alexeykuzmin0
          22.01.2018 17:29
          #10628950
          +1

          Нет. 1 обертка == 1/3 шоколадки с оберткой == 1/2 шоколадки без обертки.


        1. oleg1977
          23.01.2018 00:35
          #10629708

          здесь имелось в виду, что 1 обёртка эквивалентная 0.5 шоколадки без обертки


  1. kardan2
    21.01.2018 18:24
    #10627606

    Да уж. В этом выпуске задачи просто поразили.

    Задача с произведением мин-макс меня вгоняет в ступор. Если там нет дополнительных ограничений, и в задаче нужно найти минимальный элемент, максимальный элемент, и просто перемножить, то смысла в задаче не вижу.

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

    Решения мои

    Заголовок спойлера
    Вопрос 1.
    Заголовок спойлера
    В общем виде за n взвешиваний можно найти шарик среди не более 3^n штук. Таким образом за 2 взвешивания можно найти нужный шарик из 9. Кол-во 8 дано с целью запутать человека, чтобы он решал вопрос в степенях двойки.


    1. reci Автор
      22.01.2018 12:23
      #10628342

      >Задача с произведением мин-макс меня вгоняет в ступор
      Видимо, расчёт на то, что кандидат будет 2 часа искать подвох в задаче :)


  1. reci Автор
    22.01.2018 12:22
    #10628338

    .


    1. reci Автор
      22.01.2018 12:23
      #10628340

      .