Выпуск#16: ITренировка — актуальные вопросы и задачи от ведущих компаний

[eandr_67]

Вопрос 1

Всего существует 2 ** 3 = 8 вариантов движения муравьёв. Муравьи не столкнутся, если движутся в одну сторону — 2 варианта из 8.
Ответ: (8 — 2) / 8 = 0.75

[hokeroid]

Муравьи

Всего комбинаций 8, не столкнутся в 2, когда идут в одну сторону. Шанс 3/4

Шляпы

Раздам номера от 1 до 3 игрокам. Пусть, если на игроке 3 красная шляпа, первым спасует игрок 1, иначе игрок 2. Тогда игрок 3 знает цвет своей шляпы, отвечает, а оставшийся пасует. Шанс победы 100%

[Readme]

Шляпы

Ответы всех игроков записываются, но не показываются другим игрокам, до того момента, пока все не ответят

Тайминг-атака не пройдёт :)

[hokeroid]

Шляпы

В условии задачи не написано, что я не вижу что другой игрок дал ответ. Сказано лишь то, что я не вижу какой.

[Rsa97]

Вопрос 1

Муравьи не столкнутся, если двигаются в одну и ту же сторону — по часовой стрелке или против. Вероятности таких событий P₁^CW × P₂^CW × P₃^CW и P₁^CCW × P₂^CCW × P₃^CCW.
Значит вероятность столкновения P = 1 − P₁^CW × P₂^CW × P₃^CW − P₁^CCW × P₂^CCW × P₃^CCW.
Если направления движения выбираются равновероятно, то P = 1 − (1/2)³ − (1/2)³ = 3/4

Вопрос 2

Тут всё зависит от того, могут ли игроки подавать друг-другу какие-либо сигналы. Если да, то игрок, видящий на других шляпы одного цвета подаёт такой сигнал (например, первым пишет ответ 'pass'). Тогда два других игрока знают, что их шляпы одного цвета и могут правильно ответить.

[mbait]

Есть некоторые сомнения относительно того, что эти вопросы задают в Гугле. "Alient Language" — задача с квалификационного раунда Google Code Jam 2009, а пул задач обычно держится в относительном секрете, и задачи, получившие определённую популярность или будучи замеченными на публичных ресурсах, из пула удаляются. Задачи про муравьёв или шапки и вовсе не задаются уже очень давно.

[reci]

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

Сами же по себе задачи мне показались довольно любопытными.

[Vadimirk]

Муравьи.
75% шанс столкновения, т.к.только в 2 случаях из 8 все муравьи начинают двигаться в одну и ту же сторону.

Шляпы
Игроки дают ответ в зависимости от цветов шляп игроков, которых они видят перед собой. Если перед игроком дающим ответ, двое других с разными шляпами, он пасует, поскольку шанс угадать всего 50% и это покрывает большую часть из возможных позиций. Если отвечающий видит перед собой игроков с 2-мя одинаковыми шляпами синими или красными, то он называет противоположный цвет. Поскольку для каждого цвета возможны всего 3 подобные позиции, шанс на выигрыш уже 66.67%.

[Rsa97]

Давайте посмотрим возможные комбинации и ответы игроков по вашей системе"

Комбинации

K-K-K => С-С-С, проигрыш
K-K-C => X-X-C, выигрыш
K-C-K => X-C-X, выигрыш
K-C-C => К-X-X, выигрыш
C-K-K => С-X-X, выигрыш
C-K-C => X-К-X, выигрыш
C-C-K => X-X-K, выигрыш
C-C-C => K-K-K, проигрыш

Вероятность выпадения каждой комбинации одна и та же, выигрыш идёт в 6 случаях из 8, то есть его вероятность 75%.

[Vadimirk]

Да, я уже понял, что ошибся, не все комбинации взял в учёт :)

[Art_ta]

1 вопрос муравьи — 75% вероятность столкновения.
2 вопрос шляпа — тактика на 100% — заранее договариваются: кто видит одинаковые шляпы — отвечает, кто разные — пасует. Получается кто видит синие, на нем — красная, кто видит красные — на нем синяя. Кто видит красную и синюю — на нем или красная или синяя — надо пасовать)

[Vadimirk]

Учитывай, что если ты видишь 2 одинаковые Шляпы, на тебе может быть так же шляпа этого цвета с вероятностью 33.3%

[Art_ta]

Там же в вопросе условие — «правильная монета». Значит из 3-х раз не может выпасть 3 в пользу одного и того же цвета.

[Vadimirk]

Правильная момента подразумевает её верную физическую форму и прочие данные, то есть шанс выпадения того или иного результата ровно 1/2. Причем тут количество этих самых результатов?

[Art_ta]

Вот, вот — 1/2, а не 1/3 :)

[Art_ta]

1/2 это значит, если первая — синяя, то вторая — красная, а третья — или синяя или красная!

[Vadimirk]

Точняк!

[apapacy]

Тактика на 75%. Обратите внимание что ответы скрываются пока не ответили все игроки. То есть стратегия не сработает если были все шляпы одинакового цвета или в двух случаях из восьми.

[Art_ta]

все шляпы одинакового цвета быть не могут, потому что вероятность правильной монеты 1 к 2, в не 3 к 3. И 8 случаев быть не может, потому что игроков трое )))

[apapacy]

