23 вопроса, которые бы вы не хотели услышать на интервью

Опубликовано Apr 17, 2012 в Олимпиадные задачи | 30 коммент.

,

23 вопроса, которые бы вы не хотели услышать на интервью

На ресурсе BusinessInsider опубликована статья с любопытным названием “23 Real Job Interview Questions You Don’t Want To Be Asked”.

Заинтересовал вопрос номер 2.

Дабы не искушать защитников животных я опубликую его в оригинале на английском языке:

There 1,000 buckets, one of them contains poison, the rest of them are filled with water. They all look the same. If a pig drinks that poison, it will die within 30 minutes. What is the minimum number of pigs you need to figure out which bucket contains the poison within one hour?

Как обычно – ожидаем решение в комментариях.


30 Коммент. : “23 вопроса, которые бы вы не хотели услышать на интервью”

  1. Английский, конечно, смягчает жестокость вопроса…
    И еще вопрос – смысл этих экспериментов. Нужно яд найти, чтоб потом кого-то отравить? Невозможно – его уже выпьет свинья. Тогда, наверное, нужно оставить хорошую воду людям после свиней…

    • Яков says:

      Предлагаю заменить лакмусовыми бумажками – которые, например, краснеют в течении 30 мин, после попадании на них отравленной воды.
      Сколько таких бумажек может потребоваться?

      Для создания аналогии придется добавить дополнительные условия:
      - бумажка краснеет полностью (нет возможности использовать ее по частям)
      - время реакции – до 30 мин. Может покраснеть через минуту, а может и через 30 – это не определено.
      - разрезать нельзя (испортится)
      - попадание воды не приводит к порче бумаги (многоразовая, можно через долю секунды использовать с другой пробой)

  2. Как вам нравится такой ответ – нужна всего одна свинья (бумажка). Ведь может такое случиться что мы сразу же макнем бумажку в отравленное ведро. Вероятность маленькая, но такое возможно.

    • Яков says:

      В задаче ожидается точный ответ с вероятностью = 1 (или 100%)

      Вдруг вам доверят проектировать, например, схему движения поездов, и вы решите, что одной проверки достаточно, а там “повезет” :)

  3. Может это и не очень существенно… Но всё-же, мы может пронумеровать бумажечки?

  4. The Ork says:

    нужно 334 свиньи. Разделим 1000 ведер на 2 партии по 500 штук (точнее на 501 и 499), будем поить из них свиней в 2 захода:
    на каждые 3 ведра – 2 свиньи, свинья №1 пьет из первого и второго ведра, свинья №2 из второго и третьего. Если обе живы через 30 минут – яда не было, сдохла первая – яд был в первом ведре, сдохла вторая – яд был в третьем. Сдохли обе – яд был во втором ведре. Если никто из свиней после первого захода не помер – повторяем операцию со оставшимися ведрами. Если есть желание дать свиньям шанс справиться с заданием без потерь – одну ведро можно отставить в сторону . Если через час никто из свиней не помрет – яд в этом оставленном ведре )

    • Галина says:

      Вполне приемлемое решение, как мне кажется.

      Сумеем обойтись меньшим количеством свиней? Если подхватить и развить идею автора – делить ведра на группы, а из свиней создавать команды.

      • The Ork says:

        Извиняюсь, поленился еще подумать
        Достаточно будет 300 свиней – по 3 свиньи на 5 ведер
        свинья №1 пьет из первого и второго ведра, свинья №2 – из третьего и четвертого, свинья №3 – из первого, третьего и пятого ведер.

  5. The Ork says:

    Опять я поспешил, хватит 251 свиньи )

  6. У меня получилось 34 свиньи. Нужно давать пить каждой из 34-х свинок каждую минуту из разных вёдер (главное, записать, из какого ведра какая свинка пила и в какое время) в течение первых 30 минут. Каждая свинка успеет попробовать воду из 30 вёдер, 34 х 30 = 1020 (получается даже с запасом), а если яд окажется в последних вёдрах, будет как раз вторые 30 минут для того, чтобы он подействовал. По времени смерти невезучей свинки определяем, в каком ведре яд.

  7. Маленькое дополнение: из последнего ведра можно вообще никого не поить, если все свинки останутся живы, значит яд там.

  8. Alexander Lobas says:

    10 свиней хватит чтобы определить за 30 мин. (при условии что каждая свинья сможет почти мгновенно попробовать жидкость из 500 ведер).
    - нумеруем ведра целыми числами, записываем их в двоичном виде. каждую свинью ассоциируем с номером бита от 0 до 9 и даем пить только из тех ведер в номере которых соответсвующий бит установлен в 1. (можно пронумеровать до 2 в 10 степени ведер). в результате через 30 мин (после окончания попойки) мы будем знать какие биты у номера ведра с ядом установлены в 1 (мертвые свиньи) а какие в 0 (живие свиньи).
    ——-
    в случае если у нас есть час, и выживших свиней можно использовать повтороно. то достаточно будет 7 свиней.
    (если бы ведер было 729 – то хватило бы и 6 свиней).
    идея такая: разбиваем ведра на группы, нумеруем группы.
    на первой стадии (первые 30 мин) наша цель определить группу ведер в которой есть яд. на второй – конкретное ведро в группе. следовательно в группе должно быть кол-во ведер равное 2 в степени “число выживших свиней после идентификации группы”. (а число выживших свиней = равно числу нулей в номере группы) итого: при N свиньях
    первая группа будет иметь номер: 1111111 (N единиц в двоичном предствлени) – 1 ведро (т.к все свиньи умрут на первом этапе если будет идентифицирована эта группа)
    вторая: 1111110 ( N-1 единица + 0) – 2 ведра (одна свинья выживет – на втором шаге мы ее используем для определения какое из двух ведер содержит яд).
    таких как вторая группа будет N групп.
    и т.д.
    групп с K нулями в номере будет равно числу сочетаний из N по K. и в каждой такой группе будет 2 в степени К ведер.
    итого имея N свиней мы может иденетифицировать яд в одном из ( сумма по К от 0 до N ( (2 в степени К) * (число сочетаний из N по К) )) ведер.

    при N = 6 свиней таким алгоритом мы можем найти яд в одном из 729 ведер.

    при N = 7 свиней будет достаточно, чтобы решить даную задачу для 1000 ведер.
    ————————————————

    • Яков says:

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

  9. Чтобы мое решение не казалось слишком варварским :) предлагаю минимизировать число жертв
    в указаном решении с 7 свиньями.

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

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

     
    class Program
    {
        // returns number of bit set to 1;
        static int getBitCount(int v)
        {   
            int res = 0;
            while (v > 0)
            {
                v &= (v - 1);  // clear last bit
                res++;
            }
            return res;
        }
     
        static void Main(string[] args)
        {
            int bucketCount = 1000;
            int N = 7; // number of pigs
     
            // enumerate all possible cases and store 
            // number of dead pigs for each case
            List<int> deadPigsPerCase = new List<int>(); 
            for (int groupNo = 0; groupNo < (1 << N); ++groupNo)
            {
                int deadPigs = getBitCount(groupNo);
                for (int bucketNo = 0; bucketNo < (1 <= bucketCount, "Number of pigs is not enough to identify poison");
     
            // sort - cases with smaller number of dead pigs will be first and will be used by us.
            deadPigsPerCase.Sort();
     
            // calculate expected value: total number of death for all cases altogether / number of cases(buckets)
            int expectedVal = 0;
            for (int i = 0; i < bucketCount; ++i)
                expectedVal += deadPigsPerCase[i];
     
            Console.WriteLine("Expected value of dead pigs: {0}", (double)expectedVal / bucketCount);
            Console.WriteLine("Worst case dead pigs: {0}", deadPigsPerCase[bucketCount - 1]);
     
            // calculate probablity distribution
            int[] distrib = new int[N + 1];
            for (int i = 0; i < bucketCount; ++i)
                distrib[deadPigsPerCase[i]]++;
     
            for (int i = 0; i  0; ++i)
                Console.WriteLine("Probability that {0} pigs dies is {1}", i, (double)distrib[i] / bucketCount);
        }
    }

    в итоге получим при оптимальном разбиении на группы и назначении номеров.
    в худшем случае погибнет 5 свиней. (как минимум 2 свиньи всегда остаются живы).
    вероятность возникновения худшего случая: 0.061 (6.1%)
    при многократном проведении процедуры поиска яда в среднем будут погибать 3.567 свиньи.
    вероятность, что все свиньи останутся живы: 0.001 (0.1%) – и любое корректное решение не сможет дать лучшую вероятность happy end’a.
    —-
    для сравнения:
    в решении Ork’а – 334 свиньи – 2 свиньи на 3 корыта:
    вероятность смерти 2х свиней: 0.333
    вероятность сметри 1й свиньи: 0.666
    вероятность смерти 0 свиней : 0.001 (отставленное в сторону ведро).

    в среднем гибнет: 1.333 свиньи (против 3.567)
    в худшем случае: 2 свиньи (против 5).

  10. Для модератора: форматирование csharp кода выглядит ужасно " вместо “, < вместо < , у List – int вообще пропал.

    как такая солидная на первый взгляд компания у которой в названии выделено слово Web (по-видимому занимающаяся веб проектами) может допусткать такие глупые баги в своем собственном сайте?

    • Kostiantyn says:

      Справедливое замечание. Спасибо.

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

  11. Если подытожить – решение, созданное с применением навыков программиста (использование свиней как идентификаторов бит в числе) – оказалось самым эффективным и в тоже время – самым беспощадным :)

    • Alexander Lobas says:

      Хочу заметить, что формально никто из отписавшихся тут не привел полное решение данной задачи… в задаче спрашивается какое МИНИМАЛЬНОЕ количесво свиней необходимо чтобы определить где яд. это означает что нужно А) привести алгоритм определения яда для определенного числа свиней и Б) доказать, что не существует решения с меньшим числом свиней.
      В совем посте я показал что существут решение для 7 свиней. но не приводил доказательства того, что решения с 6-тью свиньями не существует. и почему-то никто не обратил на это внимания.

      если когда-нибудь я попаду к вам на собеседование, я обязательно поделюсь с вами своими мыслями по поводу такого доказательства.

  12. Достаточно одной свинки. Засечь стартовое время и скармливать ей очередную порцию через каждые 1.8 сек.

    • Нет, не достаточно.
      Пожалуйста, обратите внимание на постановку задачи.
      В задаче сказано – “within 30 minutes”.
      Т.е. продолжительность жизни свинки после употребления жидкости составит от миллисекунды до 30-ти минут, но не более.

  13. i’m thing that i’m will be enough a 100 pigs to find out an answer 4 this question.
    Let see. I have 1000 containers one of them contains a poison. And i have a 100 pigs to find out wich from them has a poisoned water. So i will do that thing.
    Let’s divide a 1000 container on 10 pigs for an instance.
    And we will have a 10 sets of containers, with 100 containers on each unit on the set. So some of this unit will be poisoned,
    And on each pig will be a 100 container with a water.
    So we will ask 9 pigs to drik from this containers.
    IF(
    after half of hour 1 of 9 pigs is dead. That’s will be bad. But we exactly know from which unit of the set she was drinking) and we have a 99 alive pigs.

    Else
    (if all piggs are alive. We know from which unit of the set piggs was not drinking)And we have a 100 alive pigs which we will use next.

    So the next we have to do is to to ask the alive pigs to drink againe from the poisoned unit of the set, and if one of pigs will die againe we will know what container is poisoned. If not whe have only one container from which pigs did not drinks a water.
    So iа the best happened we wil pass around without death’s
    If the worst happends we will have a 2 dead pigs on our concience.
    Please send me a mail, if some body has a better solution, i want to hear it.

    • Спасибо за усилия, связанные с формулировкой комментария на английском языке. Практика – это залог успеха. Судя по тексту вам стоит продолжать усиленно практиковаться :)

      Относительно задачи,первое, на что вам стоит обратить внимание – это на четкое понимание постановки задачи.
      В постановке спрашивается – какое минимальное количество подопытных необходимо для идентификации сосуда с ядом. При этом ничего не сказано относительно необходимости сохранения их жизней.
      Вы использовали 10 * 100 свинок. А можно было, например, 33 * 33. Если же пытаться сохранить жизни – то ваше решение верное.

  14. Достаточно 32 свиньи. 24 пьют из 31 ведра каждая, 8 – из 32ух каждая. Если гибнет одна из этих 8-и (рассматриваем сложный случай), то оставшимся 31 свиньям даём выпить из 31 ведра (по одному ведру на каждую). Так и выясняем где отрава. Если же, (о!чудо!) через полчаса все живы, то яд содержится в 32ом ведре.

  15. Alehandro says:

    Может уже и поздно оставлять свой комментарий, но у меня меньше 9 поросят за час времени не получается.
    Ответ: мне нужно девять поросят.

  16. Alehandro says:

    Кстати, я вижу, что здесь собирается аудитория которая может решить любую задачу! А если эту не простую задачу про 1000 вёдер воды взять и ещё усложнить?!?
    Как именно? А просто: как в лучших традициях детективного жанра добавить ещё в одно какое-нибудь ведро противоядие. И вот вопрос:
    ” Какое минимальное количество поросят необходимо, чтоб определить в каком из 1000 вёдер находится яд, а в каком противоядие? ”
    Эту задачу я уже решить не могу, и даже не представляю как её решить!

    • Галина says:

      Ну можно начать так.
      0) ДОПОЛНИТЕЛЬНО СЧИТАЕМ
      0.а. Если выпить противоядие, не выпив при этом предварительно яд, то действие противоядия не обнаружится.
      0.б. Противоядие действует безотказно, вне зависимости через сколько времени ПОСЛЕ приема яда его выпили, если еще не померли.
      0.в. Противоядие, выпитое ДО приема яда, не действует.

      ТОГДА точно достаточно количества свиней, которое равно количеству ведер.

      1) ДЕЙСТВУЕМ
      1.1. Даем каждой из 1000 свиней попробовать одно ведро. Через пол часа знаем, где яд, одна свинья, увы, погибла. Осталось 999 свиней и 999 ведер, в одном из котрых противоядие.
      1.2. Даем каждой из оставшихся свиней попить из ведра с ядом и из одного из непроясненных 999-ти ведер. Через пол часа знаем, где противоядие, 998 свиней погибли.

      Результат достигнут, но какой ценой! Можно ли его улучшить? Этому вопросу посвящен новый пост “Снова свиньи и ведра”.

      • Alexander Lobas says:

        Ваше решение задачи содержит математическую неточность, и строго говоря является неверным. В условии как вы сами написали, противоядие действует безотказно если его выпить ПОСЛЕ яда. для того, чтобы ваше решение было верным – противоядие должно действовать безотказно если его выпить ВМЕСТЕ с ядом. т.к если яд был выпит в момент времени t1 а противоядие в t2. ПОСЛЕ означает, что t1 < t2. следовательно существет такой момент времени t ( t1 < t < t2, например t = (t1 + t2)/2)) в который свинья может умереть не дожив до питья противоядия, и в приведеный вами алгоритм не позволит определить где было противоядие.

  17. алексей says:

    Может я что-то не так понимаю, но вроде хватит 1 свиньи. Пусть свинья пьет воду из каждого ведра таким образом: в первую секунду из первого, во вторую — из второго и т.д. Таким образом чтобы узнать какое ведро с ядом, нужно от времени смерти свиньи в секундах отнять 1800 и получим номер ведра.

    • Галина says:

      Так не пойдет – яд хитрый. Может подействовать через минуту, может через 10, а может через 30. Это уточнялось в самых первых комментариях по задаче.

  18. Может мой вариант слегка запоздалый, но попытаюсь предложить свое решение. Нужно upperBound(sqrt(1000)) свиньи. Сначала поделим 1000 корзин на равные участки . Тот после которого свинья умрет – содержит решение. Далее оставшимся свиньям даем каждой по еде из каждой корзины и там где свинья умрет – будет ответ.

Оставить комментарий

Ваш адрес email не будет опубликован.


*