Amazon Interview Questions
 0of 0 votes
An employee class has id, name and a vector of employees who reports him. Given two employees find the common manager of them.
 0of 0 votes
Given two Binary Trees (not BST). Each node of both trees has an integer value. Validate whether both trees have the same integers, there could be repetitive integers.
ex
Tree1:
5
1 6
5 4 3 6
Tree2:
1
3 4
6 5
have identical integers.
 1of 1 vote
Given a string which may contain parenthesis. We must verify the validity of the string.
ex
1) "<ad675+fkmfd>" is a valid string
2) "<[((kskfhdbh7)" is invalid
3) "[<<((shfs8))>>]" is valid
Extension to the question 
Suppose you had a hash table that told you how a parenthesis starts and how it ends as a key value pair, how would you then validate the string.
ex  <key,value> = < '(' , ')' > indicates '(' is a start parenthesis and ')' should be the end of that paranthesis.
<'A','&'> indicates that 'A' is a start parenthesis and '&' is the end parenthesis.
Note: Validity means a parenthesis that starts, must end.
 1of 1 vote
Find the largest substring palindrome in a given string.
ex: input: abbac output: abba
Solution: Use Hashmap
 0of 0 votes
Given a grid of m*n size. Each block in grid has some amount of gold.
We start from first column of the grid(any row) and we can move in 3 direction  right, rightup and rightdown.
What is the maximum amount of gold we can collect from the grid.
 1of 1 vote
Print first and last node of all the levels of a tree.
Ex if tree is 
root>data = 1
root>left>data = 2
root>right>data = 3
root>left>right>data = 4
root>right>right>data = 6
root>right>left>data = 5
root>right>left>left>data = 7
root>right>left>left>right>data = 8
Output  1 2 3 4 6 7 8
 0of 0 votes
The truck monitoring app is installed on the truck driver's phone. This app sends the
location info back to the truck supervising application. there is a supervisor who monitors
the route, drop off locations and time for the trucks from the head office to make sure the
SLA's with the vendors(time, location, goods sign off) are honored. List the test cases and
certify this application
 1of 1 vote
3. Implement a function that returns the ith most popular item sold at Amazon. You cannot rely on any libraries.
class Item {
String itemId;
int quantitySold;
}
/**
* Find the ith most popular item in the list.
*/
String find(List<Item> items, int i) {
// your code goes here
}
 1of 1 vote
2. Suppose you are given a puzzle that is represented as a matrix with 0s and 1s, where a 0 indicates you’re allowed to move into that position and 1 means you’re not allowed to move in that position. Write a function that given a start position and an end position, returns a boolean value indicating if there exists a path from start to end. You are only allowed to move up, down, right or left. Diagonal movement is not allowed.
Example #1
Input
0 0 1 0 1
0 0 0 0 0
0 1 1 1 1
0 1 1 0 0
start: 4,1
end: 0,3
Output
true
Example #2
Input
0 0 1 1 1
0 1 0 0 0
1 1 1 1 1
0 0 0 0 1
start: 0,0
end: 1,2
Output
false
Example #3
Input
0 0 1 1 1
0 1 0 0 0
0 1 1 1 1
start: 0,0
end: 2,1
Output
False
class Position {
final int x, y;
public Position(final int x, final int y) {
this.x = x;
this.y = y;
}
}
boolean pathExists(int[][] puzzle, Position start, Position end) {
// your code goes here
}
 0of 0 votes
1. Write a function that removes the duplicate of a collection of numbers and returns the number of elements remaining in the collection after the duplicates have been removed. You must ensure that duplicates are actually removed from the list.
Example #1
Input
{1, 1, 5, 3, 8, 3, 7, 32, 32}
Output
6
Example #2
Input
{21, 10, 24, 2, 21}
Output
4
int removeDuplicates(List numbers) {
// your code goes here
}
 2of 2 votes
Given three arrays A,B,C containing unsorted numbers. Find three numbers a, b, c from each of array A, B, C such that ab+bc +ca is minimum.
 0of 0 votes
Given a 2D matrix which contains 0’s and 1’s. Given two points of matrix whose value is 1. Find the path(with only 1’s) between the given points
 0of 0 votes
