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

   In one day, the farmer sold several chickens to four buyers. It turned out that each of them bought half of the remaining chickens and another half a chicken.
   
   Can you tell how many chicks were sold that day if it is known that the 4th buyer bought the whole chicken?
   
   
   
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

   You were kidnapped by a Russian gangster ( oh, those stereotypes! ). He consistently inserted 2 bullets into a six-shot revolver, spun the drum, aimed at your head and pulled the trigger. * click *. You are still alive. The gangster asked you - “Do you want me to scroll again and shoot, or shoot immediately?”. What is the probability of being shot in each case?
   
   
   

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 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. Do not remove the stack from the stack.
   
   Example:
   
   Input: -3 <- Top
   14
   18
   -five
   thirty
   
   Output: 30 <- Top
   18
   14
   -3
   -five

   
   
   Transfer

   The stack is given, the task is to sort it using recursion. The use of cyclic constructions, such as while, for ... and others is prohibited. You can use only the following abstract commands on the S stack:
   
   is_empty (S): Checks if the stack is empty.
   push (S): Adds a new item to the stack.
   pop (S): Removes the top element of the stack.
   top (S): Returns the value of the top element. Please note that the item is not deleted.
   
   Examples:
   
   Input: -3 <- Top of stack
   14
   18
   -five
   thirty
   
   Exit: 30 <- Top of stack
   18
   14
   -3
   -five
   
   

It can be segmented into a sequence of dictionary words. See the 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".

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

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

Solutions

1. Question 1

   Answer: 15. They explained why.
   
   
2. Question 2

   In the comments correctly answered this question.
   The likelihood that there is a cartridge in the next slot of the drum - 1/4
   If you rotate the drum, the probability that it stops at the cartridge is 2/6 = 1/3
   
   
   
3. Task 1

   Solution option, dynamic programming:
   

   #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 'ji' if (wb[j] == false && dictionaryContains( str.substr(i, ji) )) 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. Task 2

   Solution option on 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. Task 3

   Solution option:
   

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