20 MCQs + 2 Coding Questions:
MCQs based on Data Structures like binary trees, arrays and OS concepts.
Coding quesiton of low level difficulty shouldn't be a problem if you are regular in competitive coding.
Here are the questions they asked:
Note: Optimized solution is desired.
2 easy Coding Questions were asked:
They desire you to come up to the most optimized solution starting from the least optimized one.
1. Given a number in how many ways can it be reduced to 0.
Rules for reduction
1. subract by 2
2. subract by 3
3. subract by 5
this is silimar to coin exchange problem. http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
2. Given a binary tree print its left view. http://www.geeksforgeeks.org/print-left-view-binary-tree/
1 Coding quesiton and 1 Alogrithm design question
The interviewer asked me what was my favourite data structure out of linked list, trees and graph.
I said linked list. This is what he asked, http://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/
Algorithm design quesiton:
The question goes like this:
As you all know amazon is gigantic e-commerce platform having a number of sellers and and buyers.
Each seller has his list of favourite customer(s) and vice-versa. I was required to come up with an algorithm which would make pair of buyer and customer such that both are favourite of each other.
I gave him my initial approach. I said it will not always be possible to do such pairing.
Then I suggested that I will maintain a NxN matrix which will have 1 if both buyer and seller likes each other or 0 otherwise.
Then choose the row(column) with least number of 1,s and choose any one of the 1's and make all other 1's in that row and column to 0, repeat this for all other rown(columns). I was not sure whether my solution was correct but the interviewer seemed to be satisfied.(Luckily he didn't ask me to code this one :P)
In this round I was asked 1 coding quesiton and some questions on trees.
Here is the coding quesiton http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/
After discussing the solution from the most in elegant solutoin using arrays to the most effecient one using heaps he asked me to code the solution.
In my code there were some redundant code he pointed me those and advied me to avoid doing such things as this will affect he code quality.
After that the discussion was on trees:
He gave me an in-order traversal and post-order traversal of a BST and asked me to construct the BST.
I tried deducing an algorithm for it but ultimately came to the conclsion that it is not possible as ther there is no way we could figure out the root ement around which we could split the given input for its left and right subtree
1 Coding quesiton and Questions on OS
This is how the question goes you are given a string of 'I' and 'D'(length upto 8)
'I' = increasing, 'D' = decreasing
So according to the string you have to output a series of numbers which satisfy the following conditions
let s(length n) be the input string and op[n+1] be the output array
if s[i]='I' then op[i]<op[i+1]
if s[i]='D' then op[i]>op[i+1]
There could be multiple answers and you need to output the array which has the minimum lexiographic value
suppose s=III then op could be [1 2 3 4], [2 3 4 5], .... [6 7 8 9]
since [1 2 3] has the minimum lexiographic value so it is the answer
suppose s=DIDII then op=[2 1 4 3 5 6]
NOTE: Each digit is used only once.
He then asked me the most naive solution which has a time complexity of O((N+1)!).
After he gave his O(N^2) solution and asked me to optimize it further and I gave him an O(N) soulution.
I coded the solution, however I forgot to decrement one of the loop counters after the inner loop but he noticed that bug in my code but he didn't allow me to correct it.
After this he asked questions on operating systems.
1.What is a process?
2.What is a therad?
3.What is the difference between them? Their advantages and disadvantages over each other.
4.Process and therad scheduling algorithms
5.What is deadlock? Why is it happens?
6.How to prevent them?
After that we discussed about my internship
If you want a placement/internship at amazon start doing competitive coding or be ready to mug up entire geeksforgeeks.org.
And don't panic during the interview the panelists are very friendly. If you are struck at a point or did not understand the question properly ask them multiple times. Also dont hesitate to discuss even the most lames't solution and don't be mum keep on speaking to the panelist what are you currently thinking this shows that you are making some progress and sometims the panelist me give some hints without even you asking for it. Of course you can always ask for some hints here and there.
After each round the panelist asks you whether you have any questions make sure you utilise this opportunity and ask some relevent questions this will help you learn more about the firm and the working conditions there.
Prepare atleast one of these subjects really well operating systems, computer networkng and DBMS.