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

Questions

1. Ants in corners
   

   There are 3 ants sitting on three corners of a triangle. Moving along the edge of the triangle. Ants collide?

   
   
   Transfer

   3 ants are in different corners of the triangle. All ants begin to move in a randomly chosen direction along the sides of the triangle. What is the probability of a collision of 2 ants?
   
   
   
2. Red hat / blue hat
   

   A team of three people decide on a strategy for playing the following game. Each player walks into a room. For each player, decid that player's hat, either red or blue. Hey, Hey, Hey. After deciding on the colors of each player
   - “I have a red hat”
   - “I had a blue hat”
   - “I pass”
   ')
   The player’s responses are recorded. The team wins the player making the response. In other words, it’s not a problem. What is your chance?
   
   For example, one of the three players. This player will respond “I have a red hat” and the others will respond “I pass”. The expected chance of winning with this strategy is 50%. Can you do better?

   
   
   Transfer

   A team of three people chooses a strategy to play the following game: each player enters the room. At the entrance, the correct coin color is determined by throwing the player's hat - red or blue. Each player can see the colors of the hats of 2 other players, but not his own. After reviewing the colors, the player can choose one of the answer options:
   - I have a red hat
   - I have a blue hat
   - I pass
   Answers of all players are recorded, but not shown to other players, until all are answered. The team wins if at least one player wrote the color in the answer and if all the colors were specified correctly. In other words, the team loses if everyone answers “I pass” or someone makes a mistake with the definition of their color. What strategy can increase a team’s chances of winning?
   
   For example, one of the possible options is the answer of only the chosen player. This player answers "I have a red hat" or "I have a blue hat", the others fold. The expected probability to win with this strategy is 50%. Can you offer a better solution?
   
   
   

Tasks

1. Special keyboard
   

   Imagine you have a special keyboard with the following keys:
   

     A
            Ctrl + A
            Ctrl + C
            Ctrl + V 
   

   
   where ctrl + a, ctrl + c, ctrl + v, select all ”,“ copy ”, and“ paste ”operations respectively.
   If you can only use the keyboard for the times, then you can also get out the sequence of keys.
   If you can press it, you can use it.
   
   Ex:
   
   Input: N = 3
   Output: 3
   3 keying up the following key sequence.
   A, A, A
   
   Input: N = 7
   Output: 9
   9 keys for pressing the following key sequence.
   A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
   
   Input: N = 11
   Output: 27
   27 keying up the following key sequence.
   A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V, Ctrl A, Ctrl C, Ctrl V, Ctrl V
   

   
   
   Transfer

   Imagine that you have a special keyboard with the following keys:
   

     A
            Ctrl + A
            Ctrl + C
            Ctrl + V 
   

   
   where CTRL + A, CTRL + C, CTRL + V work as “Select All”, “Copy”, “Paste” respectively.
   You can press the keyboard N times (only the specified keys). Write a program that gives the maximum amount of “A” using these operations. If possible, also output a sequence of clicks. In other words, the input is N (the number of clicks), the output is M (the number of "A" that can be obtained).
   Examples:
   Input: N = 3
   Output: 3
   We can get a maximum of 3 A with the following sequence of clicks: A, A, A
   
   Input: N = 7
   Output: 9
   Maximum - 9 A, sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
   
   Input: N = 11
   Output: 27
   Maximum - 27 A, sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V, Ctrl A, Ctrl C, Ctrl V, Ctrl V
   
   
   
