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

Questions

1. Water in bathroom
   

   I completed my bath tub along with new accessories. I have two taps now - hot one and cold one. It is a hot water bath and a bathtub.
   
   Taps are not running.
   ')
   If I have to leave it to my bathtub?

   
   
   Transfer

   After repair, a new bathroom with new taps appeared in my bathroom. There are two of them - hot and cold. A hot tap fills the bathroom faster in fifteen minutes, while a cold tap will take eighteen minutes.
   
   If you open the drain - the bath will be empty after 10 minutes with taps closed.
   
   If I leave both taps open and do not plug the drain, how long will it take to fill the bath?
   
   
   
2. Mark and the traffic
   

   Mark his last weekend. He started out on Saturday and found out that the road was too crowded. There were times that he has completely stationary. He reached his mother's house after lunch.
   
   He had to travel through the same route again. He found the time of day for a smooth drive.
   
   He traveled?

   
   
   Transfer

   Mark went to visit his mother for the weekend, who lives 250 miles from his home. He left at 7 in the morning and found that the roads were crowded. At times he even stood and arrived at his mother after lunch ( approx. At 13:00 ).
   Mark had to return on Sunday by the same route. He left at 7 am, noting in passing that there were no cars on the road, and came home before lunch ( note at 12:00 ), enjoying a leisurely ride.
   
   What is the probability that Mark could end up at the same point at the same time on the way there and back?
   
   
   

Tasks

