Hi All,

Some time back, I appeared in an interview with Amazon and had a really good experience. Though, I couldn't make it, it was the best interview experience I have ever had. My interview consisted of 7 rounds, 2 telephonic and 5 on-site interview @ HYD. Here are questions from my interviews. I am not able to recall some more questions but that were not hard to crack else I must be able to recall those :)

1st Telephonic:
1)
Convert a decimal number in Hexa Decimal. Though there is nothing in the question but he want a production quality code in first go.

2) There is an integer array consisting positive numbers only. Find maximum possible sum of elements such that there are no 2 consecutive elements present in the sum. (solution)

3) There is an integer array consisting positive and negative integers. Find maximum positive difference S defined as:

S = a[i] - a[j] where i>j
and
S > 0
2nd Telephonic:
1)
There is a huge file containing billions of integers. Find maximum 20 integers form that file. (solution)

2) There is an integer array. The array represent a graph which increases till one point and then start decreasing. WAP to find the maximum number in that array. Write production quality code which handles all the scenarios. He also checked various combinations of number with my code.

3)
Write a class for finding next element in preorder traversal of a binary tree. You can't modify the basic structure of tree. Also discuss about your algorithm.

4) WAP for inplace removal of vowels from a char string.

5) Derive formula for finding angle between minute and hour hand of a clock at any given point of time.

1st F2F:
1)
You have millions of image in Amazon's databse. You also have a image with you. You need to find products which have similar image. A long discussion was there on this question. Since I have worked earlier on Image Processing, so I handled the question pretty well.

2) Find an algo for bucket-fill in MSPAINT. A long discussion was there on this too. In the end I won with my argument. He also asked to write pseudo-code.

3) Make a class diagram for thread-pool. Also discuss how to allocate threads for different calls.

2nd F2F:
1)
Given an n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But a node cannot be locked if any of its descendant or ancestor is locked. You are supposed to:

-> write the structure of node
-> write codes for

• Islock()- returns true if a given node is locked and false if it is not
• Lock()- locks the given node if possible and updates lock information
• Unlock()- unlocks the node and updates information.

Codes should be :

• Islock –O(1)
• Lock()- O(log n)
• unLock()- O(log n)

2) An n-ary tree is represented in a matrix form such that A[i,j] = 1 if j is the ancestor of i. Otherwise A[i,j] = 0. Given this construct the tree. (solution)

3) How to store costs for these considering combinations in most efficient manner:
• Source
• Destination
• Courier
• Weight etc
You need to optimize your search. Many question with different considerations.

4) Further questions on 2nd question of 2nd telephonic.

3rd F2F:
1)
At a bus-station, you have time-table for buses arrival and departure. You need to find the mininum number of platforms so that all the buses can be accommodated as per their schedule. Write production code.
Hint: Very simple question, don't think too hard. (solution)

2) Write production quality code to reverse alternate nodes in a link list. Play with pointer, don't swap the values.

Hint: It looks very simple and you can write the code at very first go. But run your code again and again. (solution)

4th F2F:
1)
A very simple puzzle, which has a magic pond where flowers doubles when you dip them in its water.

2) Find all the characters, which are present in the character array given. The order of character should remain intact. (solution)
Ex:
i/p: acdaacbdac
o/p: acdb

3) Find all the patterns once which are present in the character array given. A pattern is a sub-array containg 2 or more chars.
Ex:
o/p: ab, abc, bc, da

5th F2F:
1)
You have a fair coin. Make it unfair with win and loose probability p and (1-p) respectively, where p is greater than 0 less than 1. A long discussion followed on this question.

2) Find nth fibbonacci number in less than 0(n), I couldn't do it. (solution)

3) Write production quality code to find whether a given binary tree is a BST or not. You can't make any global variable.

4) You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. A long discussion about optimization followed.

5) Prime factors of an integer and count of each of those.

Suggestions:They asked a number of question regarding any data structure you use. Like Hash tables, heaps, arrays etc. And also asked comparison between them. So whatever data structures you are using you must be having a sound knowledge of that. Also gather knowledge about sorting and other things. Another input is that Amazon guys don't like to give hints. Though they give hints if you are stuck, but don't count that as good.

PS: This was all what was asked from me in Amazon Interview. Except one question about Fibonacci's, I have done well but unfortunately I couldn't make it. I am thinking of discussing some of these questions in upcoming posts. I have already discussed about 'virtual destructors' here.