2. Boolean parenthesization
   

   Given a boolean expression with the following symbols.
   
   Symbols
   'T' ---> true
   'F' ---> false
   
   And following operators filled between symbols
   
   Operators
   & ---> boolean AND
   | ---> boolean OR
   ^ ---> boolean XOR
   
   The number of ways to count the number of ways to count.
   
   There are no symbols for each of the rules.
   
   Examples:
   
   Input: symbol [] = {T, F, T}
   operator [] = {^, &}
   Output: 2
   The given expression is "T ^ F & T", it evaluates true in two ways "((T ^ F) & T)" and "(T ^ (F & T))"
   
   Input: symbol [] = {T, F, F}
   operator [] = {^, |}
   Output: 2
   The given expression is “T ^ F | F ", it evaluates true in two ways" ((T ^ F) | F) "and" (T ^ (F | F)) ".
   
   Input: symbol [] = {T, T, F, T}
   operator [] = {|, &, ^}
   Output: 4
   The given expression is “T | T & F ^ T ”, it evaluates true in 4 ways ((T | T) & (F ^ T)), (T | (T & (F ^ T))), (((T | T) & F) ^ T) and (T | ((T & F) ^ T)).
   

   
   
   Transfer

   A logical expression is given with the following characters:
   
   Characters
   'T' ---> true
   'F' ---> false
   
   And the following statements inserted between characters:
   
   Operators
   & ---> logical AND
   | ---> logical OR
   ^ ---> exclusive OR
   
   Count the number of options for the placement of brackets so that the value of the expression becomes equal to true.
   
   Suppose the input data is presented in the form of 2 arrays - characters (T and F) and operators (&, | and ^).
   
   Examples:
   
   Input: symbol [] = {T, F, T}
   operator [] = {^, &}
   Output: 2
   The expression "T ^ F & T" becomes true in 2 cases: "((T ^ F) & T)" and "(T ^ (F & T))"
   
   Input: symbol [] = {T, F, F}
   operator [] = {^, |}
   Output: 2
   The expression "T ^ F | F ”, becomes true in 2 cases" ((T ^ F) | F) "and" (T ^ (F | F)) ".
   
   Input: symbol [] = {T, T, F, T}
   operator [] = {|, &, ^}
   Output: 4
   The expression "T | T & F ^ T ", becomes true in 4 cases: ((T | T) & (F ^ T)), (T | (T & (F ^ T))), (((T | T) & F) ^ T) and (T | ((T & F) ^ T)).
   
   
   
3. Alien language
   

   This is a sorted dictionary of languages.
   
   Examples:
   
   Input: words [] = {"baa", "abcd", "abca", "cab", "cad"}
   Output: Order of characters is 'b', 'd', 'a', 'c'
   The words “baa” comes before “abcd”, therefore 'b' is before 'a' in output. Similarly we can find other orders.
   
   Input: words [] = {"caa", "aaa", "aab"}
   Output: Order of characters is 'c', 'a', 'b'
   

   
   
   Transfer

   Given a dictionary (array of words) sorted in alphabetical order of a foreign language, find the order of the letters in the alphabet of this language.
   
   Examples:
   
   Input: words [] = {"baa", "abcd", "abca", "cab", "cad"}
   Output: The order of the letters 'b', 'd', 'a', 'c'
   Note that 'baa' comes before 'abcd', therefore in the alphabet 'b' stands for 'a'. Similarly, we learn the order of other letters.
   
   Input: words [] = {"caa", "aaa", "aab"}
   Output: The order of the letters 'c', 'a', 'b'.
   
   
   

Solutions

1. Question 1

   In the comments found the correct answer.
   
   
   
2. Question 2

   The comments found the correct answer for the option "blindly", when players do not see who has already answered.
   
   
   
