Задачи для IT интервью

[Pantigalt]

можете считать, что в момент 0 Программист находится в центральной комнате, а Вор - где-то в туннелях.

Так если нужно _гарантированно_, скорость не имеет значения. Имеет значение только, видит ли сейчас программист вора. Чтобы гарантированно видеть нужно, чтобы длина каждого туннеля была не больше видимости, т.е. 10м.
Но я подозреваю, что я чего-то не понял.

Подсказываю: программист может начать проверять один туннель за другим.

Программисту надо вернуться до того как вор успел выйти из туннеля.
То есть он видит 10м каждого из 3 туннелей.
Он может пройти 10 метров, увидеть еще 10 метров и вернуться обратно.
То есть мой ответ 20м.

[Berlaga]

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

Можно и длиннее.

[Berlaga]

можете считать, что в момент 0 Программист находится в центральной комнате, а Вор - где-то в туннелях.

Так если нужно _гарантированно_, скорость не имеет значения. Имеет значение только, видит ли сейчас программист вора. Чтобы гарантированно видеть нужно, чтобы длина каждого туннеля была не больше видимости, т.е. 10м.
Но я подозреваю, что я чего-то не понял.

Подсказываю: программист может начать проверять один туннель за другим.

Программисту надо вернуться до того как вор успел выйти из туннеля.
То есть он видит 10м каждого из 3 туннелей.
Он может пройти 10 метров, увидеть еще 10 метров и вернуться обратно.
То есть мой ответ 20м.

Близко! но можно еще лучше.

[M. Ridcully]

У меня чуток побольше - 25 получилось. Если скорость в 2 раза больше, то к тому моменту, как вор дойдёт до комнаты, программист пройдёт в другом туннеле 15 (увидит на 25) и ещё вернётся на 5, чтобы на всякий случай увидеть вора в комнате.

[Berlaga]

У меня чуток побольше - 25 получилось. Если скорость в 2 раза больше, то к тому моменту, как вор дойдёт до комнаты, программист пройдёт в другом туннеле 15 (увидит на 25) и ещё вернётся на 5, чтобы на всякий случай увидеть вора в комнате.

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

Смотрите. П стоит в центре, если он не видит В - то В как минимум в 10м от центра. П уходит в туннель, проходит 20м (видит на 30), В тем временем проходит 10м до центра и уходит в другой туннель. П возвращается назад, т.е. проходит 20м и видит В на расстоянии не более 10м в одном из туннелей. Если П не видит В - значит В остался в том же туннеле, что и был. Итого гарантировано за 3 проверки П поймает В. Логично?

[M. Ridcully]

Смотрите. П стоит в центре, если он не видит В - то В как минимум в 10м от центра. П уходит в туннель, проходит 20м (видит на 30)...

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

[Berlaga]

Смотрите. П стоит в центре, если он не видит В - то В как минимум в 10м от центра. П уходит в туннель, проходит 20м (видит на 30)...

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

Не увидит сразу. Но после того, как П вернется в центр - В не успеет убежать дальше, чем на 10м. И П его увидит.

[M. Ridcully]

Да, похоже.

[Pantigalt]

У меня чуток побольше - 25 получилось. Если скорость в 2 раза больше, то к тому моменту, как вор дойдёт до комнаты, программист пройдёт в другом туннеле 15 (увидит на 25) и ещё вернётся на 5, чтобы на всякий случай увидеть вора в комнате.

Ну это совсем другие условия, откуда предположение что вор попав в комнату сразу станет виден из тоннеля.
Попав в комнату он может свалить из пещеры так что бедный программист из тоннеля его не заметит.

[Berlaga]

Вот еще задачка:

Есть 1000 пронумерованных конвертов, от 1 до 1000. В одном конверте лежат дэнги! в остальных - пусто. Ваша задача - назвать номер конверта с дэнгами! Вам в помощь есть некий Знаток, который знает точно где что лежит. Вы можете послать Знатоку несколько записок с вопросами. Знаток может отвечать только "да" или "нет", если вопрос поставлен так, что он не может ответить - то на этом все заканчивается, дэнэг! вам не дадут. Перед тем, как ответить - Знаток перемешивает ваши записки, тусует их как колоду карт. Потом отвечает на вопросы по одному, но не оглашая сам вопрос вслух. Вы слышить только его ответы. Ответы честные, можно доверять.

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

