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

Questions

1. Gems and pirates
   

   Seven pirates attacked the ship and looted some rare gems from them. They didn’t have a chance to share the time later. It is clear that between the two. When they divided gems it was equally one gem was left. So, they decided to wake up the third pirate and it was not clear. They decided that they wouldn’t have been left. The same happened again with the fifth and sixth. Finally, they woke up the 7th pirate and this time the gems were divided equally.
   How many minimums did they stole in total?

   
   
   Transfer

   Seven pirates seized the ship and mined several gems. They decided to take a break and share their prey later. While everyone was asleep, 2 pirates woke up and decided to divide the stones equally among themselves. When they shared, there was one stone left. Then they decided to wake up another pirate and divide the stones equally for three, but when they did, there was only one stone left. They woke the 4th pirate and tried again to share the treasure, and once again there was one stone left. It was the same when they woke the fifth and sixth pirates. Only when they woke up the seventh pirate, they were able to separate all the stones without a trace.
   How many (minimum) gems made up pirates?
   
   
   
2. Faulty coin & perfect coin
   

   I have two coins.
   * One of the coin is a tail of the coin.
   * The other coin is a perfect coin.
   ')
   I’m blind myself Towards the sky is tail.
   
   Is it tail?
   

   
   
   Transfer

   I have 2 coins:
   * One of them is the wrong coin, with tails on both sides.
   * The second coin is an ideal coin (an eagle on one side, and tails on the reverse).
   
   I, blindfolded, take a coin and toss it on the table. The visible part of the coin is tails.
   
   What is the probability that tails are also tails?
   
   
   

Tasks

1. Print all nodes at distance k
   

   Given the target number of the tree, it will be at the distance from the given target node. No parent pointers are available.
   
   Consider the tree shown in diagram:
   

    
                                  20
                                 / \
                                8 22
                              / \
                            4 12
                                  / \
                                 10 14
   

   
   
   Input: target = pointer to data with data 8; root = pointer to node with data 20; k = 2.
   Output: 10 14 22
   
   If target is 14 and k is 3, then output should be “4 20”
   

   
   
   Transfer

   Given a binary tree, a selected tree node and an integer k. Print all tree nodes that are at a distance k from the target node. Parental links are not available.
   
   Consider a tree:
   

    
                                  20
                                 / \
                                8 22
                              / \
                            4 12
                                  / \
                                 10 14
   

   
   
   Input: target = pointer to node 8; root = pointer to node 20; k = 2.
   Output: 10 14 22
   
   If target = 14 and k = 3, then the output should be “4 20”.
   
   
   
2. Car assembly task
   

   A car factory has two assembly lines, each with n stations. The station is denoted by S _{i, j} where it is either 1 or 2 and it indicates the number of the station. The time taken per station is denoted by a _{i, j} . Each station has been designed to make it easy to use. So, a car chassis must pass through the stations before order before exiting the factory. Assembly lines perform the same task. After it passes through the station, it will continue to be the case. At the junction of the line it takes a ti _{, j} . Each assembly line takes an e and an x ​​and an e. It is a car chassis.

   
   
   Transfer

   The machine factory has 2 assembly lines, each with N stations. A station is defined by S _{i, j} , where i, which can take values ​​of 1 or 2, indicates the line on which the station is located, and j - indicates the number of the station. The time spent by the station is denoted as a _{i, j} . Each station is designed to perform a specific type of work - engine fitting, body fitting, painting, etc. Thus, the undercarriage must pass through all n stations in a certain order before being released from the factory. Parallel stations on both assembly lines perform the same task. After the part passes the station S _{i, j} , it will continue to move through S _{i, j + 1} , unless it is decided to transfer it to another line. Transition from station to station on one line does not require additional time, but transfer from station ji to station j on another line takes time t _{i, j} . Each assembly line also has an input time e _i and an output time x _i , which may be different for both lines. Suggest an algorithm with a minimum build time of the machine.
   
   
   
3. Search in sorted matrix
   

   Given an nxn matrix, sorted in increasing order. Write the key to the matrix.

   
   
   Transfer

   An NxN matrix is ​​given, where each row and column is sorted in ascending order. Given key meaning. Write a program to determine where the key value is in the matrix.
   
   
   

Solutions

1. Question 1

   The pirates had 301 gems, as rightly noted in the comments .
   
   
   
2. Question 2

   The probability is 2/3, why you can see in this comment .
   
   
   
