## Amazon Interview Questions

- 0of 0 votes
Sort two sorted Linked Lists.

Write your own implementation of structs / classes you might need to use.

Try to come up with the best time and space complexity.

I ran out of time after merging the two lists in O(n) time and O(1) space, but I am guessing he wanted to expand the solution to implement a merge sort algorithm for an unsorted Linked List.

- 0of 0 votes
write boundary test cases for whether a linked list is circular linked list or not?

- 0of 0 votes
Write a java program logic to find whether list is circular

linked list or not?

- 0of 0 votes
given a pre and post order kindof a traversal (2 arrays) create an n-ary treee out of it with struct of the form :

struct node {

int data;

struct node *child[MAX];

int child_num;

}

- 0of 0 votes
given matrix like :

a b e d

b c f e

a b d d

….

find the longest path of consecutive alphabets given a starting alphabet. You can move in all 8 directions. for eg. a->b(right)->c(down)->d(diagnal down)… len = 4 , find max such len

- -1of 3 votes
20

/ \

8 22

/ \ / \

5 3 4 25

/ \

10 14

traverse this binary tree vertically and its output will be

5

8 10

20 3 4

22 14

25

- 0of 0 votes
Implement the divide of two integers without using the divide operator.

After implementing the O(n) algorithm to subtract the divisor from the divider, he asked me to implement a better algorithm.

I started working towards bit manipulation, but ran out of time.

He also hinted that I could have used binary search. Not sure how though.

- 0of 0 votes
Given a stack of magazines create an anonymous love note (pick words or alphabets from the magazine and create the note)...

He gave me the choice of handling words or alphabets

Assume you have a scanned copy of the magazine as a string.

Once I implemented both words and alphabets, he asked me to scale it to mass production and maximize the throughput of a fulfillment center handling this

- 0of 0 votes
Design a robot that will take your order and make sandwiches for you.

Once I was done with this, I was supposed to extend it to have multiple robots doing this job like an assembly line handling multiple sandwiches and other edible items

Once I handled that, he asked me to create a web service for this that will handle online ordering. He also wanted me to implement fulfillment centers

- 0of 0 votes
A batch of time intervals like {2/3-2/20, 2,6-3/5}. need to split the intervals to{2/3-2/6, 2/7-2/20, 2/21-3/5}. Solve it with minimum time complexity. How to do it?

- 0of 0 votes
Given a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.

- -10of 10 votes
singly link list

- 0of 0 votes
Describe Class diagram of a Card Game like Poker. What classes to be used. How to deal and shuffle the cards in cards class

- 1of 1 vote
Give you a list of Modules of Dependencies,

A --> B,C

B --> D,E,F

D --> F

And please return back a correct build order of Module (input)

- -4of 4 votes
Shorten a List of Strings.

- 0of 0 votes
Design a Black-Jack poker game

- 2of 2 votes
Give an 2d-characters Grid, char[][] A, and a dictionary, List<String> dict. Search all possible words in the 2d-Grid.

- 1of 1 vote
Take a list of integers (left to right order) and return an integer of the number of identical binary trees that can be created from the same list.

Input: [10, 8, 15, 6, 9, 4, 5]

Output: 24

Input: [12, 6, 19, 15, 5]

Output: 6

Input: [44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 64]

Output: 1

I wrote a brute-force 'solution', creating a binary tree for each permutation of the list (with the same root as Input list) and compared each to the binary tree from the Input list. For large input lists (length > 10), my 'solution' is way too slow.

- 0of 0 votes
Given two strings. Figure out if 2nd one is substring of 1st one. 2nd may contain wildcard characters like '*','?' etc

- 0of 0 votes
Write a recursive function to print directory structure. Two function were given isfolder() and openfolder().

- 0of 0 votes
What data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc.

- 0of 0 votes
finds a domino pattern for a "double-N" domino set that forms a loop / a ring using all available tiles.

for example,In a double-two domino set, with six tiles, (0 , 0) (0 , 1) (1 , 1) (1 , 2) (2 , 2) (2 , 0). So if parameter is 2, the function should return true. if no loop found, should return false.

Dominoes are small rectangular game tiles divided into two squares and embossed with dots on the top surface of the tile. You can think of dots as integers. A double-N domino set consists of (N+1)(N+2)/2 tiles, e.g. a standard double-six domino set has 28 tiles (T): one for each possible pair of values from (0.0) to (6.6) - no pair of numbers occurs more than once.

- 0of 0 votes
Input a matrics, print the elements one by one:right->left down->left->up. The 1st line is the matrics size, then follows the matrics elements. Ex:

5 3

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

First loop:

starts from the top left '1';

1: to right, print 1,2,3,4,5

2: to left down, print 9,13

3: to left, print 12,11

4: to up, print 6 ('1' has been print, ignore)

Second round:

1: to right, print 7,8

2: no more elements to print

So the elements should be:

1,2,3,4,5,9,13,12,11,6,7,8

- 0of 0 votes
We have a class as follows:

`public class People{ String name; String position; String sex; ... ... public String getAttribute(String attrName){ /** * This is a generic getter method that will give you * any attribute value based on the passed attribute * Name; * for eg: getAttribute("name") => will return the * attriute(Name) value of the current object. */ } }`

I now give you two List:

list1<People> friends;

list2<String> attributes;

Using the generic getter method, we have to group "friends" on "attributes". Think of this as an implementation of GROUP BY function to be implemented on objects in list1 and to be grouped on entries in list2.

eg: list2 = {sex, occupation}

So objects in list1 will be grouped such that all Male-doctors together, Female-cops together, male-cops together, etc.

- 1of 1 vote
Given an array of type:-

1. Increasing

2. Decreasing.

3. Increase-Decrease

4. Decrease-Increase

Find:- 1. Type of array in minimum steps ?

2. Maximum element from array in min steps?

- 1of 1 vote
You have 81 balls. 80 balls have the same weight. 1 ball is the lightest one. What would be the minimum possible way to find the lightest ball ?

(Use Dynamic Programming)

- 2of 2 votes
Given a large array of unsigned ints, quickly find two who's sum is 10

Then the interviewer asked me to write test cases.

Followed by how to implement this on a distributed system, where multiple systems can read/write simultaneously on a shared cache (HINT: It is ok if you do not return the first instance)

- 0of 0 votes
In a city year of birth/death of people who where born and died between year 1900 to 2000 are given. Write an algorithm to find the year in which max people were alive.

- 1of 1 vote
Minesweeper question: Given an n x m grid holding individual mine co-ordinates, identify all of the mine clusters. A mine cluster is the largest collection of neighboring mines.

Example input:

0 1 2 3

---------

0|0|1|0|1

1|0|0|1|1

2|0|0|0|0

3|1|1|0|0

Expected output:

[cluster 1] (0,1),(1,2),(1,3),(0,3)

[cluster 2] (3,0),(3,1)

- 0of 0 votes
`6 / \ 3 5 / \ \ 2 5 4 / \ 7 4`

There are 4 leaves, hence 4 root to leaf paths:

Path Sum

6->3->2 632

6->3->5->7 6357

6->3->5->4 6354

6->5>4 654

Answer: 632+6357+6354+654=13997