1st Round
Q1 – Clone a graph. ( Similar Question -> https://www.geeksforgeeks.org/clone-linked-list-next-arbit-pointer-set-2/)
Basically while cloning, when you create a new node in the cloned graph, have a hashmap which maps the old node to new node.
So in the hashmap key = old node, value = new node.
Q2 – Given an array of numbers, for each number print the first number to it’s left which is greater than the current number.
Example
Input -> 5,3,2,4,8,6
Output-> -1, 5,3,5,-1,8
Use stacks. Simple O(n) solution.
2nd Round
Q1 – Find the row number according to the excel nomenclature –> (the opposite of this, https://www.geeksforgeeks.org/find-excel-column-name-given-number/)
i.e given Z, Output -> 26
Given AX, Output -> 50
Q2 – Find the number of islands in a 2d Array -> https://www.geeksforgeeks.org/find-number-of-islands/
3rd Round(Hiring Manager)
Q1 – Given a number in words, print the number.
Example 1) Input - "One Hundred and Five", Output should be "105"
Example 2) Input - "One Thousand and two hundred", Output should be "1200"
Example 3) Input - "Twelve hundred", Output should be "1200"
Example 4) Input - "Five Lacs", Output should be "500000"
Example 5) Input - "Five Hundred Thousand", Output should be "500000"
There were a lot of edge cases, and discussion with regards to this. ( I took a lot of time and the manager did not seem to pleased. )
Q2- In a sorted array, find two numbers who’s difference is k.
Given -> 1,2, 3,4,7,8,9,11 and k=7
Ouput -> 1,8 or 2,9, or 4,11 (Print any one)
https://www.geeksforgeeks.org/find-a-pair-with-the-given-difference/
A lot of questions as to Why Amazon, Why do you want to leave so early.
4th Round(Bar Raiser)
Q1 – Given a sorted array find a number. (Simple Binary Search)
Now consider repetitions and find the left most occurrence. (Binary Search to first find number, then again Binary Search to find left most occurrence)
Similarly find the right most occurrence. (Binary Search to first find number, then again Binary Search to find right most occurrence)
Now using the above two functions, find the number of times the element is present.
Note – Cases like where number is NOT present,
Q2- Assembly Line Scheduling. (Very Simple DP.)
https://www.geeksforgeeks.org/dynamic-programming-set-34-assembly-line-scheduling/
Result
After three weeks, I got a generic email saying that I could not clear it. I had a really irresponsible recruiter who did not have the courtesy to give me a call and just convey some feedback. Eventually, I think I took too much time with the first question in the manager round.