10 математических и логических задач с собеседований в Apple, Google, Adobe и Microsoft

303670
144
Читать на UA

Кто не хотел бы попасть на работу в Google, Intel, Amazon или Apple? Многие IT-компании известны тем, что на собеседовании задают претендентам каверзные задачи на математику, логику и общую смекалку. Наверное, один из самых известных примеров — вопрос о том, почему канализационные люки круглые. Редакция AIN.UA постаралась найти самые интересные примеры таких задач, для решения которых нужны знания по математике на школьном уровне или просто смекалка. Некоторые из них приводят сами компании, некоторые публикуют пользователи, которые ходили на собеседование, некоторые собраны на популярных сайтах с задачами.

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

Что спрашивают в Apple

  1. Задача на логику. Шелдон Купер (этот гениальный физик из популярного сериала) дошел в игровом квесте по поиску сокровищ до последнего рубежа. Перед ним две двери, одна ведет к сокровищу, вторая — к смертельно опасному лабиринту. Возле каждой двери стоит часовой, каждый из них знает, какая дверь ведет к сокровищу. Один из часовых никогда не врет, другой — врет всегда. Шелдон не знает, кто из них лжец, а кто нет. Прежде чем выбрать дверь, можно задать только один вопрос и только одному часовому.

Вопрос: что Шелдон должен спросить у часового, чтобы добраться до сокровища?

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

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

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

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

Вопрос: Что нужно отвечать, чтобы выжило как можно больше людей?

Ответ: Первый, кто отвечает, считает количество зеленых шляп перед собой: если это нечетное число, он называет «зеленый», если четное — «розовый». Следующий, видя количество и цвет шляп перед собой, может таким образом понять, какого цвета шляпа у него на голове (например, если зеленых все еще нечетное количество, то очевидно, что на нем — розовая), и так далее. Таким образом гарантированно выживают 9 из 10, а у того, кто отвечал первым, шанс 1 к 1.

Что спрашивают в Adobe

  1. У вас 50 мотоциклов, каждый с заполненным топливом баком, которого хватает на 100 км езды.

Вопрос: используя эти 50 мотоциклов, насколько далеко вы сможете заехать (учитывая, что изначально они находятся в условно одной точке пространства)?

Ответ: самый простой ответ: завести их все одновременно и проехать 100 км. Но есть и другое решение. Сначала переместите все мотоциклы на 50 км. Затем перелейте топливо из половины мотоциклов в другую половину. У вас таким образом — 25 мотоциклов с полным баком. Проедьте еще 50 км и повторите процедуру. Так можно преодолеть 350 км (не учитывая того топлива, которое останется от «лишнего» мотоцикла после деления 25 надвое).

Что спрашивают в Microsoft

  1. У вас есть бесконечный запас воды и два ведра — на 5 литров и 3 литра.

Вопрос: Как вы отмеряете 4 литра?

Ответ: Наполните водой пятилитровое ведро и вылейте часть воды в трехлитровое. У вас сейчас 3 литра в маленьком ведре и 2 — в большом. Освободите маленькое ведро и перелейте туда 2 литра из большого. Снова наполните большое ведро и перелейте воду в малое. Там уже есть 2 литра воды, поэтому долить придется литр, а в большом останутся 4 литра.

  1. У вас есть два отрезка веревки. Каждый такой, что если поджечь его с одного конца, он будет гореть ровно 60 минут.

Вопрос: Имея только коробку спичек, как отмерить с помощью двух отрезков такой веревки 45 минут (рвать веревки нельзя)?

Ответ: Один из отрезков поджигается с двух концов, одновременно с этим поджигается второй отрезок, но с одного конца. Когда первый отрезок полностью догорит, пройдет 30 минут, от второй веревки также останется 30-минутный отрезок. Подпалив его с двух концов, получим 15 минут.

Задачи в Google

  1. У вас есть 8 шариков одинакового вида и размера.

Вопрос: как найти более тяжелый шарик, используя весы и только два взвешивания?

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

Задачи в Qualcomm

  1. Эту задачку описал пользователь, с которым было собеседование на позицию senior systems ENGINEer. В описании он отметил, что у него был свой ответ, о котором он долго спорил с человеком, который проводил собеседование.

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

Вопрос: какую пропускную способность канала мы получаем?

Ответ: по версии пользователя, ответ должен был быть 9 пакетов в секунду. Но человек, проводивший интервью, с ним не согласился, правда, ответ не назвал, но повторял, что «из-за ретрансмиссии пропускная способность должна уменьшиться больше, чем на 1/10».

Задачи в «Яндекс»

  1. Эту задачу предлагали решить для поступления в Школу анализа данных в феврале 2014 года. Ответов на задачи из «Яндекса» у нас, к сожалению, нет.