Восемь это два в степени три (потому что игроков трое).
Почему все шляпы не могут быть одинакового цвета?
Давайте начнем так
Если один игрок то вероятностью 1 у него шляпа одного цвета.
Если игрока два то будет четыре варианта цветов равновероятных из них благоприятных два. То есть с вероятностью 0.5 на игроках будут шляпы одинакового цвета, потому что монета правильная. В этом правильная монета отличается от правильного бутерброда для которого вероятность 1.
Если игроков три то вариантов равновероятных будет 8 из них неблагоприятных по прежднему два (все синие все красные).

[Art_ta]

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

[apapacy]

Давайте уйдем от тонкостей перевода и скажем термин как в условии fair coin.
Это монета которая в одном независимом испытании даст равную вероятность событий и все. Никакой мистики, никакой способности предугадывать последующие события и количество подбрасываний, никакой памяти монета не имеет. Каждое из подбрасываний является независимым и не исключает ни одного из событий.

[Art_ta]

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

[Rsa97]

en.wikipedia.org/wiki/Fair_coin

In probability theory and statistics, a sequence of independent Bernoulli trials with probability 1/2 of success on each trial is metaphorically called a fair coin.

Сказано, что в каждом испытании вероятность успеха равняется 1/2. Где здесь вы увидели одинаковое количество выпадений?

[apapacy]

Там написано то же что и я Вам сказал выше: идеальная монета при бросании имеет равную вероятность выпадания орла или решки 0,5+0,5. В отличии от реальной монеты результат бросания который зависит от ее реальных параметров и может быть например 0,4 + 0,6.

При двух подряд испытаниях не гарантируется выпадание с вероятностью 100% разных результатов.

[Art_ta]

Возможно Вы и правы, а может — я. Посмотрим ответы через неделю.

[hokeroid]

Правильная монета — монета, у которой предел отношения количества выпавших орлов на количество бросков в бесконечности равен 1/2

[Art_ta]

Хорошо. Убедили.Тактика на 75%.

[alex_nightingale]

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

[Art_ta]

Про правильный бутерброд — это точно!!! )))

[Yeah]

Муравьи

50% — или встретятся или не встретятся

[apapacy]

Хотелось бы узнать ваше обоснование

[hokeroid]

Обоснованием является рофл)

[Rsa97]

Эта задача может не иметь однозначного решения. Например, по словарю 'аб', 'в' невозможно судить о взаимном порядке букв 'б' и 'в'.

[kardan2]

На этой неделе я пас.

[Rsa97]

Задача 3

Можно решить через матрицу предшествия. Заводим словарь предшественников для каждой буквы. Берём слова, начиная со второго, находим совпадающие начала в предыдущих словах и по первым несовпадающим буквам добавляем в словарь для буквы текущего слова букву из предшествующего.
Пройдя по всем словам ищем буквы, у которых нет предшественников (пустые словари), выводим их в произвольном порядке. Удаляем эти буквы из всех словарей предшествия и из общего списка. Повторяем, пока в списке есть буквы.
{«baa», «abcd», «abca», «cab», «cad»}
'b' => {}
'a' => {'b', 'd'}
'c' => {'b', 'a'}
'd' => {'b'}
Ответ: {'b', 'd', 'a', 'c'}

[smer44]

Задача 1. — там по примерам почти видно.
до семи символов выигрывают просто А
потом после трёх А идёт комбинация ctrl+a, ctrl+c, ctrl+v, ctrl+v, пока эти 4 символа влезут в остаток, или же в остаток влезает просто ctrl+a, ctrl+c, ctrl+v иначе остаток заполняется несколькими ctrl+v

Задача 3. — я бы просто конструировал дерево поиска, и в него кидал бы буквы из расчёта между какими буквами новую вставлять.

Задача 2. — бессмысленный вырвиглаз, решаемый перебором

[apapacy]

По первой задаче пример решение кажется неверный для 11.
Заметим что для 6 есть два равнозначны варианта аааааа и ааа сa cc cv
Для 11 aaa ca cc cv ca cc cv cv cv то есть 36 не 27
То есть алгоритм такой с кратными 3 действуем тройками ааа са сс cv ca cc cv
Если некратно то заполняем последние один или два нажатия cc

[Igor_gg]

Для Вашей последовательности ответ будет 24 а не 36

[apapacy]

Да действительно ошибся

[Nick_mentat]

1

1/4: выкидываем первого муравья — от его решения ничего не зависит, в силу симметрии задачи. Куда бы он не двинулся, смотрим на муравья, в угол которого он двинулся. Он может пойти навстречу, и тогда точно столкнется, значит -50%. Если же он всё-таки пойдёт в другую сторону, то третий муравей также может пойти ему на встречу с вероятностью 50%, а 50% от 100%-%50 — это -25%. Значит ответ 100%-50%-25% = 25%

2

Шляпы не так просты как кажутся. Раз уж они заинтересовны в кооперации, то наверное стоит сообщать друг-другу инфу фактом написания, или не написания какого-либо варианта. Пускай есть один Избранный, который либо сразу же пишет пас, если видит одинаковые шляпы, либо пишет тот же пас, но после того как другие напишут свой цвет. Двое других всегда ответят правильно. Если же игра каким-то образом запрещает такие стратегии (хотя в условии ничего не сказано об этом) то они должны исходить только из того, какие шапки видят. Тут больше 75% они не выжмут, как мне кажется. Пример такой стратегии: видишь одинаковые — пиши противоположный цвет, видишь разные — пиши пас.