Трудные вопросы на собеседовании, hard interview questions Опции

[compiler]

Добрый день!
Итак, один из ресурсов рунета решил опубликовать цикл ”Трудные вопросы на собеседовании” на русском языке. Каждую неделю там будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую преследуют этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений.
Всего 33 вопрса. На англоязычном оригинали есть уже все ответы, но найти и посмотреть не спортивно, имхо... Русскоязычный аналог начал публикации 2.06. Перевод от Скакунова Александра.
В общем почему бы не продублировать цикл здесь?

Задача #1

Есть две деревни: деревня магов и деревня гномов. Раз в год маги проходят по деревне гномов и выстраивают их по росту в возрастающем порядке, так что каждый гном может видеть только тех, кто ниже его самого.

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

Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет).

Какой стратегии должны придерживаться гномы, чтобы минимизировать количество убиенных гномов?

Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии?

В атаче задание на ангельском.
Источники(русскоязычный и англоязычный), приложены из-за моральных соображений, просьба не смотреть..

Спойлер (Показать/Скрыть)

http://www.developers.org.ua/archives/a4/2...ew-questions-1/
http://everything2.com/title/hard%2520inte...w%2520questions

Говорю сразу, я ответы не смотрел да и нет их еще на русском, а мой английский не тот)... в любом случае, пытаемся ответить сами!

Сообщение отредактировано: compiler - 6.06.2008 1:46

[klem4]

Спойлер (Показать/Скрыть)

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

ps идея хорошая, если можешь выкладывай задачи дальше.

[compiler]

мое решение:

Спойлер (Показать/Скрыть)

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

ps идея хорошая, если можешь выкладывай задачи дальше.

будут читать - буду выкладывать, ну и конечно, если Скакунов будет продолжать переводить..

Сообщение отредактировано: compiler - 6.06.2008 2:22

[andriano]

Спойлер (Показать/Скрыть)

Разбиваются на пары, один из пары (кто стоит сзади) называет цвет шляпы другого.
Очевидно, минимум половина выживает (в худшем случае), матожидание выживших - 75%.

[compiler]

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

[Michael_Rybak]

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

[compiler]

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

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

[мисс_граффити]

Спойлер (Показать/Скрыть)

считаем белый истиной, черный - ложью (можно наоборот... не принципиально)

самый высокий гном высчитывает "исключающее или" (xor) всех шапок, которые перед ним. вероятность, что этот цвет совпадет с его цветом - 50%.
То есть с вероятностью 50% выживут все, а если не получится - выживут (все-1)

[compiler]

Прошу прощение за задержку.. были проблемы с сетью + экзамены. Вобщем Вот решение в переводе того же Скакунова..

Спойлер (Показать/Скрыть)

У гномов есть стратегия, которая будет стоить жизни максимум одному из них.

Пусть черные шляпы обозначают единицы, а белые - нули. Каждый гном вычисляет сумму по модулю 2 шляп перед ним. Первый (самый высокий гном) объявляет цвет, согласно сумме, им посчитанной. Он может быть убит либо нет (зависит от его удачливости… конечно, маги всегда могут подстроить так, что он умрет в любом случае, т.к. они знают, что используется оптимальная стратегия).

Следующий гном сравнивает сумму, посчитанную им, с суммой, сказанной самым высоким гномом. Если суммы совпадают, сие означает, что его шляпа белая, иначе - черная. Он объявляет свой цвет и выживает.

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

Итак, только самый первый (и самый высокий) гном погибает… что, на мой взгляд, объясняет, почему гномы такие низенькие.

оригинальное решение( by jliszka )

Спойлер (Показать/Скрыть)

The dwarves have a strategy that will cost the life of at most one dwarf. If you want to know what this strategy is, read on.

Let black hats signify 1's and white hats signify 0's. Each dwarf calculates the parity (sum modulo 2) of the hats in front of him. The first (tallest) dwarf announces the color corresponding to the parity he calculated. He may or may not be killed (depending on his luck... of course the Wizards can always engineer it so he dies, because they know this is the optimal strategy).

The next dwarf compares the parity he calculated and the parity the first dwarf announced. If the two parities are the same, that means his hat is white, otherwise it is black. He announces this color, and lives.

Each successive dwarf, armed with the original parity of all but the first dwarf and the colors of the hats of all the preceding dwarves (but the first), can easily calculate the color of his own hat. An inductive proof of correctness is pretty easy.

Thus only the first (and tallest) dwarf dies... which I guess explains why dwarves are so short.

Чесно говоря, я его не понял( Может кто объяснит?

Для следующий задачи создам следующую тему ( Re:Трудные вопросы на собеседовании ), куда буду помещать все четные задания, а в этой теме неделя для обсуждения решения..

Сообщение отредактировано: compiler - 12.06.2008 22:41

[andriano]

Не понял чего?
Если английский текст, то по-русски написано то же самое.
Если же алгоритма, то по сути он не отличается от того, что предложила мисс граффити.

[compiler]

отредактированнно.. проблема с алгоритмом.. подумаю еще сам.. может что-то не так понял..

Сообщение отредактировано: compiler - 13.06.2008 2:01

[мисс_граффити]

То же самое, только наоборот )) У них черные единицы, белые нули.

[compiler]

Так и не понял ;(
Объясните пожалуйста на конкретной последовательности..

[compiler]

Задача #3

Как вы обернете порядок слов (не символов) в строке длиной n при постоянном объеме дополнительной памяти (constant extra space) за линейное время (linear time)?

[мисс_граффити]

про первую задачу.
допустим, у нас 5 гномов.
им надели колпаки и построили в такой ряд:
ч ч б ч б
то есть
1 1 0 1 0
последний гном считает
1 xor 1 xor 0 xor 1 = 1
говорит: черный
его убивают (не повезло).

предпоследний получает такую задачу:
1 xor 1 xor 0 xor х = 1
(х - его шляпа. цвет неизвестен ему)
находит, что х=1 (черный).

третий гном:
1 xor 1 xor х xor 1 = 1
находит, что х=0

так же поступают оставшиеся гномы

[compiler]

про первую задачу...

спасибо.. понял..