IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Трудные вопросы на собеседовании, hard interview questions
сообщение
Сообщение #1


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


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

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

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

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

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

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

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

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


Прикрепленные файлы
Прикрепленный файл  01.txt ( 779 байт ) Кол-во скачиваний: 242


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


мое решение:
Спойлер (Показать/Скрыть)

Цитата(klem4 @ 5.06.2008 21:53) *
ps идея хорошая, если можешь выкладывай задачи дальше.
будут читать - буду выкладывать, ну и конечно, если Скакунов будет продолжать переводить..

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


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


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


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


скрытый ответ, думаю, можно постить сразу. идея хорошая. задача - боян smile.gif ждем еще.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Цитата(Michael_Rybak @ 6.06.2008 15:05) *
скрытый ответ, думаю, можно постить сразу. идея хорошая. задача - боян smile.gif ждем еще.
ну.. Постить сразу ответ, можно только если он есть на русском(мой перевод врядли кого устроит))), а на русскоязычном сайте выкладывают решение через неделю после условия(можно конечно дать им фору и брать уже с решением). А так, если очень не терпиться, есть ссылка на оригинал, есть гугл.. + если я буду выкладывать с решением, то сам буду его знать(
Насчет бояна, на англ. сайти задачи датированы 2001 годом, и это не значит что они не появились раньше, поэтому.. Но, надеюсь, следующии будут менее известны)


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


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


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

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

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


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

Репутация: -  28  +


Не понял чего?
Если английский текст, то по-русски написано то же самое.
Если же алгоритма, то по сути он не отличается от того, что предложила мисс граффити.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


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

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


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


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


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Цитата
Задача #3

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



Прикрепленные файлы
Прикрепленный файл  03.txt ( 131 байт ) Кол-во скачиваний: 228


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Цитата(мисс_граффити @ 17.06.2008 1:57) *
про первую задачу...
спасибо.. понял.. give_rose.gif


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 27.01.2021 2:13
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name