Company : **Amazon**

CTC: 16.5 LPA

**Round 1: Online Round (90 mins):**

1. 20 MCQ

2. 2 coding questions

• Find the diameter of a tree

• Print all anagrams pair in separate line

**Round 2: (PI 1)**

Find the next larger element in a BST, given key might not be in the BST. O(logn) time and O(1) space.

Delete all nodes on a DLL whose data is a multiple of 5. O(n) time

**Round 3: (PI 2)**

1. Given n-ary tree, print the nodes in level-order zig-zag manner. O(n) time

2. Given a BST find the number of pair of nodes which sum upto a given value. O(n) time, O(1) space.

3. Given a 2D plane and n points, find the line which passes through maximum number of lines.

4. If a/b is recurring like 10/3 print 10/3 as 3.(3), 16/6 as 2.(6)

**Round 4: (PI 3)**

1. Explain caching, implement LRU caching.

2. Explain working of DNS, implement domain search in DNS.

3. What is hashing. Implement domain search using hashing.

4. Given a string of alphabet of at most 5 characters. Write a function which returns a unique number for each string with O(1) space.

5. Explain working of virtual function.

6. There is pointer of base class pointing to derived class. Explain the working with respect to the pointer, if this pointer calls the virtual function of base class.

7. How does write head take a value from process buffer and writes on a particular address (Explanation of address bus and register needed).

**Round 5: (PI 4)**

1. Clone a linked list having an arbit pointer.

2. You are given deque(), enque(), isEmpty() function for queue, implement push(), pop(), min() functions of stack. O(1) time was required for min().

3. Convert a binary tree to a DLL such that a next node for DLL is selected in a top down order in zig-zag manner. O(n) space was allowed, but not O(2n).

If you would like to contribute, mail us your interview experience at [email protected] We will like to publish it on CrazyforCode and help other job seekers.