3. Task 1

   Solution option:
   
   

   // Java program to print all nodes at a distance k from given node // A binary tree node class Node { int data; Node left, right; Node(int item) { data = item; left = right = null; } } class BinaryTree { Node root; /* Recursive function to print all the nodes at distance k in tree (or subtree) rooted with given root. */ void printkdistanceNodeDown(Node node, int k) { // Base Case if (node == null || k < 0) return; // If we reach ak distant node, print it if (k == 0) { System.out.print(node.data); System.out.println(""); return; } // Recur for left and right subtrees printkdistanceNodeDown(node.left, k - 1); printkdistanceNodeDown(node.right, k - 1); } // Prints all nodes at distance k from a given target node. // The k distant nodes may be upward or downward.This function // Returns distance of root from target node, it returns -1 // if target node is not present in tree rooted with root. int printkdistanceNode(Node node, Node target, int k) { // Base Case 1: If tree is empty, return -1 if (node == null) return -1; // If target is same as root. Use the downward function // to print all nodes at distance k in subtree rooted with // target or root if (node == target) { printkdistanceNodeDown(node, k); return 0; } // Recur for left subtree int dl = printkdistanceNode(node.left, target, k); // Check if target node was found in left subtree if (dl != -1) { // If root is at distance k from target, print root // Note that dl is Distance of root's left child from // target if (dl + 1 == k) { System.out.print(node.data); System.out.println(""); } // Else go to right subtree and print all k-dl-2 distant nodes // Note that the right child is 2 edges away from left child else printkdistanceNodeDown(node.right, k - dl - 2); // Add 1 to the distance and return value for parent calls return 1 + dl; } // MIRROR OF ABOVE CODE FOR RIGHT SUBTREE // Note that we reach here only when node was not found in left // subtree int dr = printkdistanceNode(node.right, target, k); if (dr != -1) { if (dr + 1 == k) { System.out.print(node.data); System.out.println(""); } else printkdistanceNodeDown(node.left, k - dr - 2); return 1 + dr; } // If target was neither present in left nor in right subtree return -1; } // Driver program to test the above functions public static void main(String args[]) { BinaryTree tree = new BinaryTree(); /* Let us construct the tree shown in above diagram */ tree.root = new Node(20); tree.root.left = new Node(8); tree.root.right = new Node(22); tree.root.left.left = new Node(4); tree.root.left.right = new Node(12); tree.root.left.right.left = new Node(10); tree.root.left.right.right = new Node(14); Node target = tree.root.left.right; tree.printkdistanceNode(tree.root, target, 2); } } 

   
   
   
   
4. Task 2

   Initial solution:
   

    // AC program to find minimum possible time by the car chassis to complete #include <stdio.h> #define NUM_LINE 2 #define NUM_STATION 4 // Utility function to find minimum of two numbers int min(int a, int b) { return a < b ? a : b; } int carAssembly(int a[][NUM_STATION], int t[][NUM_STATION], int *e, int *x) { int T1[NUM_STATION], T2[NUM_STATION], i; T1[0] = e[0] + a[0][0]; // time taken to leave first station in line 1 T2[0] = e[1] + a[1][0]; // time taken to leave first station in line 2 // Fill tables T1[] and T2[] using the above given recursive relations for (i = 1; i < NUM_STATION; ++i) { T1[i] = min(T1[i-1] + a[0][i], T2[i-1] + t[1][i] + a[0][i]); T2[i] = min(T2[i-1] + a[1][i], T1[i-1] + t[0][i] + a[1][i]); } // Consider exit times and retutn minimum return min(T1[NUM_STATION-1] + x[0], T2[NUM_STATION-1] + x[1]); } int main() { int a[][NUM_STATION] = {{4, 5, 3, 2}, {2, 10, 1, 4}}; int t[][NUM_STATION] = {{0, 7, 4, 5}, {0, 9, 2, 8}}; int e[] = {10, 12}, x[] = {18, 7}; printf("%d", carAssembly(a, t, e, x)); return 0; } 

   
   
   
   
5. Task 3

   Here an interesting graphical analysis of the problem. Initial option:
   

    // Java program for implementation of divide and conquer algorithm // to find a given key in a row-wise and column-wise sorted 2D array class SearchInMatrix { public static void main(String[] args) { int[][] mat = new int[][] { {10, 20, 30, 40}, {15, 25, 35, 45}, {27, 29, 37, 48}, {32, 33, 39, 50}}; int rowcount = 4,colCount=4,key=50; for (int i=0; i<rowcount; i++) for (int j=0; j<colCount; j++) search(mat, 0, rowcount-1, 0, colCount-1, mat[i][j]); } // A divide and conquer method to search a given key in mat[] // in rows from fromRow to toRow and columns from fromCol to // toCol public static void search(int[][] mat, int fromRow, int toRow, int fromCol, int toCol, int key) { // Find middle and compare with middle int i = fromRow + (toRow-fromRow )/2; int j = fromCol + (toCol-fromCol )/2; if (mat[i][j] == key) // If key is present at middle System.out.println("Found "+ key + " at "+ i + " " + j); else { // right-up quarter of matrix is searched in all cases. // Provided it is different from current call if (i!=toRow || j!=fromCol) search(mat,fromRow,i,j,toCol,key); // Special case for iteration with 1*2 matrix // mat[i][j] and mat[i][j+1] are only two elements. // So just check second element if (fromRow == toRow && fromCol + 1 == toCol) if (mat[fromRow][toCol] == key) System.out.println("Found "+ key+ " at "+ fromRow + " " + toCol); // If middle key is lesser then search lower horizontal // matrix and right hand side matrix if (mat[i][j] < key) { // search lower horizontal if such matrix exists if (i+1<=toRow) search(mat, i+1, toRow, fromCol, toCol, key); } // If middle key is greater then search left vertical // matrix and right hand side matrix else { // search left vertical if such matrix exists if (j-1>=fromCol) search(mat, fromRow, toRow, fromCol, j-1, key); } } } }