Round 1: (Paper Coding)
Q1. A person is standing at the center(0, 0). He is facing north(N). There can be 4 possible commands – Turn left, Turn right, Move ahead, Move back. Find the final coordinates after a set of instructions. This is an easy implementation problem.
Q2. Find longest palindromic sub string in a given string. This can be approached top-down or bottom-up (DP).
I had to wait 3 hours for the result of this round. Every round was an elimination.
Q1. Given a binary tree. Find if there is path from root to leaf with given sum X. After I answered the question, interviewer asked me to print all possible paths for the previous problem.
Q2. Given a binary tree. Add links in binary tree in such a way that all the nodes on a level form a linked list.
Interviewer asked me if I have any questions.
I was given a brief overview about the team for which hiring is going on – Amazon Payments Team.
Q1. This was somewhat related to modified spiral traversal. I can vaguely describe the problem as printing even level nodes (starting node 0) right to left and odd level nodes left to right. Also, the order of printing levels is – 0, 2, 1, 4, 3 …
Q2. This was a question related to data structure design where interviewer told me that I just need to explain different approaches. Lets say DJ is using an application (something like Amazon Music) where he is getting requests from people and then he is picking Nth popular song among current requests. There are two functions – GetRequest() and NthPopular(). Discussed different approaches to store song requests and then ways to retrieve Nth popular by checking count. In these types of questions, it is very important to clarify the requirements and then start discussion.
I must say that interviewer was very supportive.
Brief introduction about myself.
Q1. Given a binary tree, a node N and distance K. We need to find count of all nodes which are at distance K from N.
Q2. A matrix is sorted row-wise and column-wise. We need to find if a number N exist in this matrix. I gave a O(MlogN) solution. We were already running out of time, so she hinted me and then I was able to come up with O(M+N) solution.
The person interviewing me was senior development manager of some other team. Also, I had a feeling that this is a bar-raiser round.
I was asked to introduce myself. Then he asked me about projects in my current company. There were few questions like – Tell me about your most challenging work. Was there a situation where you faced any conflict and how did you resolve it? Was there a situation where you took initiative to do something? These questions are asked to examine Amazon’s principles. Also, in this round, you are the one who is actually driving the interview. The moment you use a term, you can be asked different questions on it. The entire discussion took 1 hour.
Then, there was a programming question – counting all pairs in an array whose sum is X. I answered an approach which stores count (maps) of all numbers and checking the count of (X-num) where num is an array element and then doing calculations. It appeared to me that he was not expecting this answer. Then I answered the approach of maintaining two pointers – start and end. He said I could code any of the approaches. I coded the second approach but missed one test case.