В новый выпуск ITренировки вошли задачи от «синего гиганта», компании IBM.
В этой компании, с богатым историческим прошлым, тоже задают логические задачи на собеседованиях. Некоторые из них, самые интересные на наш взгляд, мы включили в подборку. Под катом Вас ждут задачи для соискателей, как обычно — не только простые, но и требующие размышления.
Tile Stacking Tower
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
В этой компании, с богатым историческим прошлым, тоже задают логические задачи на собеседованиях. Некоторые из них, самые интересные на наш взгляд, мы включили в подборку. Под катом Вас ждут задачи для соискателей, как обычно — не только простые, но и требующие размышления.
Вопросы
- Chickens
A farmer sold a few chickens to four different customers on a particular day. It was such that each customer purchased half of the remaining chickens and a half chicken more.
Can you find out how many chicken were sold by the farmer on that day if we tell you that the fourth customer bought a single chicken ?
ПереводЗа один день фермер продал несколько цыплят четырем покупателям. Так вышло, что каждый из них купил половину остававшихся цыплят и ещё полцыплёнка.
Можете ли Вы сказать, сколько цыплят было продано в этот день, если известно, что 4-ый покупатель купил целого цыпленка?
- Bullets and revolver
A Russian gangster kidnaps you. He puts two bullets in consecutive order in an empty six-round revolver, spins it, points it at your head and shoots. *click* You’re still alive. He then asks you, “do you want me to spin it again and fire or pull the trigger again right away?” For each option, what is the probability that you’ll be shot?
ПереводВас похитил русский бандит (ох уж эти стереотипы!). Он последовательно вставил 2 пули в шестизарядный револьвер, прокрутил барабан, прицелился Вам в голову и спустил курок. *щёлк*. Вы всё ещё живы. Бандит спросил Вас — «Вы желаете, чтобы я прокрутил ещё раз и выстрелил, или выстрелил немедленно?». Какова вероятность быть застреленным в каждом случае?
Задачи
- Sort a stack using recursion
Given a stack, the task is to sort it using recursion. Use of any loop constructs like while, for..etc is not allowed. We can only use the following ADT functions on Stack S:
is_empty(S): Tests whether stack is empty or not.
push(S): Adds new element to the stack.
pop(S): Removes top element from the stack.
top(S): Returns value of the top element. Note that this function does not remove element from the stack.
Example:
Input: -3 < — Top
14
18
-5
30
Output: 30 < — Top
18
14
-3
-5
ПереводДан стек, задача — отсортировать его с помощью рекурсии. Использование циклических конструкций, вроде while, for… и др. запрещено. Позволено использовать только следующие абстракные команды на стеке S:
is_empty(S): Проверяет, пуст ли стек.
push(S): Добавляет новый элемент в стек.
pop(S): Снимает верхий элемент стека.
top(S): Возвращает значение верхнего элемента. Обратите внимание, что элемент не удаляется при этом.
Примеры:
Вход: -3 < — Вершина стека
14
18
-5
30
Выход: 30 < — Вершина стека
18
14
-3
-5
Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
Consider the following dictionary
{ i, like, sam, sung, samsung, mobile, ice,
cream, icecream, man, go, mango}
Input: ilike
Output: Yes
The string can be segmented as «i like».
Input: ilikesamsung
Output: Yes
The string can be segmented as «i like samsung»
or «i like sam sung».
Перевод
Дана входная строка и словарь. Напишите программу для нахождения, может ли быть строка разбита на последовательность слов из словаря. Примеры:
Дан следующий словарь:
{ i, like, sam, sung, samsung, mobile, ice,
cream, icecream, man, go, mango}
Строка: ilike
Выход: Да. Строка может быть разбита на «i like».
Строка: ilikesamsung
Output: Да. Строка может быть разбита на «i like samsung» или «i like sam sung».
Дан следующий словарь:
{ i, like, sam, sung, samsung, mobile, ice,
cream, icecream, man, go, mango}
Строка: ilike
Выход: Да. Строка может быть разбита на «i like».
Строка: ilikesamsung
Output: Да. Строка может быть разбита на «i like samsung» или «i like sam sung».
Tile Stacking Tower
A stable tower of height n is a tower consisting of exactly n tiles of unit height stacked vertically in such a way, that no bigger tile is placed on a smaller tile. An example is shown below:
[ 1 ] [ 2 ] [ 3 ] [ 4 ]
We have infinite number of tiles of sizes 1, 2, …, m. The task is calculate the number of different stable tower of height n that can be built from these tiles, with a restriction that you can use at most k tiles of each size in the tower.
Note: Two tower of height n are different if and only if there exists a height h (1 <= h <= n), such that the towers have tiles of different sizes at height h.
Examples:
Input: n = 3, m = 3, k = 1.
Output: 1
Possible sequences: { 1, 2, 3}.
Hence answer is 1.
Input: n = 3, m = 3, k = 2.
Output: 7
{1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}, {1, 3, 3}, {2, 2, 3}, {2, 3, 3}.
Перевод
Устойчивая башня высотой n — это башня, состоящая из ровно n плиток одинаковой высоты, уложенных вертикально таким образом, что на меньшей плитке не лежит плитка большего размера. Пример:
У нас имеется бесконечное количество плиток размеров 1, 2,..., m. Задача — рассчитать количество возможных стабильных башен высотой n, которые могут быть построены из этих плиток, с учетом того, что Вы можете использовать не более k плиток каждого размера в башне.
Обратите внимание: две башни высотой n различны только тогда, когда существует такая высота h (1 <= h <= n), что башни имеют плитки разных размеров на высоте h.
Примеры:
Вход: n = 3, m = 3, k = 1.
Выход: 1
Возможная последовательность: { 1, 2, 3}. Ответ — 1.
Вход: n = 3, m = 3, k = 2.
Выход: 7
{1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}, {1, 3, 3}, {2, 2, 3}, {2, 3, 3}.
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
У нас имеется бесконечное количество плиток размеров 1, 2,..., m. Задача — рассчитать количество возможных стабильных башен высотой n, которые могут быть построены из этих плиток, с учетом того, что Вы можете использовать не более k плиток каждого размера в башне.
Обратите внимание: две башни высотой n различны только тогда, когда существует такая высота h (1 <= h <= n), что башни имеют плитки разных размеров на высоте h.
Примеры:
Вход: n = 3, m = 3, k = 1.
Выход: 1
Возможная последовательность: { 1, 2, 3}. Ответ — 1.
Вход: n = 3, m = 3, k = 2.
Выход: 7
{1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}, {1, 3, 3}, {2, 2, 3}, {2, 3, 3}.
Ответы будут даны в течение следующей недели — успейте решить. Удачи!
qw1
Задача chickens
Тогда XN=XN/2 + 0.5 + XN+1.
Знаем, что X5=0 (5-му покупателю ничего не осталось), получаем
X4=1, X3=3, X2=7, X1=15.
Ответ: 15
MaxVetrov
А почему вы решили, что 5-му покупателю ничего не досталось? В условиях задачи ничего об этом ни сказано.
qw1
Да, действительно. Но тут ещё проще. В условии сказано, что последнему достался один, отсюда X4=1
MaxVetrov
Я это я уже понял. Просто логику не нашел в резком переходе на X5 :)
.MaxVetrov
PS. X5 — не машина. :)
qw1
Про револьвер
AlexTest
Если стрелять второй раз, то у вас уже не играет пустая камора барабана, выпавшая в первый раз. Т.е. у вас играют два патрона в пяти каморах. А если крутануть барабан, то у вас играет еще раз эта же пустая камора, т.е. у вас снова два патрона в шести каморах. Вероятность быть убитым без прокрутки 2/5, с прокруткой 2/6, т.е. с прокруткой вероятность быть убитым — меньше.
AlexTest
Даже еще хуже, после первого выстрела у вас уже не играют две каморы, т.к. мы знаем что патроны заряжены последовательно. Т.е. шанс быть убитым без прокрутки — 1/2, а с прокруткой — 1/3, т.е. надо крутить, чтобы шанс выжить был выше.
Rsa97
Если в первый раз выстрела не было, значит выпало одно из четырёх пустых гнёзд. Гнёзда эти идут подряд, причём после трёх из них снова пустое гнездо, после четвёртого — патрон. Следовательно, вероятность выстрела без прокрутки барабана — 1/4.
AlexTest
да, ваше рассуждение вернее моего — после первой осечки в этом случае крутить не надо!
Rsa97
Четвёртый: N4/2 + 1/2 = 1 ? N4 = (1 — 1/2) * 2 = 1
Третий: N3 — N3/2 — 1/2 = 1 ? N3/2 = 3/2 ? N3 = 3
Второй: N2 — N2/2 — 1/2 = 3 ? N2/2 = 7/2 ? N2 = 7
Первый: N1 — N1/2 — 1/2 = 7 ? N1/2 = 15/2 ? N1 = 15
Ответ: 15 кур
Ellias
Если всё таки прочитать задачу до конца, то нужно посчитать сколько всего было продано кур за день, а не сколько первый купил. Итого из вашего расчета ответ: 15+7+3+1 = 26.
Простенькая проверка, исходя из условий задачи: будем делить пополам и прибавлять 0,5 курицы.
1: 26/2 + 0,5 = 13,5 (12,5 в остатке)
2: 12/2 + 0,5 (та что в остатке оставалась) = 6,5 (6 в остатке)
3: 6/2 + 0,5 = 3,5 (2,5 в остатке)
4: 2/2 + 0,5 = 1,5 (1 в остатке) или 2/2 = 1 (1,5 в остатке)
То есть, всё сходится, хоть значения N и не совпадают (про то, что у продавца куриц не осталось ни одной курицы в условии ничего нет, значит всё ок).
В задаче есть противоречие, либо это просто исключение, что последний купил одну курицу, но при этом ВСЕ купили половину и ещё пол курицы.
Странно, но кажется ответом может быть и 19 куриц (если принимать, что половина от нечётного числа куриц это округление до чётного числа в меньшую сторону):
1 купил 9,5
2 купил 4,5
3 купил 2,5
4 купил 1,5 (или одну)
Rsa97
А вы внимательней прочитайте решение. N1 — остаток перед продажей первому покупателю, то есть изначальное количество кур.
Ellias
Неверно понял, но тогда получается, что у задачи не менее 4 решений в диапазоне от 12,5 до 26. Интересен правильный ответ, или тут скорее более важен ход мыслей, чем результат.
MaxVetrov
Важен и результат, и ход мыслей я полагаю.(правильный ход мыслей обычно приводит правильному результату)
MaxVetrov
Цыплята
Тогда, из условия задачи:
Найти:
Решение:
Так как
Так как
Подставим,
Получаем,
Выразим
Либо,
Ну и начинаем подставлять до нахождения
Ответ: 15
MaxVetrov
Хотя еще проще :) Не нужно подставлять до нахождения
Если бы покупателей было 1000, то получаем количество проданных цыплят:
т.е.
MaxVetrov
Ошибся, правильный ответ:
т.е.
nasl
В первой задаче не очень понятен вопрос в плане целочисленности действия «половина оставшихся кур и еще пол куры». Очевидное решение, двигаться верх по значению 2^n — 1, может быть не очень правильным. Согласитесь, попросив у продавца выдать половину оставшихся кур и пол куры из 15 штук, вряд ли он выдаст вам 8 штук:) Хотя чисто математически это верно.
Предлагаю другое решение:
У продавца было 12 целых кур и пол куры;
Первому он отдал 6 целых кур (половину от оставшихся 12 целых) и пол куры, осталось 6 целых кур;
Второму отдал 3 (половину от оставшихся 6 целых) и еще пол куры, осталось 2 целых куры и пол куры;
Третьему отдал 1 (половину от оставшихся 2 целых) и еще пол куры, осталось 1 целая кура;
Вот четвертому и осталась одна целая кура
MaxVetrov
Вроде все понятно:
Половина от 15 есть 7.5, если к этому еще 0.5 добавить то первый покупатель получает 8.
nasl
Я согласен, что 15 — правильный ответ! Да, просто я пытался взглянуть на условия задачи под другим углом.
MaxVetrov
ну да, половина в магазине, и в половина в математике — это разные вещи. :)))
nasl
Абсолютно согласен, а в жизни покажите мне хоть одного продавца, который после фразы «половина оставшихся кур и еще пол куры», даст ровно восемь:)
MaxVetrov
Поэтому люди килограммами вешают.)
MaxVetrov
А если убрать доли, и переформулировать задачу
На
То как бы Вы поняли эту задачу?
nasl
Это уже будет совсем другая задача:) Но в такомслучае, после первой же итерации, кур станет нечетное количество, если и было четсное. И тут вопрос деления пополам будет еще более интересным. И вряд ли можно будет сказать, что 7 или 8 — это будет пополам.
MaxVetrov
Чисто
MaxVetrov
:) Если повышать градус неоднозначности, то половину можно брать от оставшихся цыплят и полцыпленка таким способом:
У фермера есть 15 цыплят, берем половину от 15+0.5=15.5
И получаем либо 7 либо 8 :)))
Либо 7.25 :)
tashihu
У вас к третьему покупателю остается 2.5 курицы. Следуя условиям задачи он должен был купить 2.5/2 + 0.5 = 1.75. А 4 останеться только 0.75 курицы.
nasl
Да нет же, я предложил условие задачи интерпретировать не как [N/2 + 0.5], а говоря языком, например, матлаба [fix(N)/2 + 0.5], т.е. половину берем от целого количества куриц.
P.s. Но как мы выяснили выше, при текущем решении значения fix(N) удачно оказались четными, a с нечетными появляется некая неоднозначность при такой условии.
MaxVetrov
Револьвер
Ох уж эти зловещие русские, Сталина хоть не приплели :))
Имеем
x — зарядность револьвера
y — количество подряд вставленных пуль
Вероятность смерти при новой прокрутке револьвера:
P1 = y/x = 2/6 = 1/3
Вероятность смерти без прокрутки:
P2 = 1/(x-y) = 1/(6-2) = 1/4
Получили:
P1>P2
А это значит, что нужно стрелять сразу. И лучше — в бандита. Так шансов выжить больше :))
SkylineIT
Внимательней просто читайте про цыплят и всё станет понятно.
Мне кажется это очевидны.
Просто включаем обратный перебор:
4 итерация:
3 итерация:
2 итерация:
1 итерация:
Ответ 15.
Не знаю как вы мистически больше получаете)
Про револьвер:
Сидим до выстрела = вероятность 2/6 = 1/3 шанс быть убитым;
Выживаем.
Просим еще раз стрелять = 2/5 шанс ~ 40%
Крутим повторно = 1/3 шанс ~ 33.3%
MaxVetrov
Вы мне написали?
MaxVetrov
Про цеплят прочитайте полностью, я общий ответ вывел при любом n(количестве покупателей).
Там спойлер есть, откройте, если вы первый раз здесь.
MaxVetrov
PS. цИплят
reci Автор
Вы шутите?
MaxVetrov
В смысле? я с ошибкой написал — цЕплят, а не цИплят. А править коммент не успел.
MaxVetrov
Вот блин, цЫплят.)))) Очепятка. Тороплюсь.
nasl
Там и правда получается 1/4, а не 2/5. Вы видимо в условии пропустили, что пули вставлены последовательно.
MaxVetrov
А с чего Вы взяли что 2/5?
SkylineIT
А нет.
Всё правильно писали:
При продолжении, получается так, что в барабане остается еще 3 пустых гнезда, которые нас устраивает, а только один следующий патрон ведёт нас к фаталу.
Соотвественно:
При прокрутке мы возвращаемся к вероятности:
MaxVetrov
Ну да, при первом холостом выстреле, мы знаем, что мы находимся на одном из 4 пустых мест, если стреляем дальше, то только один исход из 4 дает реальный выстрел.
MaxVetrov
А если 3 пули вставили подряд, то уже все равно какое решение вы примите — вероятность 50 на 50.
MaxVetrov
ан, нет, оказывается, 1/3 и 1/2 не одно и тоже, все еще больше вероятность выживания если стреляешь сразу.
jmdorian