Amazon Interview of Vaibhav Shukla

Round 1 : Written (Online @ Interview Streets)
Apti , C/OS mcqs(Test your C Skills level) and 2 codes

1. Given a tree, return its mirror image.
2. Given a tree and an integer SUM , return true if there is a root-to-leaf path such that sum of all the node values result to given SUM.

Round 2 : Written 4 coding questions

1. You have a singly linked list where apart from 'next' pointer , each node has a random pointer which can point to anything (either any node or may be NULL).
   Create a clone of this list and return its head. Figure could be helpful.
2. Given an array of the form {a1,a2,a3.....an,b1,b2,b3......bn,c1,c2,c3........cn}
   Write a funtion to rearrange the array in the form {a1,b1,c1,a2,b2,c2,a3,b3,c3..........an,bn,cn}
3. Given a binary tree in which each node has an extra "next" pointer . Populate this next pointer of each node with its InOrderSuccessor
   
   InorderSuccesor of a node is the next node appearing while travering the tree InOrder.
   
   struct node {
       int data;
       struct node *left;
       struct node *right;
       struct node *next;
   };
4. Given a Binary tree , a start node and an integer K, Find/Print all nodes @ distance K from the start node
   function prototype - void findNodesAtK(struct node *root, struct node *start,int K);

Round 3 : Telephonic Interview
He told me that he'll be asking coding questions and puzzles only.His focus was on optimization.

1. 25 horses , 5 can race at one time. Minimum number of races to find three fastest horses.Though its a well known puzzle,he wanted me to code this :P
2. Given a binary matrix where each row has 1s followed by 0.There can also be a row with no 1s(or all zeros) . Return a row with maximum number of zeros.
   Gave two three approach, he wanted me to give optimal solution.From n^2 to nlogn to n .
3. Given a integer array , return maximum product subarray. You just have to return maximum sum.

Round 4 : Face to Face Interview
Again focus was on Coding and Problem Solving Skills

1. There is a town having civilians and a Mayor . You have been given an API bool xKnowsy(x,y) which will return true IFF x knows y.
   Now you have to find the Mayor based on following constraints
        a. Mayor doesn't know any civilian.
        b. Every civilian knows the Mayor.
        c. and between civilian,they may or may not know each other.
   Write a code to find the mayor using the given API.
2. Implement Google's auto-completion feature i.e as you keep on typing characters,you see the sentences or words appearing below.
   Then he modified the problem and said , You have a dictionary having words, every time I type a character,return me the list of top 5 words appearing as in google's search bar.
   For example : if dictionary has words: if,in,info,int,integer,it. Then on typing i , words suggestion would be if,in,it
   then if the next character entered is n i.e now "in" , so possible suggestions are in,info,int,integer
   Again he modified the problem to search the word entered using the same struture that i used for above problem.
3. Few questions on my resume-extra curricular activities. (He was Rajan sir's class mate from RLA :P)

Round 5 : Face to face interview

Mixed questions

1. Performing Big Int Addition using linked lists
      1->2->3
   + 2->1->2
   -------------
      3->3->5
   -------------
   
   The resultant addition linked list has to be returned. He asked me about different test cases that i would be handling.
       a. Linked lists can be of different length.
       b. On adding last to digits, if the carry is there, then one extra node would be there in the resultant
    linked list. and rest basic test cases(NULL check etc).
   Then he modified the problem and asked to solve it recursively. The addition should be done recursively.
2. Given a linked list and an integer K . Reverse the nodes in groups of K.
3. Vaibhav is connected to A,B,C,D on facebook. A is connected to P, P to R and may be other. like wise B->E->F->C. This type of structure was given in which a person may be connected to other, in such a way that there could be more than one path between any two given people.
   Now, given two people. Find the shortest path between the two.
   Note : Don't use Dijkstra's.Actually you can (he wanted something else :P)
4. How TCP verifies that packets are reachng the destination in sequence?
5. Explain the process of page load when you hit www.amazon.com in url bar,in brief.
6. Diff between threads and process. Why are threads called light weight ? What is a system call ? Difference between system call and interrupt.
7. You are moving in an infinite string of words.At any point in time,you'll be asked to stop. Then on whichever word you are, return all the anagrams of that word present in the infinite string.
8. Probability : Given two jars and 50 blue ball and 50 red balls. Distribute the balls in two jars in such a way so as the probability of picking up a red ball is always maximum.

After a month :
Round 6 : Face to Face interview (Algo/DS)

1. A number i is given in its binary form, Find the next greater number than i having equal number of Set bits.
   Example : If i = 011001 , then next greater number with equal number of 1s will be 011010.
   Hint : Try more examples and figure out a pattern.
2. Given an integer Array and a number K , find a Pair (just one) in the array whose sum equals to given K.
   Two three approaches were discussed and he wanted to optimize the solution as much as possible.
   Last constraint was : Without sorting the array, do it in O(n) time.
3. You are given an array of Strings, return TRUE if and only if All the strings can be connected in one chain.
   Condition for connectivity is , if the last character of one string matches first character of second string, the two string can be connected.
   
   Example : String []arr ={"abc", "cde", "cad" , "def" , "eac"} will return TRUE coz all strings can be connected in one chain
   "abc"->"cde"->"eac"->"cad"->"def"
   
   Another Example : String []arr ={"acb" , "cde", "def", "ead" } returns False coz "cde"->"ead"->"def" is the possible chain but "acb" is left out.
   
   Note : Its not necessary to start with the first String and form the chain, It may happen that you won't get a chain if you start with first string but you can get a chain if you Start with any other String. If there exists a possible chain, then your solution should return True.
   
   In the second example , if the first String was suppose "fcb" , then a possible chain would have exists "cde"->"ead"->"def"->"fcb" so True.