[M. Ridcully]

Ну если в пределах 10м то должен увидеть, по условию.
Предполагается "сферичность" программиста, как я понимаю.
Иначе "не заметить" и с 2х метром можно, мало ли что...

[M. Ridcully]

Вот еще задачка:

А конверты тоже как колода лежат - то есть упорядочены? Если да, то бинарный поиск, 10 вопросов.
Но это в-принципе типовая задача.

[Pantigalt]

Вот еще задачка:

Есть 1000 пронумерованных конвертов, от 1 до 1000. В одном конверте лежат дэнги! в остальных - пусто. Ваша задача - назвать номер конверта с дэнгами! Вам в помощь есть некий Знаток, который знает точно где что лежит. Вы можете послать Знатоку несколько записок с вопросами. Знаток может отвечать только "да" или "нет", если вопрос поставлен так, что он не может ответить - то на этом все заканчивается, дэнэг! вам не дадут. Перед тем, как ответить - Знаток перемешивает ваши записки, тусует их как колоду карт. Потом отвечает на вопросы по одному, но не оглашая сам вопрос вслух. Вы слышить только его ответы. Ответы честные, можно доверять.

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

Задача на бинарный поиск. 10 записок.

[Berlaga]

Вот еще задачка:

А конверты тоже как колода лежат - то есть упорядочены? Если да, то бинарный поиск, 10 вопросов.
Но это в-принципе типовая задача.

Конверты пронумерованы.

Значит, 10... Ну давайте обсудим. Какие именно вопросы вы напишите?

[M. Ridcully]

Стоп, момент перемешивания записок я пропустил...

[M. Ridcully]

А ну пофиг, всё равно 10, нужно спрашивать, установлен ли бит N в номере выигрышного конверта.

[Berlaga]

А ну пофиг, всё равно 10, нужно спрашивать, установлен ли бит N в номере выигрышного конверта.

Так какие вопросы-то?

[M. Ridcully]

1 Установлен ли бит 0 в номере выигрышного конверта?
2 Установлен ли бит 1 в номере выигрышного конверта?
3 Установлен ли бит 2 в номере выигрышного конверта?
4 Установлен ли бит 3 в номере выигрышного конверта?
...
10 Установлен ли бит 9 в номере выигрышного конверта?

[Berlaga]

1 Установлен ли бит 0 в номере выигрышного конверта?
2 Установлен ли бит 1 в номере выигрышного конверта?
3 Установлен ли бит 2 в номере выигрышного конверта?
4 Установлен ли бит 3 в номере выигрышного конверта?
...
10 Установлен ли бит 9 в номере выигрышного конверта?

Потом отвечает на вопросы по одному, но не оглашая сам вопрос вслух. Вы слышить только его ответы

Ну и услышите вы "да, да, нет, да, нет,...., нет". Дальше что будете делать?

[M. Ridcully]

Блин, теперь пропустил момент, что вопросы не читаются...

[Berlaga]

Вы на верном пути. Осталось совсем ерунда!

[M. Ridcully]

Установлен ли бит <номер вопроса> в номере выигрышного конверта?

[Berlaga]

Установлен ли бит <номер вопроса> в номере выигрышного конверта?

Бинго! Можно и чуть четче сформулировать, но смысл ясен.

ОК, вижу что это хорошая задачка. Не сложная, но и подумать чуток надо. Про Вора, наверное, тяжеловата для интервью.

[Мальчик-Одуванчик]

Когда-то давно-давно... еще в той жизни... я работал в месте с "четко сформулированными задачами"... Сторожем подрабатывал, по студенчеству.
А потом я выучился и стал софтверным инженером.

В институте вахтером?

[FreemanUSA]

Какие-то задачки мрачные во попробуйте http://www.playcast.ru/view/819459/439f ... 9de73291pl в японии пользуют, слышал, если кто пробывал до этого пальцы не гните, а скажите время до решения, у меня 10 минут заняло "без Ютуба"
20 метров наверное плюсь погрешность в 1 мм (так как В не поместиться в 1 мм) болле точный ответ так как П пролитит 10 метров до середины тунеля и остальные увидет, за это время В может пробежать 5 метров и если он сохранит движение то встретиться с П или опять уйдёт в глубь.