Issue # 24: IT training - current issues and challenges from leading companies

Questions

1. Chickens
   

   A farmer sold out on a particular day. It was purchased for each chickens and a half chicken more.
   
   If you’ve bought a single chicken?

   
   
   Transfer

   За один день фермер продал несколько цыплят четырем покупателям. Так вышло, что каждый из них купил половину остававшихся цыплят и ещё полцыплёнка.
   
   Можете ли Вы сказать, сколько цыплят было продано в этот день, если известно, что 4-ый покупатель купил целого цыпленка?
   
   
   
2. Bullets and revolver
   

   A Russian gangster kidnaps you. He puts two bullets in his hands on the road. * click * You're still alive. It can be a shot?

   
   
   Transfer

   Вас похитил русский бандит (ох уж эти стереотипы!). Он последовательно вставил 2 пули в шестизарядный револьвер, прокрутил барабан, прицелился Вам в голову и спустил курок. *щёлк*. Вы всё ещё живы. Бандит спросил Вас — «Вы желаете, чтобы я прокрутил ещё раз и выстрелил, или выстрелил немедленно?». Какова вероятность быть застреленным в каждом случае?
   
   
   

Tasks

1. Sort a stack using recursion
   

   Given a stack, it is a reuse. Constructs like while for for etc is not allowed. We can only use the following functions: Stack S:
   
   is_empty (S): Tests whether it 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. Do not remove the stack from the stack.
   
   Example:
   
   Input: -3 <- Top
   14
   18
   -5
   30
   
   Output: 30 <- Top
   18
   14
   -3
   -5

   
   
   Transfer

   Дан стек, задача — отсортировать его с помощью рекурсии. Использование циклических конструкций, вроде while, for… и др. запрещено. Позволено использовать только следующие абстракные команды на стеке S:
   
   is_empty(S): Проверяет, пуст ли стек.
   push(S): Добавляет новый элемент в стек.
   pop(S): Снимает верхий элемент стека.
   top(S): Возвращает значение верхнего элемента. Обратите внимание, что элемент не удаляется при этом.
   
   Примеры:
   
   Вход: -3 < — Вершина стека
   14
   18
   -5
   30
   
   Выход: 30 < — Вершина стека
   18
   14
   -3
   -5
   
   

It can be segmented into a sequence of dictionary words. See the following examples for more details.

Consider the following dictionary
{like, sam, sung, samsung, mobile, ice,
cream, icecream, man, go, mango}

Input: ilike
Output: Yes
.

Input: ilikesamsung
Output: Yes, it
can be segmented as "i like samsung"
or "i like sam sung".

The height of the height of the height of the tile is not the same as the height of the tile. An example is shown below:

          [ one ]
       [2]
    [3]
[ four ]

We have infinite number of tiles of sizes 1, 2, ..., m. It can be used to calculate the number of

If there is a height of h (1 <= h <= n),

Examples:

Input: n = 3, m = 3, k = 1.
Output: 1
Possible sequences: {1, 2, 3}.
Hence answer

: 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           ]

Solutions

1. Question 1

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

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

   Вариант решения, динамическое программирование:
   

   #include<iostream>#include<string.h>usingnamespacestd;
   /* 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*/intdictionaryContains(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)
              returntrue;
       returnfalse;
   }
   // Returns true if string can be segmented into space separated// words, otherwise returns falseboolwordBreak(string str){
       int size = str.size();
       if (size == 0)   returntrue;
       // 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 prefixif (i == size)
                   returntrue;
               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 characterif (j == size && wb[j] == true)
                       returntrue;
               }
           }
       }
       /* 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 workedreturnfalse;
   }
   // Driver program to test above functionsintmain(){
       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";
       return0;
   }

   
   
   
   
4. Task 2

   Вариант решения на java:
   

   import java.util.ListIterator;
   import java.util.Stack;
   classTest{
       // Recursive Method to insert an item x in sorted waystaticvoidsortedInsert(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 recurint temp = s.pop();
           sortedInsert(s, x);
           // Put back the top item removed earlier
           s.push(temp);
       }
       // Method to sort stackstaticvoidsortStack(Stack<Integer> s){
           // If stack is not emptyif (!s.isEmpty())
           {
               // Remove the top itemint 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 stackstaticvoidprintStack(Stack<Integer> s){
          ListIterator<Integer> lt = s.listIterator();
          // forwardingwhile(lt.hasNext())
              lt.next();
          // printing from top to bottomwhile(lt.hasPrevious())
              System.out.print(lt.previous()+" ");
       }
       // Driver method publicstaticvoidmain(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. Task 3

   Вариант решения:
   

   #include<bits/stdc++.h>usingnamespacestd;
   #define N 100intpossibleWays(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 mfor (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 Programintmain(){
       int n = 3, m = 3, k = 2;
       cout << possibleWays(n, m, k) << endl;
       return0;
   }