Игра состоит из одинаковых и независимых конов, в каждом из которых выигрыш происходит с вероятностью p. Когда игрок выигрывает, он получает 1 доллар, а когда проигрывает — платит 1 доллар. Как только его капитал достигает величины N долларов, он объявляется победителем и покидает казино.

Вопрос: найдите вероятность того, что игрок рано или поздно проиграет все деньги, в зависимости от его стартового капитала K.

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

Есть морфологический словарь объемом примерно 100 000 входов, в котором глаголы совершенного и несовершенного вида помещены в отдельные статьи (то есть «делать» и «сделать» считаются разными словарными входами). Вам нужно найти в словаре такие видовые пары и «склеить» статьи в одну.

Вопрос: опишите общий сценарий решения такой задачи и примерный алгоритм поиска видовых пар.

И бонус

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

  1. На улице стоят пять домов.
  2. Англичанин живет в красном доме.
  3. Испанец имеет собаку.
  4. В зеленом доме пьют кофе.
  5. Украинец пьет чай.
  6. Зеленый дом стоит сразу справа от белого дома.
  7. Тот, кто курит Old Gold, разводит улиток.
  8. В желтом доме курят Kool.
  9. В центральном доме пьют молоко.
  10. Норвежец живет в первом доме.
  11. Сосед того, кто курит Chesterfield, держит лису.
  12. В доме по соседству с тем, где держат лошадь, курят Kool.
  13. Тот, кто курит Lucky Strike, пьет апельсиновый сок.
  14. Японец курит Parliament.
  15. Норвежец живет рядом с синим домом.
  16. Каждый из домов окрашен в отдельный цвет, в каждом доме живет представитель отдельной национальности, у каждого — свой питомец, своя любимая марка сигарет и напиток.

Вопрос: кто пьет воду? Кто держит зебру?
Ответ: Японец держит зебру, норвежец пьет воду.

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

