Трудные вопросы на собеседовании, hard interview questions |
Трудные вопросы на собеседовании, hard interview questions |
compiler |
5.06.2008 21:08
Сообщение
#1
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
Добрый день!
Итак, один из ресурсов рунета решил опубликовать цикл ”Трудные вопросы на собеседовании” на русском языке. Каждую неделю там будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую преследуют этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений. Всего 33 вопрса. На англоязычном оригинали есть уже все ответы, но найти и посмотреть не спортивно, имхо... Русскоязычный аналог начал публикации 2.06. Перевод от Скакунова Александра. В общем почему бы не продублировать цикл здесь? Цитата Задача #1 Есть две деревни: деревня магов и деревня гномов. Раз в год маги проходят по деревне гномов и выстраивают их по росту в возрастающем порядке, так что каждый гном может видеть только тех, кто ниже его самого. У магов неограниченное количество чёрных и белых шляп. Они одевают белую или черную шляпу на голову каждого гнома. Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет). Какой стратегии должны придерживаться гномы, чтобы минимизировать количество убиенных гномов? Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии? В атаче задание на ангельском. Источники(русскоязычный и англоязычный), приложены из-за моральных соображений, просьба не смотреть.. Спойлер (Показать/Скрыть)
Говорю сразу, я ответы не смотрел да и нет их еще на русском, а мой английский не тот)... в любом случае, пытаемся ответить сами! Сообщение отредактировано: compiler - 5.06.2008 21:46 Прикрепленные файлы 01.txt ( 779 байт ) Кол-во скачиваний: 287 -------------------- Спасибо!
Удачи! |
klem4 |
5.06.2008 21:53
Сообщение
#2
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Спойлер (Показать/Скрыть)
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
compiler |
5.06.2008 22:22
Сообщение
#3
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
мое решение:
Спойлер (Показать/Скрыть)
ps идея хорошая, если можешь выкладывай задачи дальше. будут читать - буду выкладывать, ну и конечно, если Скакунов будет продолжать переводить..Сообщение отредактировано: compiler - 5.06.2008 22:22 -------------------- Спасибо!
Удачи! |
andriano |
6.06.2008 11:39
Сообщение
#4
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Спойлер (Показать/Скрыть)
|
compiler |
6.06.2008 14:00
Сообщение
#5
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
И вот еще вопрос по оформлению темы, стоит ли скрывать ответ, или оставлять его доступным способствуя обсуждению предложеных вариантов, а скрывать только заведомо правильный ответ?
-------------------- Спасибо!
Удачи! |
Michael_Rybak |
6.06.2008 15:05
Сообщение
#6
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
скрытый ответ, думаю, можно постить сразу. идея хорошая. задача - боян ждем еще.
|
compiler |
6.06.2008 15:24
Сообщение
#7
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
скрытый ответ, думаю, можно постить сразу. идея хорошая. задача - боян ждем еще. ну.. Постить сразу ответ, можно только если он есть на русском(мой перевод врядли кого устроит))), а на русскоязычном сайте выкладывают решение через неделю после условия(можно конечно дать им фору и брать уже с решением). А так, если очень не терпиться, есть ссылка на оригинал, есть гугл.. + если я буду выкладывать с решением, то сам буду его знать(Насчет бояна, на англ. сайти задачи датированы 2001 годом, и это не значит что они не появились раньше, поэтому.. Но, надеюсь, следующии будут менее известны) -------------------- Спасибо!
Удачи! |
мисс_граффити |
9.06.2008 1:01
Сообщение
#8
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
Спойлер (Показать/Скрыть)
-------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
compiler |
12.06.2008 18:29
Сообщение
#9
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
Прошу прощение за задержку.. были проблемы с сетью + экзамены. Вобщем Вот решение в переводе того же Скакунова..
Спойлер (Показать/Скрыть)
Спойлер (Показать/Скрыть)
Чесно говоря, я его не понял( Может кто объяснит? Для следующий задачи создам следующую тему ( Re:Трудные вопросы на собеседовании ), куда буду помещать все четные задания, а в этой теме неделя для обсуждения решения.. Сообщение отредактировано: compiler - 12.06.2008 18:41 -------------------- Спасибо!
Удачи! |
andriano |
12.06.2008 19:49
Сообщение
#10
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Не понял чего?
Если английский текст, то по-русски написано то же самое. Если же алгоритма, то по сути он не отличается от того, что предложила мисс граффити. |
compiler |
12.06.2008 20:09
Сообщение
#11
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
отредактированнно.. проблема с алгоритмом.. подумаю еще сам.. может что-то не так понял..
Сообщение отредактировано: compiler - 12.06.2008 22:01 -------------------- Спасибо!
Удачи! |
мисс_граффити |
13.06.2008 2:53
Сообщение
#12
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
То же самое, только наоборот )) У них черные единицы, белые нули.
-------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
compiler |
13.06.2008 9:59
Сообщение
#13
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
Так и не понял ;(
Объясните пожалуйста на конкретной последовательности.. -------------------- Спасибо!
Удачи! |
compiler |
16.06.2008 18:42
Сообщение
#14
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
Цитата Задача #3 Как вы обернете порядок слов (не символов) в строке длиной n при постоянном объеме дополнительной памяти (constant extra space) за линейное время (linear time)? Прикрепленные файлы 03.txt ( 131 байт ) Кол-во скачиваний: 257 -------------------- Спасибо!
Удачи! |
мисс_граффити |
17.06.2008 1:57
Сообщение
#15
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
про первую задачу.
допустим, у нас 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 |
17.06.2008 11:18
Сообщение
#16
|
Человек Группа: Пользователи Сообщений: 1 050 Пол: Мужской Реальное имя: Станислав Репутация: 3 |
-------------------- Спасибо!
Удачи! |
Текстовая версия | 13.06.2024 6:36 |