Выпуск#24: ITренировка — актуальные вопросы и задачи от ведущих компаний

В новый выпуск ITренировки вошли задачи от «синего гиганта», компании IBM.

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

Вопросы

1. 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-ый покупатель купил целого цыпленка?

2. 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 пули в шестизарядный револьвер, прокрутил барабан, прицелился Вам в голову и спустил курок. *щёлк*. Вы всё ещё живы. Бандит спросил Вас — «Вы желаете, чтобы я прокрутил ещё раз и выстрелил, или выстрелил немедленно?». Какова вероятность быть застреленным в каждом случае?

Задачи

1. 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

Word breaker

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».

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}.

          [ 1 ]
       [    2    ]
    [       3       ]
[          4           ]

Ответы будут даны в течение следующей недели — успейте решить. Удачи!

Автор: Андрей

Источник