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

Questions

1. Free place
   

   The board is a 100-seat airplane. Harry is the first person in the line. He picks up a seat at random. If you’ve selected a chord, you’ll see it. The flight is full and you are in line. What is the case?

   
   
   Transfer

   Passengers awaiting landing in a 100-seater airliner. Harry is first in line. When he goes to the plane, he discovers that he has forgotten the number of his seat, so he sits down at a random place. Passengers who come after him begin to occupy their seats according to the tickets, but if they discover that their seat is occupied, then they take their place at a random place. The plane was filled and you are the last to enter. What is the probability that you will fall into your place?
   
   
   
2. Two hourglasses
   

   Measure 9 minutes from a minute and a 7 minutes hour.

   
   
   Transfer

   Measure out 9 minutes using two hourglasses for 4 and for 7 minutes.
   
   
   

Tasks

1. Word boogle
   

   Given where the cell has one character. Find all possible words that can be formed. There is no need to have multiple instances of the same cell.
   ')
   Example:
   
   Input: dictionary [] = {"HABR", "FOR", "QUIZ", "GO"};
   
   boggle [] [] = {{'H', 'I', 'Z'},
   {'U', 'A', 'R'},
   {'Q', 'N', 'B'}};
   
   isWord (str): returns true if str is present in dictionary
   else false.
   
   Output: Following words of dictionary are present
   HABR
   QUIZ
   
   
   
   

   
   
   Transfer

   Given: dictionary; dictionary search method and MxN matrix, where each cell contains one character. Find all possible vocabulary words that can be assembled in sequence from adjacent matrix characters. We can move to any of the 8 neighboring cells, but the word cannot include the same cell twice.
   
   Example:
   
   Login: dictionary [] = {"HABR", "FOR", "QUIZ", "GO"};
   
   boggle [] [] = {{'H', 'I', 'Z'},
   {'U', 'A', 'R'},
   {'Q', 'N', 'B'}};
   
   isWord (str): returns true if the word str is in the dictionary, otherwise - false.
   
   Output: The following words are in the dictionary:
   HABR
   QUIZ
   
   
   
   
   
2. FBI. Ways to decode
   

   The following is a secret mapping message:
   
   'A' -> 1
   'B' -> 2
   ...
   'Z' -> 26
   
   You are an FBI agent. You can decoded.
   Note: An empty digit sequence is decoding. It can be taken away from 0 to 9 and it can be seen as an invalid string.
   
   Example:
   “ABC” (1 2 3) or “LC” (12 3) or “AW” (1 23).
   So total ways are 3.
   
   

   
   
   Transfer

   The secret message consisting of letters AZ is encoded with a numeric notation with the following match:
   
   'A' -> 1
   'B' -> 2
   ...
   'Z' -> 26
   
   You are an FBI ILV agent You need to determine the number of options for decrypting this message. Note: an empty numeric sequence is considered to have one option. It is assumed that the input string has the correct sequence of numbers 0-9. If there are leading 0 or extra closing 0, as well as two or more repeating 0 - such a line is incorrect.
   
   Example:
   The encrypted message is “123”, it can be decrypted as “ABC” (1 2 3) or “LC” (12 3) or “AW” (1 23).
   Answer: 3.
   
   
   
   
3. Multiply strings
   

   Given two numbers as stings s1 and s2, your task is to multiply them. It can be used to complete the function.
   
   Constraints:
   1 <= length of s1 and s2 <= 100
   
   Input: s1 = 4154
   s2 = 51454
   Output: 213779916
   
   Input: s1 = 654154154151454545415415454
   s2 = 63516561563156316545145146514654
   Output: 41549622603955309777243716069997997007620439937711509062916
   

   
   
   Transfer

   Given two numbers in the form of strings s1 and s2, your task is to multiply these numbers. You need to write the multiplyStrings function, which takes only 2 string arguments (s1 and s2) and returns their product as a result.
   
   Limitations:
   1 <= length s1 and s2 <= 100
   
   Example:
   Input: s1 = 4154
   s2 = 51454
   Exit: 213779916
   
   Input: s1 = 654154154151454545415415454
   s2 = 63516561563156316545145146514654
   Exit: 41549622603955309777243716069997997007620439937711509062916
   

Solutions

1. Question 1

   The probability of 50%. In the comments it is discussed in detail, for example, in this .
   
   
   
2. Question 2

   The correct answer is in the first comment.
   
   
   
3. Task 1

   Initial solution:
   

   // C++ program for Boggle game #include<iostream> #include<cstring> using namespace std; #define M 3 #define N 3 // Let the given dictionary be following string dictionary[] = {"HABR", "FOR", "QUIZ", "GO"}; int n = sizeof(dictionary)/sizeof(dictionary[0]); // A given function to check if a given string is present in // dictionary. The implementation is naive for simplicity. As // per the question dictionary is given to us. bool isWord(string &str) { // Linearly search all words for (int i=0; i<n; i++) if (str.compare(dictionary[i]) == 0) return true; return false; } // A recursive function to print all words present on boggle void findWordsUtil(char boggle[M][N], bool visited[M][N], int i, int j, string &str) { // Mark current cell as visited and append current character // to str visited[i][j] = true; str = str + boggle[i][j]; // If str is present in dictionary, then print it if (isWord(str)) cout << str << endl; // Traverse 8 adjacent cells of boggle[i][j] for (int row=i-1; row<=i+1 && row<M; row++) for (int col=j-1; col<=j+1 && col<N; col++) if (row>=0 && col>=0 && !visited[row][col]) findWordsUtil(boggle,visited, row, col, str); // Erase current character from string and mark visited // of current cell as false str.erase(str.length()-1); visited[i][j] = false; } // Prints all words present in dictionary. void findWords(char boggle[M][N]) { // Mark all characters as not visited bool visited[M][N] = {{false}}; // Initialize current string string str = ""; // Consider every character and look for all words // starting with this character for (int i=0; i<M; i++) for (int j=0; j<N; j++) findWordsUtil(boggle, visited, i, j, str); } // Driver program to test above function int main() { char boggle[M][N] = {{'H','I','Z'}, {'U','A','R'}, {'Q','N','B'}}; cout << "Following words of dictionary are present\n"; findWords(boggle); return 0; } 

   
   
   
   
4. Task 2

   Suggested solutions for js , python and go.
   
   
   
5. Task 3

   It can be solved with the help of “multiply in a column”, multiplying the digits one by one and transferring it to the next digit. Solution