Комментарии | 144

  • Потери пакетов будут 0.1(1) в среднем, ведь вероятность фэйла ретрансляции также 1/10. Таким образом, потери = 0.1 + 0.1 * 0.1 + (0.1)^3 + (0.1)^4 + … (0.1)^(inf) = 0.1(1)
    Поправьте, если не так. Интересно.
    http://www.wolframalpha.com/input/?i=sum+0.1%5Ex+where+x%3D1+to+infinity

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

    • При передаче первых 10 пакетов 9 будет передано. При следующей передаче будет передаваться 1 пакет из предыдущей передачи и 9 новых. 9 будет передано и так до конца полной передачи. Погрешность даст последняя группа.

      • Почитайте оригинал задания. Имеется ввиду «передача десяти пакетов». Передача каждого пакета осуществляется до тех пор, пока он успешно не будет передан (в оригинале — When it fails, the transmitter retransmit the packet, until it finally succeeds). В задаче. очевидно, идет речь о сетевом пакете — 802.11 packet

        • Я внимательно прочитал задание. Я расписал алгоритм по которому получивший задание утверждал, что пропускная способность 9 пакетов в секунду. Формулу Бернулли следует применять для расчета времени, необходимого на полную передачу, а для пропускной способности нужно 10 разделить на 1.111111111(1)

    • Пропускна здатність каналу буде рівнесенько 90%. Інтерв’ювер не правий.
      Поглянемо на задачу за такої сторони. В кожних 10 таймслотах цілі досягають в середньому 9 пакетів, і всі ці 9 пакетів є різними, бо ж ми не передаємо повторно пакет, який досяг цілі. Відповідно пропусна здатність каналу буде рівно 9/10.

      • припустімо, маємо 10 пакетів для передачі, з вірогідністю 10% ми втрачаємо пакет.
        припустімо перший же пакет б’ється, тоді ми його передамо з вірогідністю 100% за наступні 9 ре-трансміссій. так як перший же пакет побився то всі наступні 9 пакетів повинні дійти до цілі неушкодженими.
        отже маємо к-ть трансмісій з ретрансмісіями: 1(битий пакет)+9(ретрансміссій)+9(цілих пакетів) = 19 передач з яких тільки 10 з корисною інформацією, а 9 ре-трансмісії.
        пропускна здатність буде 10/19 => близько 0,53 тобто 53% ніяк, не 90% — повірте.

    • Можемо провести обчислювальний експеримент.

      Хоч потоком з мільйона пакетних передач.

      from random import randint

      s = 0
      for i in range(1000000):
      if randint(0, 9) == 0: continue
      s += 1

      print(s/1000000)

      Хоч 100000 експериментів групами по 10 пакетних передач, точно як в умові.

      from random import randint

      ts = 0
      for t in range(100000):

      s = 0
      for i in range(10):
      if randint(0, 9) == 0: continue
      s += 1

      ts += s/10

      ts = ts / 100000

      print(ts)

      Відповід весь час одна, в середньому рівно 0.9

      • …только вот вероятность неудачной ретрансляции вы упустили 😉

        • Зовсім ні. Код можна розуміти так.
          Робляться спроби передачі пакета доти, доки він не буде успішно переданий. Тільки потім він зараховується (s+=1). Кожна спроба є неуспішною з ймовірністю 1/10 (if randint(0, 9) == 0: continue). Кожна спроба. Ніякої помилки.

          • вы уж простите, но ваш код лишь проверяет равномерность распределения генератора случайных чисел)))

          • Так і є. Але одночасно він є точною моделлю задачі.

          • Вы заблуждаетесь. Сейчас вы проверяете сколько пакетов долетает. Очевидно, ровно столько, сколько вы пропускаете. Ваша же задача — понять сколько нужно в среднем отправить пакетов, чтобы на том конце получили N. Другими словами, сейчас вы почему-то считаете кол-во отправленных пакетов константой и считаете, сколько долетело. А должно быть — полученных константа и посмотреть, сколько надо выстрелить, чтобы долетело.

            Вот мой код, ответ совпадает с моим расчетом. http://ideone.com/TLQbMW

          • Ваша модель нічим принципово не відрізняється, окрім того, що ви інакше інтерпретуєте поняття пропускної здатності. Ви обчислюєте якусь дивну величину, (total_transmited — 100000) / 100000, тобто відношення кількості побитих пакетів (total_transmitted — 100000) до успішно переданих. Ще й віднімаєте її від одиниці, в той час, коли ця величина сама може перевищувати одиницю. Спробуйте ймовірність псування пакету підняти до 9/10 і ви отримаєте пропускну здатність -8.0, що очевидно неможливо.
            Замініть вираз на 1.0 — (total_transmited — 100000) / total_transmited і ви отримаєте точно таке значення, як і в мене. Цей вираз еквівалентний просто 100000/total_transmited, що і є пропускною здатністю каналу, відношенню кількості успішно переданих пакетів до часу передачі (в пакетах).

          • Да, перемудрил что-то (
            На то он и был спор с интервьювером 🙂

          • Наочно демонструє, що пропускна здатність каналу таки рівно одиниця мінус ймовірність неуспішної передачі. Незалежно від того, передаємо ми пакети повторно чи ні (за цієї рафінованої умови задачі звичайно).

          • Задачка с двойным дном))
            По сути, если принять сферического коня в вакууме и считать что отправка неудачного пакета происходит мгновенно, тогда да, надо считать по формуле прогрессивной вероятности sum 0.1^x where x=1 to infinity но фишка в том, что системе пофиг на «неудавшийся пакет» для нее передача неудавшегося = передаче обычного следующего пакета)) все с той же вероятностью 0,9
            т.е. 0,9 — правильный ответ

    • Тільки таби побило. Вставити за сенсом. 🙂

  • Кстати, задача Эйнштейна когда-то была у меня на олимпиаде по программированию. Единственный раз, когда я использовал пролог ))) Ностальгия…

    • Андрей, сколько времени у Вас заняло решение этой задачи? Я потратил на это почти 1.5 часа…(я не программист, тупо упирался в логику). Вероятно, с использованием ваших методик она решается значительно быстрее?

      • Именно эту задачу из статьи не решал, они все однотипные, решаются одинаково через составление таблички. А в школе на прологе заняло где-то часик, пока разбирался с синтаксисом…

  • В Яббл не пойду, ибо задачи на минимизацию потерь 🙂

    • Придумай задачу сам. Вот примеры моих:
      Грибы это мясо или картошка.
      Почему фрукты сладкие а овощи крахмалистые.
      В каком контексте желтый цвет не вписывается в RGB пространство.
      Как измерить кеш пямяти написав код на C++.
      Фотографируем луну без зума — автоматика экспозиции бесполезна — какую ставим эксп. вручную, такую как фото лица 1) днем 2) на закате или 3) ночью.

  • По-моему, в ответе на 6 вопрос неправильная зависимость.

  • В третьей задаче максимально можно проехать 368,5 км. 25 мото — проезжают 52 км, для полного распределения топлива в следующих 12(уже + 2 км). когда остается 3 мото — проезжают 66,6 после чего в последнем моте будет полный бак (еще +100). В итоге 50(50м) + 52(25м) + 50(12м) + 50(6м) + 66,6(3м) + 99,9(1м) = 368,5 км

  • В третьей, по моему, сумма 100/n от 1 до 50, около 450.

    • В задаче про мотоциклы не достаточно начальных условий описывающих место положение 50 мотоциклов. А расстояние которое можно проехать на них зависит именно от этих условий. Если предположить, что они находятся на расстоянии в 100 км друг од друга( а условие «у вас есть 50 мотоциклов» не исключает этот вариант), то удастся проехать 5000 км. Вариант ответа завести их все и проехать 100 км абсурден. С таким же успехом можно завести их все и проехать 0 км. Таким образом можно проехать от 0 до 5000 км в зависимости от начального расположения мотоциклов.

        • Используя эти 50 мотоциклов, как далеко вы сможете заехать? На 50 мотоциклах одному — седалища не хватит.)) Ответ тут очевиден — 1 мотоцикл, 100 км. Либо нужны дополнительные факторы — например, помощь друзей-мотоциклистов (а вы попробуйте их 49 соберите, и еще уговорите бензин вам по дороге сливать), наличие шланга для сливания бензина и т.д. Проще уж газельку-транспортер нанять, которая бы за вами с мотоциклами ехала — но и туда все 50 не поместятся, максимум 8). Самое реальное — это 2й мотик на гибкую сцепку (а трос для прицепа — этот такой же доп фактор, как и шланг для сливания бензина) и друга на него. В таком случае первый мот проедет примерно 75 км (100 не проедет, т.к. вес стал в 2 раза больше). Задний мот — просто на холостом ходу без газа. Потом вы этот мот припаркуете, пересядите на мот к другу и с ним проедите еще километров 75 (с расчетом того, что он на холостом ходу потерял).

          • Я б сказал что можно проехать 50 км., но в разные стороны с шагом 7 градусов (если мото все в одном месте), итого — 50*50=2500 км. неповторимого пути..

  • 6 вопрос: Сначала берем и ложим на чаши весов по 3 шара, если перевесило, то берем шары из тяжелой чашы и ложим опять на чаши, только уже по одному. Если весы опять перевесило, то соответственно там будет самый тяжелый шар, но если весы остались на одном уровне, то шар самый тяжелый — это оставшийся трейтий.

    • делим 8 шаров на 2 категории > 6 и 2 > взвешиваем 6 шаров (3/3) если они равны то один из 2х шаров кот остались на столе тяжелый, если нет, то из более тяжелой группы берем 2 шара (оставляем один на столе), взвешиваем > если равны то на столе тяжелый.

      • А можно для невнимательных еще раз:)
        Делим на 2 группы: 6 и 2 шара, 3/3 (например 0,7+0,3+0,5=1,5) и (0,5+0,5+0,5=1,5) 2 (0,2+0,2.). Группа 3/3 покажет поровну, то есть самый тяжелый будет 0,2 из 2 группы что не верно.
        Когда мы взвешиваем 6 шаров, мы не учитываем 2 оставшиеся на столе. А если взвешивать 4, то не получится решить таким путем.
        Про мотоциклы лажа — одной жопой точно не уехать)) Или +1 на буксир как писали выше.
        Про шляпы я ни фига не понял: правило работает, если их поровну, 5+5. А если 1+9 то тут как не гадай, 9 человек точно не выживет)

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

    • «называть любые цвета» — в тексте условия «других слов, кроме цвета шляпы, произносить нельзя».

      • каждый называет цвет впереди сидящего? правда одного 50 на 50 съедят

        • не, надо было предполагать цвет только своей шляпы) читы инопланетяне пресекали)

        • Нет, представьте, что цвета шляп распределились так, что они идут по очереди «зеленый — розовый». И что это будет? Каждый говорит тот, что видит впереди, а с его цветом это не совпадает. Все, съели. И только последнему повезет. Он назовет тот цвет, что ему подскажет предпоследний и это будет цвет его шляпы.

          • верно, тут решение одно, называть шляпы одним цветом всем. только половина спасется.

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

    • Совершенно точно. Потерянный кусочек условия — разноцветных шляп ОДИНАКОВОЕ количество (то есть по пять штук).

    • Наиболее рациональное решение(на мой взгляд):
      1. предварительная договоренность, что все называют цвет, озвученный первым;
      2. первый отвечающий, имея возможность увидеть все шляпы впереди сидящих, определяет цвет по большинству.
      Это сохранит жизнь большинству, независимо от расклада(или половине при равном раскладе).

  • в 1 задаче у любого нужно спросить «Другой стражник соврет что у него за спиной дверь к сокровищу?»

    • Вернее, спросить у любого из стражников: «Куда бы меня направил твой сосед, если бы я спросил его где находиться дверь ведущая к сокровищнице?» в любом случаи, говорит стражник правду или лжет, он укажет на дверь ведущую в лабиринт, следовательно выбрать нужно противоположенную…

  • В задаче про мотоциклы не достаточно начальных условий описывающих место положение 50 мотоциклов. А расстояние которое можно проехать на них зависит именно от этих условий. Если предположить, что они находятся на расстоянии в 100 км друг од друга( а условие «у вас есть 50 мотоциклов» не исключает этот вариант), то удастся проехать 5000 км. Вариант ответа завести их все и проехать 100 км абсурден. С таким же успехом можно завести их все и проехать 0 км. Таким образом можно проехать от 0 до 5000 км в зависимости от начального расположения мотоциклов.

    • p^(n-k) — це ймовірність того, що ви виграєте підряд (n-k) разів.
      але ж потрібно ще додати і ймовірність подій, де ви при цьому на якомусь кроці програєте і потім виграєте (і так безліч разів).
      тому повна ймовірність виграшу буде p^(N-K) * sum(p^n * (1-p)^n , n=0 to oo) = p^(N-K)/(1-p+p^2)
      А вже відповідь (тобто ймовірність програшу) — це ймовірність протележної до виграшу події, тобто 1 — …

      • Проблема в том, что при подсчете вероятности выигарша, когда вы учитываете вариант n раз выиграл и n раз проиграл по формуле p^n*(1-p)^n, вы не исключаете того, что может быть n подряд поражений а после n подряд побед, и если n больше имеещегося на тот момент капитала — играть больше вы не сможете. Первое что приходит на ум при решении этой задачи — как то использовать числа Каталана

    • Pпроигр. = (1-p)^K
      т.е. это вероятность вашего проигрыша К-раз.

  • На всякий случай, уточню, что задачки собирала, исходя из отзывов пользователей на Glassdoor и других сайтах, где обсуждают работу, в подборках по типу http://www.impactinterview.com/2009/10/140-google-interview-questions/ (тут кстати есть классическая задача о двух стеклянных шариках и 100-метровом здании, тоже интересная, которую зафейлила решить, но думала включить в подборку, по здравому размышлению, думаю, лучше бы ее привела вместо слишком простой задачи о восьми шариках). Так что приведу в комментариях:

    You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.

  • Если из 50 мотоциклов 25 человек будут везти другие 25 на «буксире» и так далее, то можно проехать 700 км. Этот вариант реальнее и выгоднее, чем 1 человек везет 50 мотоциклов одновременно. Супермен, какой-то.

  • а вот что спрашивают в MS — задачка для дошкольников, Эврика Харьков

  • У второй задачи, ИМХО, есть простое решение: первому надо назвать цвет следующего за ним сидящего. И так по очереди. То есть также 9 из 10 гарантировано выживают, а у первого шансы 5050

    У Эпл очень размытая постановка, остальные вопросы более-менее простые (слабо верится что такие задают в топовых компаниях), кроме Яндекса.

    P.S. Слабо представляю как на собеседованиях задают задачку Эйнштейна — на ее решение в уме в среднем уходит минут 20-25, кто столько ждать будет?:)

    • Ниже уже обсуждали, почему нельзя называть шляпу следующего)

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

        Но в целом и с четным-нечетным решением тоже все довольно просто

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

    • Владислав, Ваш подсчет — 9 из 10 ошибочен! Ваше цепочка разрывается уже на втором, который должен назвать цвет шляпы третьего, а не своей шляпы(у каждого только один ответ). Ему повезет только в случае совпадения цветов.
      Наиболее рациональное решение(на мой взгляд):
      1. предварительная договоренность, что все называют цвет, озвученный первым;
      2. первый отвечающий, имея возможность увидеть все шляпы впереди сидящих, определяет цвет по большинству.
      Это сохранит жизнь большинству(или половине при равном раскладе).

      Что касается задачи Эйнштейна, то я, наверное, тугодум: у меня ушло на нее почти 1.5 часа…

  • Ответ на задачу Альберта Эйнштейна :
    Дом №1 Жёлтый — норвежец — курит Kool — держит лису — пьёт ВОДУ; Дом №2 синий — украинец — курит Chesterfield, держит коня, пьёт чай; Дом №3 красный — англичанин, курит Old Gold, держит улитку, пьёт молоко; Дом №4 белый _ испанец, курит Lucky Strike, держит собаку, пьёт апельсиновый сок; Дом №5 зелёный — японец, курит Parliament, держит ЗЕБРУ, пьёт кофе. Решить в уме не получилось, а таблице элементарно!

  • for #1 question: if there is treasure and here are two doors you say yes.

  • Какого цвета шляпы.. возможный мой ответ — РАЗНЫЕ

  • На мотоциклах можно прехать столько на сколько хватает топлива 100 км..Но можно посмотреть по другому.Можно проехать сколько угодно, нигде не написано что их нельзя дозаправлять.

  • Интереснее задача про бильярдные шары в следующей постановке (было на собеседовании в Microsoft): Имеется 8 шариков одинакового вида и размера. Один шарик отличается от других, только не известно тяжелее он или легче оставшихся шариков. Вопрос: как за 3 взвешивания определить шар, который отличается от других шариков.

  • Ніхто такі дурості не буде питати, якщо в кого є бажання вас вздрючити то вздрючать задачкою по спеціальності. Еппл взагалі задає питання по технологіях.

  • шелдонове питання взагалі елементарне, треба просто гарантувати що брехун візьме участь у відповіді, і перевернути відповідь

  • а шляпи — це хor кольорів шляп попереду, і після того як тіп ззаду називає число яке визначає що за шляпи попереду і всі дізнаються правильна його відповідь чм ні, всі решта дають правильну відповідь

    але хоча до цього і можна додумаьтись в принципі, такі задачі на співбесіді вам не зададуть, основне відповісти на нормальні питання і на питтанна «чому ви обрали еппл?»

  • Ах і забув згадати , що переклад енштенівської задачі бездарний, і бв більшості задач бракує деьалей для однозначності.

  • А задачка про шнурки, 8 кульок і відра — це шкільні олімпіади з математики 3-5 класу в Україні і я б за те щоб звільняти нафіг людей які їх не розв’яжуть

  • Ненавижу не конкретизируемые задачи. 🙂 Для третьего варианта созрело решение, если под «долеко» подразумевается максимальный пробег, ибо не понятно — в одном ли направлении должен двигаться ездок. то находясь с 50ю мотиками в одной точке, можно поехать на 50 км на каждом в одном из 50ти направлений, 50 ибо остальные 50 на обратную дорогу. Итого: 50 км * 50 мотиков = 2500 новых километров.

  • В задаче про мотоциклы выгоднее удалять по одному мотоциклу, а не 50 сразу.
    1. Проезжаем (100/50)=2км. В каждом мотоцикле отстается по 49 литров. Переливаем по литру из одного во все. Имеем снова полные баки.
    2. Проезжаем 100/49, повторяем.

    49. Проезжаем 100/2=50,переливаем в последний мотоцикл.
    50. Проезжаем еще 100 км.
    Итого проедем sum(n=1 to 50, 100/n)=450 км (почти)

    • Про стражников — в условии не сказано, что стражники знают про соседнюю дверь.
      Правильный ответ — спросить у 1го стражника: «ты стражник этих дверей?». У второго спросить: «сокровища за этой дверью?»

      • Это школьная задачка на логику — вопрос задается примерно так «Куда покажет твой сосед если я его спрошу про направление в?»
        Идти надо будет в противоположную сторону. Все.)

  • Придумай задачу сам. Вот примеры моих:
    Грибы это мясо или картошка.
    Почему фрукты сладкие а овощи крахмалистые.
    В каком контексте желтый цвет не вписывается в RGB пространство.
    Как измерить кеш пямяти написав код на C++.
    Фотографируем луну без зума — автоматика экспозиции бесполезна — какую ставим эксп. вручную, такую как фото лица 1) днем 2) на закате или 3) ночью.

  • 1. Задача на пакеты — ответ зависит от выбора временных отрезков. Ровно 9п/с будет достигаться на времени 1сек, 11сек, 111сек и так далее. На промежутках пропускная способность будет отличаться от 9. Оценку приводить не буду, мне лень, потому что пропускная способность в любом случае будет стремиться к 9п/с для t -> к бесконечности. Поточечную сходимость легко показать для любого не более чем счетного разбиения отрезка времени.

    2. Задача на казино: у меня получилось (1-p^(N-K))., где p^(N-K) — вероятность выигрыша. По условию, очевидно что N>K. Но хотелось бы посмотреть решение от человека, который лучше меня шарит в тервере.

  • Курт Гёдель в задаче № 1 сформулировал бы вопрос следующим образом:

    «Правдива ли ложь твоя о сокровище за этой дверью?»

    Не врущий:
    — не может ответить «Да» ни при каких обстоятельствах, т.к. признает факт своей лжи, что недопустимо по условию (ложь не может быть правдой и он не может врать).
    — ответив «Нет» он укажет на ложь лжи (правде) и о сокровище за своей дверью.

    Врущий:
    — не может ответить «Нет» ни при каких обстоятельствах, т.к. признает факт своей правды, что недопустимо по условию (ложь лжи = правда, а он не может говорить правду).
    — ответив «Да» он признает факт правдивости лжи о сокровище за его дверью, указав на другую дверь.

    Вывод:
    — если страж не отвечает: сокровище всегда за противоположной дверью.
    — если страж отвечает «Да»: он — врущий и указывает на другую дверь.
    — если страж отвечает «Нет»: он — не врущий и указывает на свою дверь.

  • 1. Ответ: где дверь со смертельным лабиринтом?

    • тут есть проблема — ты по умалчиванию не знаешь кто врет, а кто нет! Этого нет в описании, поэтому надо спросить у правого
      — честно покажи своей право рукой на дверь где сокровище?
      Если врун тогда левой рукой — если не врет тогда правой, так будет правильно чтобы не задавили дебильные загадки! Суть в противоположности!

  • Apple, Microsoft, Google прошел.
    Постановка задачки от Adobe не корректна. Реальный ответ — 100 км. У Вас нет физической возможности ездить на двух и более мотоциклах одновременно!

  • вопрос про инопланетян. Тупая хрень. Чем эти шапки и выжившие умники влияют на спасение планеты Земля? В задаче нет условия согласно которого выживут все, кроме этой нефартовой десятки))) тупые они там 😉 казалось бы — Apple…

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

    • В первой задаче спросив, сколько будет дважды два, вы узнаете только лжец ли тот, кого вы спросили. А на второй вопрос (есть ли за его дверью сокровище или нет) уже нет разрешения.

  • С ведрами можно и так:
    Наполнить 3 литра — перелить в 5 литров, повторить, в 3 литровом остался литр, вылить 5 литров, долить туда литр, а потом еще 3.

    С мотоциклами — передельное расстояние будет 50 км — как не катайся, вам придется возвращаться обратно на нем — не мешком же идти, или взять канистру или скрутить бензобаки!

  • По первой задаче.
    Сказать одному из охранников: «Покажи за какой дверью сокровища и мы пойдем туда вместе». В таком случае и врун, и правдивый скажут правду.. ) (а кто же откажется от сокровищ? ))

  • N8
    P(0)==1
    P(N)==0

    p==1/2:
    P(K)=1-K/N

    p!=1/2
    A=(1-p)/p
    P(K)=(A^N-A^K)/(A^N-1)

  • «… он — среди 2 оставшихся» — классный ответ, поржал :)))

  • Не увидел ответ на 2 вопрос.

    Кроме слов можно использовать интонацию. Таким образом выживет минимум 9 человек из 10-ти

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

    Первому кто отвечает не повезло) Шансы 50/50

    • Совершенно верно))
      Пришел практически к такому же решению, которое, кстати, не требует даже видеть всю группу, а только впереди сидящего, так что условие задачи можно даже ужесточить: судя по тексту, ее создатели тоже, видимо, не предусматривали такой вариант))
      С одной стороны, это «хитрость», но условия задачи она ни в коей мере не нарушает (можно произносить название цвета немного растянуто или действительно с вопросительной или утвердительной интонацией в зависимости от того, совпадает ли «твой» цвет с цветом впереди сидящего или, как Вы предлагаете, по предварительной договоренности сразу сопоставить этим «особенностям произношения» цвета), и это показывает, что задачу можно решить, если не зацикливаться на стандартных «технических» методах, которыми многие привыкли пользоваться, в т.ч. и «гуманитарию».
      И это решение будет вполне в стиле эппл)) с его Force Touch, скажем))
      Математически же подразумеваемое решение можно увидеть, если выделить пустое место под условием в тексте статьи.

  • apple 2) називати тільки один колір
    adobe радіус можливостей 100 км
    microsoft 1) набрати в 3 вилити в 5, нову нарати в 3 вилити в 5, зал 1, вилити з 5, вилити з 3 в 5, нарати 3 і вилити в 5=4 (л)
    »
    2)поділити пачкою на чотири частини і підпалитипоки не згорить 3/4
    от google взяти 3 кульки на оду сторону, потім 3 на другу, якщо вага рівна, кулька знаходитсь в решті (потім просте зважуваня), якщо ваги переважують, то взяти купку важчу, і з них зважити 2 кульки, якщо вон рівні, то третя, якщо ні, відповідно…

  • с мото похоже все просто: 2 мото в разные стороны = 200 км, дальше никак

  • Что спрашивают в Qualcomm

    Ответ 8,91. Начиная со 2й секунды, 1 пакет идет на повторную передачу предыдущей секунды, и у нас остается 9/10, от которых мы должны отнять 1/10.

  • По 8 у меня получилось: 1 — (p/N)*k

  • Шелдон Купер должен спросить у охранника: -Что бы ты мне сказал, если бы я тебя спросил, какая дверь правильная? /// этот ответ изящнее, однозначно

  • По мотоциклам: 432 км. /// условие поставлено некорректно, невозможно ехать одновременно на 50 мотоциклах.

  • Для Qualcomm: пропускная способность 0.8888888889.
    И не спорьте. Читайте правильно условия.

  • Про Шляпы:
    1й дает прямую подсказку 2му, называя цвет его шляпы, при этом шансы 1го всегда 50 на 50;
    2й, 3й и т.д. должны назвать цвет своей шляпы — озвучить подсказку — особым способом в зависимости от одного из 2х сценариев:
    а.) если подсказка для 2го совпадает с цветом 3го — то 2й дает прямой незамысловатый ответ;
    б.) если подсказка для 2го не совпадает с цветом 3го, тогда 2й дает ответ с «меткой» или «модулированый» ответ, и в таком случае 3й инвертирует «подсказку» 2го в свой правильный ответ, с учетом условий а.) или б.) и т.д. Т.о. 9 гарантировано живы. О «метке» или виде/способе «модуляции» группа должна договориться, либо это разный тон/тональность произношения ответа, разная окраска звука, определенная артикуляция, ударение на 1й или 2й слог, подкашливание, и прочие виды меток либо модуляции.

  • Найпростіший варіант, якщо нема помічників і додаткових засобів:
    їдете на одному мотоциклі, керуючи одною рукою,
    інший тримаєте «на буксирі» іншою рукою.
    Проїжджаєте 50 км, залишаєте буксирований і повертаєтесь назад.
    Берете наступний мотоцикл і так далі.
    Отже маєте 25 мотоциклів з повним баком і один з половиною бака за 50 км від початкової точки.
    Повторюєте процедуру і отримуєте 13 з повним баком за 100 км від початку.
    Знов повторюєте — 6 з повним баком і один з половиною за 150 км.
    Далі 3 з повним баком і один з половиною за 200 км
    (ще один мотоцикл з половиною бака втрачається на 150 км).
    Далі 2 з повним за 250 км.
    І врешті 450 км.
    Поправте, якщо помилився.

  • Не можу знайти чи писали уже в коментарях відповідь на задачу з Яндекса. У мене виходить, що все досить просто: (1-p)^K. Що скажете?

  • По поводу шляп: спасти можно всех, кроме, возможно начинающего. Для этого очевидно, что ответ должен достигать сразу 2 цели: 1)точно назвать свой цвет шляпы; 2) «между строк» дать «закономерный» намек только следующему. Эта четкая выбранная всеми закономерность может быть любая, но, конечно же, одинаковая для всех : н-р, называть свой цвет грустно или весело; тихо или громко; быстро или медленно и т.п. Итак: назвал свой цвет весело — у следующего тот же цвет. Назвал грустно — у следующего «противоположный» цвет. Таким образом, с вероятностью в 50% может погибнуть только первый. Все остальные — спасены ).

  • 🙂 Мне очень интересно, как будет звучать ответ стопроцентного лжеца на вопрос: «А правда ты знаешь, что за твоей дверью сокровища?» в том случае, если сокровища действительно за его дверью. Может быть ответ будет: «Я не знаю, что за моей дверью смертельный лабиринт?» (должна ведь обязательно быть «двойная» ложь)

  • Простите, возможно я не очень дружу с железом. Но меня напрягает вот эта часть условия: «Когда передача неудачная, трансмиттер будет передавать пакет до тех пор, пока не преуспеет.» Разве это не означает априори, что пропускная способность всегда 100%? Разве подвох не в самой постановке?

  • Про мотоциклы херня, можно использовать все топливо и заехать на 390км.

  • А почему во втором вопросе в условии нет информации о том, что именно половина шляп одного цвета? Почему не 1:9 или 2:8?

    • +1. И еще вопрос по этой задаче. Почему в конце сказано «Таким образом гарантированно выживают 9 из 10, а у первого отвечавшего шанс 1 к 1.», ведь выживают все

  • 8 Задача весьма любопытна. Для начала мы предполагаем, что N больше K. Если смотреть на задачу по-простому, то понятно, что может быть несколько случаев (т.е. получаем сумму вероятностей несвязанных событий):
    1) проигрыши идут подряд, тут все просто (1-p)^K
    2) проигрыши чередуются с выигрышами. Тут, чтобы все проиграть, число проигрышей должно превышать число выигрышей на К. Получаем формулу (1-p)^(K плюс M)*p^M, где М — целое количество дополнительных конов, от 1 до бесконечности.
    И тут всплывает последнее, самое интересное условие, о выигрыше. Ведь нужно учесть, что в чередовании выигрышей и проигрышей наш персонаж не наберет заветную сумму N, а это возможно, если разница между количеством выигрышей и проигрышей в любой из моментов достигнет разницы между N и K. Итак, имеем количество выигрышей М и число проигрышей, которое допускает набор суммы N, если его разместить в начале выборки вместе с выигрышами, равное M-(N-K). Теперь нужно определить, сколько существует запрещенных вариантов расположения выигрышей и проигрышей, чтобы знать, сколько вычитать. Воспользуемся формулой числа сочетаний из M плюс (M-(N-K)) по M-(N-K) и получаем (M плюс M-(N-K))!/(M!*(M-(N-K))!) Осталось исключить случаи, когда общее число вариантов для данного М меньше числа запрещенных вариантов, т.е. (K плюс M)!/(К!*М!) должно быть больше, чем (M плюс M-(N-K))!/(M!*(M-(N-K))!)

    Таким образом, получаем формулу (1-p)^K плюс [если (K плюс M)!/(К!*М!) больше (M плюс M-(N-K))!/(M!*(M-(N-K))!)] (1-p)^(K плюс M)*p^M*((K плюс M)!/(К!*М!)-(M плюс M-(N-K))!/(M!*(M-(N-K))!)) плюс …

  • 4. У вас бесконечный запас воды и два ведра — на 5 литров и 3 литра. Вопрос: Как вы отмерите 4 литра?

    Эту задачу мне предлагали на собеседовании (Junior QA), настаивая на поиске нескольких вариантов решения. Решила тремя вариантами.

  • це все круто, але де ж відповіді?

Поиск