1. Print numbers with mobile pad
   

   Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. Bottom row corner buttons (ie * and #).
   

       [1] [2] [3]
       [4] [5] [6]
       [7] [8] [9]
       [*] [0] [#]
   

   
   The number of possible numbers is given.
   
   Examples:
   For N = 1, the number of possible numbers would be 10 (0, 1, 2, 3,…., 9)
   For N = 2, number of possible numbers would be 36
   Possible numbers: 00.08 11,12,14 22,21,23,25 and so on.
   

   
   
   Transfer

   There is a mobile keyboard on which it is allowed to press the buttons above, below and on the sides of a given button ( Approx. A given button can also be pressed, which follows from the examples ). The bottom * and # do not touch.
   
   

       [1] [2] [3]
       [4] [5] [6]
       [7] [8] [9]
       [*] [0] [#]
   

   
   Given the number N, write a program that calculates the number of admissible numbers of a given length.
   
   Examples:
   For N = 1, the number of numbers is 10 (0, 1, 2, 3, ..., 9)
   For N = 2, the number of numbers is 36 (00.08 11,12,14 22,21,23,25, etc.)
   
   
   
2. Clone binary tree
   

   Given a Binary Tree where every node has the following structure.
   struct node {
int key;
struct node *left,*right,*random;
}

   Points to null. Create a program to clone the binary tree.
   

   
   
   Transfer

   Given - a binary tree with nodes of the following structure:
   struct node {
int key;
struct node *left,*right,*random;
}

   
   * Random pointers refer to a random tree node, and may contain NULL. Create a program to clone this binary tree.
   
   
   
3. Book readers
   

   I’m not sure that I’ve been able to make it anymore. It doesn’t read too much extra / less pages overall.
   
   Example 1:
   Input: Number of Days to Finish book = 2
   Number of pages in chapters = {10, 5, 5}
   Output: Day 1: Chapter 1
   Day 2: Chapters 2 and 3
   
   Example 2:
   Input: Number of Days to Finish book = 3
   Number of pages in chapters = {8, 5, 6, 12}
   Output: Day 1: Chapter 1
   Day 2: Chapters 2 and 3
   Day 3: Chapter 4
   
   

   
   
   Transfer

   It is known that a person reads a book for k days, but does not want to stop in the middle of a chapter. Find the optimal distribution of chapters (by day) so that the reader does not have to overwork (read too many / few pages per day).
   
   Example 1:
   Entry: Days to read the book = 2
   Number of pages in chapters = {10, 5, 5}
   Exit: Day 1: Chapter 1
   Day 2: Chapter 2, Chapter 3
   
   Example 2:
   Entry: Days to read the book = 3
   Number of pages in chapters = {8, 5, 6, 12}
   Exit: Day 1: Chapter 1
   Day 2: Chapter 2, Chapter 3
   Day 3: Chapter 4
   
   
   

Solutions

1. Question 1

   jmdorian correctly calculated the answer - 45 minutes.
   
   
   
2. Question 2

   100 %. This comment answered why.
   
   
   
3. Task 1

   Initial solution:
   

    #include <stdio.h> // Return count of all possible numbers of length n // in a given numeric keyboard int getCount(char keypad[][3], int n) { if(keypad == NULL || n <= 0) return 0; if(n == 1) return 10; // left, up, right, down move from current location int row[] = {0, 0, -1, 0, 1}; int col[] = {0, -1, 0, 1, 0}; // taking n+1 for simplicity - count[i][j] will store // number count starting with digit i and length j int count[10][n+1]; int i=0, j=0, k=0, move=0, ro=0, co=0, num = 0; int nextNum=0, totalCount = 0; // count numbers starting with digit i and of lengths 0 and 1 for (i=0; i<=9; i++) { count[i][0] = 0; count[i][1] = 1; } // Bottom up - Get number count of length 2, 3, 4, ... , n for (k=2; k<=n; k++) { for (i=0; i<4; i++) // Loop on keypad row { for (j=0; j<3; j++) // Loop on keypad column { // Process for 0 to 9 digits if (keypad[i][j] != '*' && keypad[i][j] != '#') { // Here we are counting the numbers starting with // digit keypad[i][j] and of length k keypad[i][j] // will become 1st digit, and we need to look for // (k-1) more digits num = keypad[i][j] - '0'; count[num][k] = 0; // move left, up, right, down from current location // and if new location is valid, then get number // count of length (k-1) from that new digit and // add in count we found so far for (move=0; move<5; move++) { ro = i + row[move]; co = j + col[move]; if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 && keypad[ro][co] != '*' && keypad[ro][co] != '#') { nextNum = keypad[ro][co] - '0'; count[num][k] += count[nextNum][k-1]; } } } } } } // Get count of all possible numbers of length "n" starting // with digit 0, 1, 2, ..., 9 totalCount = 0; for (i=0; i<=9; i++) totalCount += count[i][n]; return totalCount; } // Driver program to test above function int main(int argc, char *argv[]) { char keypad[4][3] = {{'1','2','3'}, {'4','5','6'}, {'7','8','9'}, {'*','0','#'}}; printf("Count for numbers of length %d: %dn", 1, getCount(keypad, 1)); printf("Count for numbers of length %d: %dn", 2, getCount(keypad, 2)); printf("Count for numbers of length %d: %dn", 3, getCount(keypad, 3)); printf("Count for numbers of length %d: %dn", 4, getCount(keypad, 4)); printf("Count for numbers of length %d: %dn", 5, getCount(keypad, 5)); return 0; } 

   
   
   
   
4. Task 2

   Solution option with hashing:
   

    // A hashmap based C++ program to clone a binary tree with random pointers #include<iostream> #include<map> using namespace std; /* A binary tree node has data, pointer to left child, a pointer to right child and a pointer to random node*/ struct Node { int key; struct Node* left, *right, *random; }; /* Helper function that allocates a new Node with the given data and NULL left, right and random pointers. */ Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->random = temp->right = temp->left = NULL; return (temp); } /* Given a binary tree, print its Nodes in inorder*/ void printInorder(Node* node) { if (node == NULL) return; /* First recur on left sutree */ printInorder(node->left); /* then print data of Node and its random */ cout << "[" << node->key << " "; if (node->random == NULL) cout << "NULL], "; else cout << node->random->key << "], "; /* now recur on right subtree */ printInorder(node->right); } // This function creates clone by copying key and left and right pointers // This function also stores mapping from given tree node to clone. Node* copyLeftRightNode(Node* treeNode, map<Node *, Node *> *mymap) { if (treeNode == NULL) return NULL; Node* cloneNode = newNode(treeNode->key); (*mymap)[treeNode] = cloneNode; cloneNode->left = copyLeftRightNode(treeNode->left, mymap); cloneNode->right = copyLeftRightNode(treeNode->right, mymap); return cloneNode; } // This function copies random node by using the hashmap built by // copyLeftRightNode() void copyRandom(Node* treeNode, Node* cloneNode, map<Node *, Node *> *mymap) { if (cloneNode == NULL) return; cloneNode->random = (*mymap)[treeNode->random]; copyRandom(treeNode->left, cloneNode->left, mymap); copyRandom(treeNode->right, cloneNode->right, mymap); } // This function makes the clone of given tree. It mainly uses // copyLeftRightNode() and copyRandom() Node* cloneTree(Node* tree) { if (tree == NULL) return NULL; map<Node *, Node *> *mymap = new map<Node *, Node *>; Node* newTree = copyLeftRightNode(tree, mymap); copyRandom(tree, newTree, mymap); return newTree; } /* Driver program to test above functions*/ int main() { //Test No 1 Node *tree = newNode(1); tree->left = newNode(2); tree->right = newNode(3); tree->left->left = newNode(4); tree->left->right = newNode(5); tree->random = tree->left->right; tree->left->left->random = tree; tree->left->right->random = tree->right; // Test No 2 // tree = NULL; // Test No 3 // tree = newNode(1); // Test No 4 /* tree = newNode(1); tree->left = newNode(2); tree->right = newNode(3); tree->random = tree->right; tree->left->random = tree; */ cout << "Inorder traversal of original binary tree is: \n"; printInorder(tree); Node *clone = cloneTree(tree); cout << "\n\nInorder traversal of cloned binary tree is: \n"; printInorder(clone); return 0; } 

   
   
   
   
5. Task 3

   Solution option with directed acyclic graph:
   

    // C++ DFS solution to schedule chapters for reading in // given days # include <iostream> # include <cstdlib> # include <climits> # include <cmath> using namespace std; // Define total chapters in the book // Number of days user can spend on reading # define CHAPTERS 4 # define DAYS 3 # define NOLINK -1 // Array to store the final balanced schedule int optimal_path[DAYS+1]; // Graph - Node chapter+1 is the sink described in the // above graph int DAG[CHAPTERS+1][CHAPTERS+1]; // Updates the optimal assignment with current assignment void updateAssignment(int* path, int path_len); // A DFS based recursive function to store the optimal path // in path[] of size path_len. The variable sum stores sum of // of all edges on current path. k is number of days spent so // far. void assignChapters(int u, int* path, int path_len, int sum, int k) { static int min = INT_MAX; // Ignore the assignment which requires more than required days if (k < 0) return; // Current assignment of chapters to days path[path_len] = u; path_len++; // Update the optimal assignment if necessary if (k == 0 && u == CHAPTERS) { if (sum < min) { updateAssignment(path, path_len); min = sum; } } // DFS - Depth First Search for sink for (int v = u+1; v <= CHAPTERS; v++) { sum += DAG[u][v]; assignChapters(v, path, path_len, sum, k-1); sum -= DAG[u][v]; } } // This function finds and prints optimal read list. It first creates a // graph, then calls assignChapters(). void minAssignment(int pages[]) { // 1) ............CONSTRUCT GRAPH................. // Partial sum array construction S[i] = total pages // till ith chapter int avg_pages = 0, sum = 0, S[CHAPTERS+1], path[DAYS+1]; S[0] = 0; for (int i = 0; i < CHAPTERS; i++) { sum += pages[i]; S[i+1] = sum; } // Average pages to be read in a day avg_pages = round(sum/DAYS); /* DAG construction vertices being chapter name & * Edge weight being |avg_pages - pages in a chapter| * Adjacency matrix representation */ for (int i = 0; i <= CHAPTERS; i++) { for (int j = 0; j <= CHAPTERS; j++) { if (j <= i) DAG[i][j] = NOLINK; else { sum = abs(avg_pages - (S[j] - S[i])); DAG[i][j] = sum; } } } // 2) ............FIND OPTIMAL PATH................ assignChapters(0, path, 0, 0, DAYS); // 3) ..PRINT OPTIMAL READ LIST USING OPTIMAL PATH.... cout << "Optimal Chapter Assignment :" << endl; int ch; for (int i = 0; i < DAYS; i++) { ch = optimal_path[i]; cout << "Day" << i+1 << ": " << ch << " "; ch++; while ( (i < DAYS-1 && ch < optimal_path[i+1]) || (i == DAYS-1 && ch <= CHAPTERS)) { cout << ch << " "; ch++; } cout << endl; } } // This funtion updates optimal_path[] void updateAssignment(int* path, int path_len) { for (int i = 0; i < path_len; i++) optimal_path[i] = path[i] + 1; } // Driver program to test the schedule int main(void) { int pages[CHAPTERS] = {7, 5, 6, 12}; // Get read list for given days minAssignment(pages); return 0; }