There is a graph which represent average number of days the defects spent in status over a
duration of time say in progress, ready for Qa etc. For example the X asis of the graph
will project the daily/weekly/monthly duration and the y axis would be the count of days.
List the test condtions to test and certify this graph
 0of 0 votes
A registration form, to get user details has phone number field. This field is javaScript
validated to get only numbers as input. But internally in the database they are stored as
text. Do think there is an issue ? High/Medium/Low ? Justify
 0of 0 votes
The client sends a string to server and the server respnds with the same string appended
with date and time. List down the tests
 0of 0 votes
Kth largest element
Consider that there are 2 lists that contain numeric values S1 and S2. the developer has
written a program to find the kth largest element in the merge of two sorted sequences S1
and S2. The developer has written a program implementing the same. List down the test
conditions to test and certify
 0of 0 votes
The truck monitoring app is installed on the truck driver's phone. This app sends the
location info back to the truck supervising application. there is a supervisor who monitors
the route, drop off locations and time for the trucks from the head office to make sure the
SLA's with the vendors(time, location, goods sign off) are honored. List the test cases and
certify this application
 2of 2 votes
Given an array of strings with only lowercase letters , create a function that returns an array of those same strings, but each string has its letters rearranged such that it becomes a palindrome (if possible, if not, return 1)
 0of 0 votes
Connect nodes at same level of a binary tree recursively using O(1) space (we can ignore stack space used for recursion)
Tree node is like following.struct node { int data; struct node* left; struct node* right; struct node* nextRight; }
Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node. You can use only constant extra space.
 2of 2 votes
In a string detect the smallest window length with highest number of distinct characters. For eg.
A = “aabcbcdbca”, then ans would be 4 as of “dbca”
 0of 0 votes
How would you implement Xray for Kindle? Xray is an index of characters in a book that shows how often a character appears in the book, and at which places. I was explained how this index works, and what it will look like on the book. There re more details here: http://www.amazon.com/gp/help/customer/display.html?nodeId=200729910
 0of 0 votes
Given two strings, return true if they are one edit away from each other, else return false. An edit is insert/replace/delete a character.
Ex. {"abc","ab"}>true, {"abc","adc"}>true, {"abc","cab"}>false
 0of 0 votes
Given a linked list and a positive integer n, reverse the order of nodes in between n and last but n nodes.
example: 1>2>3>4>5, n=2. Output is 1>4>3>2>5
 0of 0 votes
Given a postfix expression as a string, evaluate it and return the result. example : "423+*" >20. The Postfix expression is well formed(need not check for bad expression)
 0of 0 votes
Find the total number of connected components in a graph (there can be forests)
 0of 0 votes
Given a 2dimensional square matrix, rotate the matrix clockwise. Imagine concentric circles. Input from stdin: first line is length, subsequent lines are rows of the matrix. Output the matrix to stdout. This was one of the questions. You have 2 hrs to complete it.
 4of 6 votes
/**
You have list,which contains a DS(Data Structure) which have a list and a value (basically a list of list).
You need to write an iterator such that it will iterate over the numbers/integers whenever a .next() is called
1>2>3>4

6>7>10
 
8>9 11>12
Output
1 .next() > 1
2..next() > 6
3..next() >7
4..next() >8
5..next() >9
6..next() >10
7..next() >11
8..next() >12
9..next() >2
10..next() >3
11..next() >4
12..next() > throws Exception
**/
 0of 0 votes
BST is given.
Calculate and return array with a sum of every level.
For example,
1
2 3
4 5 1 2
Output should be [1, 5, 12].
 0of 0 votes
Company will start a new marketing campaign targeting the users according
to their purchasing profiles.
This campaign has 3 kinds of messages each one targeting one group of customers:
Message 1  targets the 25% of customers that spend most at the site
Message 2  targets the 25% of customers that spend least at the site
Message 3  targets the rest of the customers.
Given the list of purchases made during the week, write a program that lists
what kind of message each customer will receive.
Each purchase in this list features the customer id, the purchase amount among other information.
 0of 2 votes
A string contains az, AZ and spaces. Sort the string so that all lower cases are at the beginning, spaces in the middle and upper cases at the end. Original order among lower and upper cases needs to remain the same. For example: a cBd LkmY becomes ackm BLY. Is there a way in O(n) without extra space?