Amazon Interview (on-campus - Software Dev Engineer) with answers/solutions

Round 0 (online):There was online test for 300 students. 25 were selected for interviews. There were 4 back-to-back rounds on the same day.

Round 1:
1. Given 1 billion integers. Find 100 maximum integers. Memory available is insufficient to store 1 billion integers.

Solution: Use a min heap of max size 100 (remember, heap can be implemented using array as it is a full binary tree). Compare every integer with value at 'root' of heap.

if element>root_value

remove root from heap.

insert element in heap.

Do this for all integers.

2. Given array of N integers ranging from 0 to N-1. Output maximum repeating integer. Use only O(1) memory.

Solution: Sort the array. Traverse from start to end. At every element, store the frequency of max repeating elem in a 'separate variable'. Update the variable whenever frequency of current element exceeds the value of the 'separate variable'.

Round 2:
1. An array of integers is given such that it is first ascending and then descending. Find index of some given integer in that array. Ex. 2,4,6,8,7,5,4,3. Input: 4. Output: 2, 7. Write code on paper.

Solution: Similar to binary search, when comparing with [middle] element of array, check for arr[middle-1]<=arr[middle]<=[middle+1]. If this check is ok, continue as usual with binary search, otherwise modify algo accordingly (I think simple enough).

2. Two sorted arrays are given. Find median when both arrays are merged and sorted. Write pseudo code on paper. Take care of boundary conditions.

Solution: This is simple. Try to figure out yourself. If stuck, Check this out: http://www.geeksforgeeks.org/median-of-two-sorted-arrays/

Round 3:
Basic OS, DB concepts.

1. You are given some integers. Propose a data structure to implement “add”, “delete”, “fetch” and “fetch any” operations. All four operations must complete in constant time.

Solution: Dynamic array will work for add, delete and random access. (What is 'fetch any' ? Comment and I will answer accordingly).

2. There is a B-tree with two type of nodes A and B. Return nth A or nth B while doing inorder traversal in O(1) time. And write pseudo code on paper.

Solution: Keep two dynamic arrays. While doing inorder-traversal, store A's in arrA, B's in arrB. After this preprocessing, queries can be answered in O(1) time.

Round 4 with manager:
There is very huge text file consisting several rows and columns of integers. Memory available is not sufficient to store whole text file. One column can be stored in memory. Sort whole file corresponding to given column keeping all rows unchanged. You cannot make new text file. Write neat code on paper.

Solution: Read whole column. Heap sort (saves memory). Now you know old indices and new indices. Shift entire rows from old index to new index. Keep one row in temp storage to avoid overwriting.

This article was taken from GeeksforGeeks.org, here.