Pull to refresh
0
Spice IT Recruitment
ИТ-специализированное кадровое агентство

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

Reading time 6 min
Views 7.2K
В новый выпуск 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».

Перевод
Дана входная строка и словарь. Напишите программу для нахождения, может ли быть строка разбита на последовательность слов из словаря. Примеры:

Дан следующий словарь:
{ 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    ]
    [       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}.

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

Решения


  1. Вопрос 1
    Ответ: 15. Тут объяснили почему.

  2. Вопрос 2
    В комментариях верно ответили на этот вопрос
    Вероятность того, что в следующем гнезде барабана находится патрон — 1/4
    Если прокрутить барабан, то вероятность того, что он остановится на патроне — 2/6 = 1/3

  3. Задача 1
    Вариант решения, динамическое программирование:
    #include <iostream>
    #include <string.h>
    using namespace std;
     
    /* A utility function to check whether a word is present in dictionary or not.
      An array of strings is used for dictionary.  Using array of strings for
      dictionary is definitely not a good idea. We have used for simplicity of
      the program*/
    int dictionaryContains(string word)
    {
        string dictionary[] = {"mobile","samsung","sam","sung","man","mango",
                               "icecream","and","go","i","like","ice","cream"};
        int size = sizeof(dictionary)/sizeof(dictionary[0]);
        for (int i = 0; i < size; i++)
            if (dictionary[i].compare(word) == 0)
               return true;
        return false;
    }
     
    // Returns true if string can be segmented into space separated
    // words, otherwise returns false
    bool wordBreak(string str)
    {
        int size = str.size();
        if (size == 0)   return true;
     
        // Create the DP table to store results of subroblems. The value wb[i]
        // will be true if str[0..i-1] can be segmented into dictionary words,
        // otherwise false.
        bool wb[size+1];
        memset(wb, 0, sizeof(wb)); // Initialize all values as false.
     
        for (int i=1; i<=size; i++)
        {
            // if wb[i] is false, then check if current prefix can make it true.
            // Current prefix is "str.substr(0, i)"
            if (wb[i] == false && dictionaryContains( str.substr(0, i) ))
                wb[i] = true;
     
            // wb[i] is true, then check for all substrings starting from
            // (i+1)th character and store their results.
            if (wb[i] == true)
            {
                // If we reached the last prefix
                if (i == size)
                    return true;
     
                for (int j = i+1; j <= size; j++)
                {
                    // Update wb[j] if it is false and can be updated
                    // Note the parameter passed to dictionaryContains() is
                    // substring starting from index 'i' and length 'j-i'
                    if (wb[j] == false && dictionaryContains( str.substr(i, j-i) ))
                        wb[j] = true;
     
                    // If we reached the last character
                    if (j == size && wb[j] == true)
                        return true;
                }
            }
        }
     
        /* Uncomment these lines to print DP table "wb[]"
         for (int i = 1; i <= size; i++)
            cout << " " << wb[i]; */
     
        // If we have tried all prefixes and none of them worked
        return false;
    }
     
    // Driver program to test above functions
    int main()
    {
        wordBreak("ilikesamsung")? cout <<"Yesn": cout << "Non";
        wordBreak("iiiiiiii")? cout <<"Yesn": cout << "Non";
        wordBreak("")? cout <<"Yesn": cout << "Non";
        wordBreak("ilikelikeimangoiii")? cout <<"Yesn": cout << "Non";
        wordBreak("samsungandmango")? cout <<"Yesn": cout << "Non";
        wordBreak("samsungandmangok")? cout <<"Yesn": cout << "Non";
        return 0;
    }


  4. Задача 2
    Вариант решения на java:
    import java.util.ListIterator;
    import java.util.Stack;
     
    class Test
    {
        // Recursive Method to insert an item x in sorted way
        static void sortedInsert(Stack<Integer> s, int x)
        {
            // Base case: Either stack is empty or newly inserted
            // item is greater than top (more than all existing)
            if (s.isEmpty() || x > s.peek())
            {
                s.push(x);
                return;
            }
          
            // If top is greater, remove the top item and recur
            int temp = s.pop();
            sortedInsert(s, x);
          
            // Put back the top item removed earlier
            s.push(temp);
        }
          
        // Method to sort stack
        static void sortStack(Stack<Integer> s)
        {
            // If stack is not empty
            if (!s.isEmpty())
            {
                // Remove the top item
                int x = s.pop();
          
                // Sort remaining stack
                sortStack(s);
          
                // Push the top item back in sorted stack
                sortedInsert(s, x);
            }
        }
         
        // Utility Method to print contents of stack
        static void printStack(Stack<Integer> s)
        {
           ListIterator<Integer> lt = s.listIterator();
            
           // forwarding
           while(lt.hasNext())
               lt.next();
            
           // printing from top to bottom
           while(lt.hasPrevious())
               System.out.print(lt.previous()+" ");
        }
       
        // Driver method 
        public static void main(String[] args) 
        {
            Stack<Integer> s = new Stack<>();
            s.push(30);
            s.push(-5);
            s.push(18);
            s.push(14);
            s.push(-3);
          
            System.out.println("Stack elements before sorting: ");
            printStack(s);
          
            sortStack(s);
          
            System.out.println(" \n\nStack elements after sorting:");
            printStack(s);
          
        }
    }
    


  5. Задача 3
    Вариант решения:
    
    #include <bits/stdc++.h>
    using namespace std;
    #define N 100
     
    int possibleWays(int n, int m, int k)
    {
        int dp[N][N];
        int presum[N][N];
        memset(dp, 0, sizeof dp);
        memset(presum, 0, sizeof presum);
     
        // Initialing 0th row to 0.
        for (int i = 1; i < n + 1; i++) {
            dp[0][i] = 0;
            presum[0][i] = 1;
        }
     
        // Initialing 0th column to 0.
        for (int i = 0; i < m + 1; i++)
            presum[i][0] = dp[i][0] = 1;
     
        // For each row from 1 to m
        for (int i = 1; i < m + 1; i++) {
     
            // For each column from 1 to n.
            for (int j = 1; j < n + 1; j++) {
     
                // Initialing dp[i][j] to presum of (i - 1, j).
                dp[i][j] = presum[i - 1][j];
                if (j > k) {
                    dp[i][j] -= presum[i - 1][j - k - 1];
                }
            }
     
            // Calculating presum for each i, 1 <= i <= n.
            for (int j = 1; j < n + 1; j++)
                presum[i][j] = dp[i][j] + presum[i][j - 1];
        }
     
        return dp[m][n];
    }
     
    // Driver Program
    int main()
    {
        int n = 3, m = 3, k = 2;
        cout << possibleWays(n, m, k) << endl;
        return 0;
    }
    


Tags:
Hubs:
+5
Comments 47
Comments Comments 47

Articles

Information

Website
www.spiceit.ru
Registered
Founded
2009
Employees
31–50 employees
Location
Россия