Amazon Interview Questions

Excerpts from Interview #1:

• You’re given a Boolean 2D matrix, can you find the number of islands?
• Given an array of strings, find if the given strings can be chained to form a circle. A string X can be put before another string Y in circle if the last character of X is same as first character of Y.
• Tell us an efficient data structure for minimizing the following operations if we have an array arr[0 . . . n-1].
• Add a value x to array from index l to r where 0 <= l <= r <= n-1
• Find the value of a specified element of the array arr[i] where 0 <= i <= n-1
• Is {a, n, d} a palindrome? If you are given a random string, is it a palindrome or not?
• Questions on Implementation of AVL tree.

• Why do you want to be a part of Amazon?
• What makes you better than other candidates here?
• What are your short term & long term career goals?
• Use only 3 words to describe yourself.

Excerpts from Interview #2:

• Given a linked list, reverse K nodes in it.
• Search for an element in an array which has elements who’s values are first increasing and then decreasing. (Use modified binary search)
• Find the second largest element in an array.
• Given a sorted array which can have repeated elements, find the occurrence of an element. (Most optimal solution is O(log n) – Using binary search to find start and end occurrence)
• Make a data structure and implement an algorithm to print all the files in a directory. (The root directory can have sub-directories too.)
• Convert a BST into a DLL and DLL to BST in place.
• Vertical traversal of a Binary Tree.
• Lowest Common ancestor in a Binary Search Tree and Binary Tree.
• Implement a stack with push (), pop() and min() in O(1) time.

• Why should we hire you?
• Tell us your weaknesses that hinder your work? How will you overcome them if we hire you?
• Are you comfortable with changing cities for the job?

Excerpts from Interview #3:

• Given in facebook find an efficient way to find the mutual friends between you and one of your given friends. Hint: hashing, dictionary data structure implementation
• For two very long numbers given, find the product of these numbers in an efficient way. Hint: using binary multiplication effectively.
• Given a number n, find the number just greater than n using same digits as that of n.
• Given n coins for two players playing a game. Each player picks coins from the given n coins in such a way that he can pick 1 to 5 coins in one turn and the game continues for both the players. The player who picks the last coin looses the game. You have to tell that for given n coins who looses the game?

• Do you know someone working in Amazon?
• How did you come to know about Amazon?
• Any queries?

Excerpts from Interview #4:

• Convert Binary tree to linked list.
• Rotate a matrix by 90 degrees.
• What is the definition of tree ?
• What are the differences between graph and tree?
• When can you say a graph to be a tree?
• Write a program to show whether a graph is a tree or not using adjacency matrix.
• Given two numbers represented by two linked lists, write a function that returns sum list.
• Some stack based questions like stock span problem, next greater element.
• Some Dynamic Programming problems like maximum sum subarray, maximum sum subarray such that no elements are consecutive, edit distance, assembly line scheduling.

• Tell us about yourself.
• What inspires you to be part of the Amazon family?
• What is your dream company?

Excerpts from Interview #5:

• He asked me the worst case complexities of Quick sort and Merge sort.
• Given an array that contains post-order traversal of a binary tree. Can you construct a single tree? I said no. Then he asked if i can make a binary search tree from the array to which i said yes. Then after discussing the approach, he asked to write the code.
• Then he asked me to write the code for level-order traversal of a tree. Also asked me to calculate the complexity of the code.
• Given a linked list placed in memory, what problems can arise if simultaneous operations are performed on the list. From here he started asking about threads because the answer was related to it.
• What steps are taken when the OS shifts from one-thread execution to another?

• Why Amazon? How is it different from its competitors?
• Why do you want to leave your current company in such a short interval?
• Did you ask your current company to provide that type of work as you are looking for in Amazon?

Excerpts from Interview #6:

• What do you mean by constant time complexity?
• What do you mean by hashing?
• What is the function of DML Compiler?
• State at least four kinds of indexing?

• Describe yourself.
• Why did you apply for Amazon?
• What did you buy via online shopping last time?
• Name the founder of Amazon.