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

Вопросы

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
   
   

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

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           ]

Решения

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