3. Task 1

   Java solution:
   

   /* A recursive C program to print maximum number of A's using following four keys */ import java.io.*; class GFG { // A recursive function that returns // the optimal length string for N keystrokes static int findoptimal(int N) { // The optimal string length is N // when N is smaller than 7 if (N <= 6) return N; // Initialize result int max = 0; // TRY ALL POSSIBLE BREAK-POINTS // For any keystroke N, we need to // loop from N-3 keystrokes back to // 1 keystroke to find a breakpoint // 'b' after which we will have Ctrl-A, // Ctrl-C and then only Ctrl-V all the way. int b; for (b = N - 3; b >= 1; b--) { // If the breakpoint is s at b'th // keystroke then the optimal string // would have length // (nb-1)*screen[b-1]; int curr = (N - b - 1) * findoptimal(b); if (curr > max) max = curr; } return max; } // Driver program public static void main(String[] args) { int N; // for the rest of the array we // will rely on the previous // entries to compute new ones for (N = 1; N <= 20; N++) System.out.println("Maximum Number of A's with keystrokes is " + N + findoptimal(N)); } } 

   
   
   
   
4. Task 2

   Solution option:
   

    #include<iostream> #include<cstring> using namespace std; // Returns count of all possible parenthesizations that lead to // result true for a boolean expression with symbols like true // and false and operators like &, | and ^ filled between symbols int countParenth(char symb[], char oper[], int n) { int F[n][n], T[n][n]; // Fill diaginal entries first // All diagonal entries in T[i][i] are 1 if symbol[i] // is T (true). Similarly, all F[i][i] entries are 1 if // symbol[i] is F (False) for (int i = 0; i < n; i++) { F[i][i] = (symb[i] == 'F')? 1: 0; T[i][i] = (symb[i] == 'T')? 1: 0; } // Now fill T[i][i+1], T[i][i+2], T[i][i+3]... in order // And F[i][i+1], F[i][i+2], F[i][i+3]... in order for (int gap=1; gap<n; ++gap) { for (int i=0, j=gap; j<n; ++i, ++j) { T[i][j] = F[i][j] = 0; for (int g=0; g<gap; g++) { // Find place of parenthesization using current value // of gap int k = i + g; // Store Total[i][k] and Total[k+1][j] int tik = T[i][k] + F[i][k]; int tkj = T[k+1][j] + F[k+1][j]; // Follow the recursive formulas according to the current // operator if (oper[k] == '&') { T[i][j] += T[i][k]*T[k+1][j]; F[i][j] += (tik*tkj - T[i][k]*T[k+1][j]); } if (oper[k] == '|') { F[i][j] += F[i][k]*F[k+1][j]; T[i][j] += (tik*tkj - F[i][k]*F[k+1][j]); } if (oper[k] == '^') { T[i][j] += F[i][k]*T[k+1][j] + T[i][k]*F[k+1][j]; F[i][j] += T[i][k]*T[k+1][j] + F[i][k]*F[k+1][j]; } } } } return T[0][n-1]; } // Driver program to test above function int main() { char symbols[] = "TTFT"; char operators[] = "|&^"; int n = strlen(symbols); // There are 4 ways // ((T|T)&(F^T)), (T|(T&(F^T))), (((T|T)&F)^T) and (T|((T&F)^T)) cout << countParenth(symbols, operators, n); return 0; } 

   
   
   
   
5. Task 3

   Solution option:
   

    // A C++ program to order of characters in an alien language #include<iostream> #include <list> #include <stack> #include <cstring> using namespace std; // Class to represent a graph class Graph { int V; // No. of vertices' // Pointer to an array containing adjacency listsList list<int> *adj; // A function used by topologicalSort void topologicalSortUtil(int v, bool visited[], stack<int> &Stack); public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int v, int w); // prints a Topological Sort of the complete graph void topologicalSort(); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v's list. } // A recursive function used by topologicalSort void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack) { // Mark the current node as visited. visited[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) topologicalSortUtil(*i, visited, Stack); // Push current vertex to stack which stores result Stack.push(v); } // The function to do Topological Sort. It uses recursive topologicalSortUtil() void Graph::topologicalSort() { stack<int> Stack; // Mark all the vertices as not visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to store Topological Sort // starting from all vertices one by one for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, Stack); // Print contents of stack while (Stack.empty() == false) { cout << (char) ('a' + Stack.top()) << " "; Stack.pop(); } } int min(int x, int y) { return (x < y)? x : y; } // This function fidns and prints order of characer from a sorted // array of words. n is size of words[]. alpha is set of possible // alphabets. // For simplicity, this function is written in a way that only // first 'alpha' characters can be there in words array. For // example if alpha is 7, then words[] should have only 'a', 'b', // 'c' 'd', 'e', 'f', 'g' void printOrder(string words[], int n, int alpha) { // Create a graph with 'aplha' edges Graph g(alpha); // Process all adjacent pairs of words and create a graph for (int i = 0; i < n-1; i++) { // Take the current two words and find the first mismatching // character string word1 = words[i], word2 = words[i+1]; for (int j = 0; j < min(word1.length(), word2.length()); j++) { // If we find a mismatching character, then add an edge // from character of word1 to that of word2 if (word1[j] != word2[j]) { g.addEdge(word1[j]-'a', word2[j]-'a'); break; } } } // Print topological sort of the above created graph g.topologicalSort(); } // Driver program to test above functions int main() { string words[] = {"caa", "aaa", "aab"}; printOrder(words, 3, 3); return 0; }