Q1. [Microsoft Interview] There is a binary tree, with each node storing its parent pointer as well. Given a pointer to a node in such a tree, you should return the leftmost node in the same level as the given node. Write code and provide test cases to test the same.
A. Pretty much straight forward. Idea: Just move up till you reach the root, and from there drop down to the left most node which would fall into the same level, as the given node. Time Complexity: O(h), where h is the depth of the given node.
Q2. [Microsoft Interview] There is a binary tree, where each node has an extra pointer called 'next' which will be pointing to NULL. Given the root of such a binary tree, fill in the 'next' pointer of all the nodes in the tree in such a way that, the next pointer of a node should point to its in-order successor.
A. Finding the inorder successor for a given node takes O(lg n) time (explained in one of my previous posts). Using that, you can fill in the 'next' pointers in O(nlgn). However, there is a much better way of doing it using slight modification of Morris Inorder traversal.
Q3. [Again, Microsoft Interview] Given an array of integers A, return another array B, whose element 'i' defines the product of all the elements in A except A[i]. That is B[i] should contain the product of all elements in A, except A[i].
A. Yes, multiply all the numbers (say 'product') and store it in a temp variable. And fill in the array B as B[i] = product/A[i]. However, this method will not work if there are more than one zeroes in the array A. An alternative method is take two temp arrays X and Y and fill them as: X[i] = A[0]*A[i]*....A[i-1] and Y[i] as A[i+1] * A[i+2] * .... A[n-1]. Use this to fill in the array B.
Q4. [Google Interview] There are N persons standing in a queue at a store, where each person knows his height and the number of persons who are taller than him. Now, because of the lunch break the queue had dispersed. You job is to reconstruct the queue with the same configuration like it was before dispersion, given that you only know, for each person, his height and number of persons who are taller than him and are infront of him in the queue.
A. Hint: Use recursion:- at each step find the person who should be standing first in the queue.
Q5. {Google Interview] Given a sorted dictionary of the Chinese language and the list of alphabets of the language, find the precedence of the alphabets using the dictionary.
A. Hint: Construct a directed graph with alphabets as nodes and perform the topological sort.
A. Pretty much straight forward. Idea: Just move up till you reach the root, and from there drop down to the left most node which would fall into the same level, as the given node. Time Complexity: O(h), where h is the depth of the given node.
Q2. [Microsoft Interview] There is a binary tree, where each node has an extra pointer called 'next' which will be pointing to NULL. Given the root of such a binary tree, fill in the 'next' pointer of all the nodes in the tree in such a way that, the next pointer of a node should point to its in-order successor.
A. Finding the inorder successor for a given node takes O(lg n) time (explained in one of my previous posts). Using that, you can fill in the 'next' pointers in O(nlgn). However, there is a much better way of doing it using slight modification of Morris Inorder traversal.
Q3. [Again, Microsoft Interview] Given an array of integers A, return another array B, whose element 'i' defines the product of all the elements in A except A[i]. That is B[i] should contain the product of all elements in A, except A[i].
A. Yes, multiply all the numbers (say 'product') and store it in a temp variable. And fill in the array B as B[i] = product/A[i]. However, this method will not work if there are more than one zeroes in the array A. An alternative method is take two temp arrays X and Y and fill them as: X[i] = A[0]*A[i]*....A[i-1] and Y[i] as A[i+1] * A[i+2] * .... A[n-1]. Use this to fill in the array B.
Q4. [Google Interview] There are N persons standing in a queue at a store, where each person knows his height and the number of persons who are taller than him. Now, because of the lunch break the queue had dispersed. You job is to reconstruct the queue with the same configuration like it was before dispersion, given that you only know, for each person, his height and number of persons who are taller than him and are infront of him in the queue.
A. Hint: Use recursion:- at each step find the person who should be standing first in the queue.
Q5. {Google Interview] Given a sorted dictionary of the Chinese language and the list of alphabets of the language, find the precedence of the alphabets using the dictionary.
A. Hint: Construct a directed graph with alphabets as nodes and perform the topological sort.
