Amazon interview Experience | Set 140 (Experienced for SDE)

Hi, Recently i had interviews with Amazon.

1st Round (Telephonic):
1. Given an integer array and a constant number X, print all pair of number in the array whose product is equal to X.
follow ups: how will you do in O(n)? how will you handle duplicate pairs?
Code was required on collabedit.

2. He asked do I know level order traversal of binary tree. He ask me to code then, he changed the question and asked about spiral order traversal of binary Tree and asked me to code it.

2nd Round (Telephonic):
1. In a BST two nodes were swapped. Given the pointer to root node find the two nodes and rectify the tree. He asked the approach then asked me to code the same in collabedit.

2. Given an integer array, find and print three element in the array whose product is maximum. Code was required.

3rd Round (face2face onsite)
1. Given a sorted array of n integers, count and display number of triplets such that a[i] < a[j] < a[k] 0(n) time. Code was required.
2. In a given string some of the characters are replaced by question mark, and you can replace question mark with any character. Given such a string find total number of palindrome that can created. String contains only [a-z] characters and question marks can also be only replaced by [a-z]. Example: Input String: String str=”a??a” Output: 26
3. Given a binary tree all the leaf nodes in the form of a doubly linked list. Find the height of the tree.

4th Round (Hiring Manager Round):
Detailed discussion about previous company work?

Why I want to leave my previous employer?

Why Amazon?

What if I don’t like the work?

What are challenges I have faced in my work, how I resolved it?

Weakness and strength?

What does router do, what is static routing? Given a routing table, how would you decrease the time taken by router to decide to which router packet must be forwarded?

Details of algorithm that could be implemented and discussion time and space complexities.

5Th Round (Face2Face Onsite):
1. Given N sorted LinkList of different length, merge them into a single sorted link list. Pseudo code was required.

2. Given a number d and size of array N. Print all combination of element in the array such that first element of array is d and next element in the array can be +1 or -1 the previous element in the array. Code was required.

E.g. Input: d=4 N=3
Output:
  4 3 2
  4 3 4
  4 5 4
  4 5 6

3. What is LRU and implementation of lru? Write pseudo code for the same.

I would like to thanks w3wiki for providing us such a learning platform.