## Amazon Interview Questions

- 2of 2 votes
Lets say someone accidentally deleted all the whitespaces from a sentence. Write a program to reconstruct the sentence from that stripped out string. Assume you have access to a dictionary function that returns if a given string is a valid word or not.

Example input: thisisavalidsentence

Output: this is a valid sentence

If multiple solutions are possible, any one valid solution should be given. Assume there is always a valid solution. No invalid input will be given.

- 0of 0 votes
Ideal goal:

Given data set of strings divide them into equivalence classes such that the equivalence relation is fuzzyMatchingOfString

Problem: as far as I know there isn’t a relation function fuzzyMatchingOfString such that it is transitive, i.e. given A,B,C and fuzzyMatchingOfString(A,B), fuzzyMatchingOfString(B,C) does not imply fuzzyMatchingOfString(A,C)

e.g. foo ~ goo and goo~gol but not foo~gol

given that I think we have to compromise about our goal and create a set to each string In our data set – that is n^2 for each run when the basic action is fuzzyMatchingOfString

- 0of 0 votes
Design a deck of cards that can be used for different card game applications.

Please code out what you would need for the deck class and a card class.

Implement a deal method.

- -1of 1 vote
Design unix file system in database.

- 0of 0 votes
Given the following inputs, return a list of rooms that are available and large enough:

# of people

Start Time

End Time

You should return

total list of rooms

capacity of each rooms

availability

- 0of 0 votes
10000 cameras, 100 hours of video each. 30 fps. Police need to input a plate number and find the path of a suspicious vehicle. (Estimate the size of the video, e.g., blueray disc is 2 hours and 20 GB. No need to scan all of the videos. Estimate the time that a vehicle can be seen between 2 traffic cameras, e.g., 0.3 miles and 30 miles per hour, then select 1 out of 100). Web client, load balancer, servers, db.

- -2of 2 votes
Given a number n.find (l X b) dimension such that it is maximally close .

E.g:--

12---o/p->4X3 not 6X2

13---o/p->5X3 // as it is close

- 1of 1 vote
given a LinkedList like 1->2->3->4->5->6

Modify it as:

1->6->2->5->3->4

- -1of 1 vote
The question is in the image.

https://s32.postimg.org/xv0x002p1/mcq_1.jpg

- 2of 2 votes
Swap the elements in Kth position from the start and end of a link list.

ex:

input: list: 1,2,4,5,7,8 & K=2

output: 1,7,4,5,2,8

- 0of 0 votes
Given two strings, print all the inter-leavings of the Strings in which characters from two strings should be in same order as they were in original strings.

e.g.

for "abc", "de", print all of these:

adebc, abdec, adbce, deabc, dabce, etc, etc

- 0of 0 votes
Given a matrix of positive integers, you have to reach from the top left corner to the bottom right in minimum cost. You can only go one square right, down or diagonally right-down. Cost is the sum of squares you've covered. Return the minimum cost.

e.g.

4 5 6

1 2 3

0 1 2

Answer: 8 (4+1+0+1+2)

- 1of 1 vote
Find the length of maximum number of consecutive numbers jumbled up in an array.

e.g.: 1, 94, 93, 1000, 2, 92, 1001 should return 3 for 92, 93, 94

- 0of 0 votes
Given some resources in the form of linked list you have to canceled out all the resources whose sum up to 0(Zero) and return the remaining list.

E.g-->> 6 -6 8 4 -12 9 8 -8

the above example lists which gets canceled :

6 -6

8 4 -12

8 -8

o/p : 9

case 3 : 4 6 -10 8 9 10 -19 10 -18 20 25

O/P : 20 25

- 0of 0 votes
In an incoming stream of +ve integers, return true if 2 numbers with sum equal to 10 has occurred till now.

How to handle stream of numbers

- 0of 0 votes
Given an array,find all valid ip-address form this array.

- 0of 0 votes
An unsorted array is given . Find the no of greater elements on right side on current element in array. Find this for every element of array Expected time complexity is lesser then O(n^2)

- 0of 0 votes
A monotonically increasing function F(X) exists. For a given no N , find the value of X when F(X) = N.

- 1of 1 vote
Given a list of numbers of odd length, design an algorithm to decide whether it's possible to remove any number from the list and split the remaining numbers into two sets of equal length with the same sum.

Example:

Input: [1, 1, 1, 1, 1]

Output: Yes

Input: [1, 2, 2]

Output: No

- 0of 0 votes
How to calculate sum of all numbers in a string. Example 11aa22bb33dd44 =110

Note: Should not use Regex and replace

- 1of 1 vote
A program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35

- -1of 1 vote
This is a interview question which needs to be optimized for time.

Suppose you have a 2 dimensional Array and you have a String say "Amazon" inside the Array such that the individual characters can be present from Left to Right, Right to Left, Top to down and down to up.

I will explain with example :

char[][] a = {

{B,B,A,B,B,N},

{B,B,M,B,B,O},

{B,B,A,B,B,Z},

{N,O,Z,B,B,A},

{B,B,B,B,B,M},

{B,B,B,B,B,A}

};

The above Array has two Amazon Strings. You need to return the count of number of such strings present.

- 0of 0 votes
Find the height difference between two nodes in a binary tree.

`1 2 3 4 5 6 7 8 9 10`

For example: For a given tree above, what would be the height difference between node 4 and node 10?

- 0of 0 votes
Milly and Pranjul are playing a game in which Pranjul will give an index of a chocolate.

Then, Milly has to tell him the box number in which that chocolate is in. There are N

such boxes and Ci chocolates are there in ith the box. Description of index is given below

:

Suppose there are A1, A2 … AN chocolates in 1st, 2nd… Nth boxes respectively. So,

indexing of chocolates in 1st box will be from 1 to A1, similarly in 2nd box indexing will be

A1 + 1 to A2 … and indexing in Nth box will be from AN-1 + 1 to AN.

Milly is blind folded so she can’t see the boxes. You are required to help her.

Input

First line will contain N (No. of boxes). Next line will contain N space separated

integers denoting Ci, the number of chocolates in ith box.

Next line will contain Q (No. of times Pranjul will ask her). Then each next Q lines

will contain the asked index I.

Output

For every query, print in a new line : the box number in which that index of

chocolate is in.

Constraints

1 ≤ N, Q ≤ 105

1 ≤ Ci ≤ 10

1 ≤ Σ Ci ≤ 106

1 ≤ I ≤ Σ Ci

- 0of 0 votes
2. You have logfile for one process, that logfile is updating with heavy logs like never before. What will be cause for logfile to be updating with heavy logs.

- 0of 0 votes
1. If server is slow then tell me what are all the possible ways to trouble shoot to find why the server is slow.

- 0of 0 votes
There is an input log file given as follows-

log = [

{ 'user': 'A', 'page': 1},

{ 'user': 'B', 'page': 5},

{ 'user': 'A', 'page': 2},

{ 'user': 'A', 'page': 1},

{ 'user': 'B', 'page': 2},

{ 'user': 'C', 'page': 7},

{ 'user': 'C', 'page': 3},

{ 'user': 'A', 'page': 3},

{ 'user': 'C', 'page': 1},

]

please implement

discover_site_map(log)

discover_site_map returns a representation of the links between pages, using whatever data structure you think is suitable:

1 -> 2, 3

2 -> 1

3 -> 1

5 -> 2

7 -> 3

How to solve this in C++ and Python?

- 0of 0 votes
You have rating (0-10) of the hotels per user in this format:

scores = [

{'hotel_id': 1001, 'user_id': 501, 'score': 7},

{'hotel_id': 1001, 'user_id': 502, 'score': 7},

{'hotel_id': 1001, 'user_id': 503, 'score': 7},

{'hotel_id': 2001, 'user_id': 504, 'score': 10},

{'hotel_id': 3001, 'user_id': 505, 'score': 5},

{'hotel_id': 2001, 'user_id': 506, 'score': 5}

]

Any given hotel might have more than one score.

Implement a function, get_hotels(scores, min_avg_score) that returns a list of hotel ids that have average score equal to or higher than min_avg_score.

get_hotels(scores, 5) -> [1001, 2001, 3001]

get_hotels(scores, 7) -> [1001, 2001]

*/

How to solve this in C++ and Python?

- 0of 0 votes
Find out the longest repeated common sub-string(overlapped) in a string.

For example:- mystr = banana # The "ana" is the common overlapped sub-string is been used 2 times.

- 0of 0 votes
Given input format, The first line has the number of employees of a company Z. The next two lines have employees to perform certain operations on. The first employee of the fourth line can be assumed to be the ceo of the company. Each line from then on has the format Employee X Employee Y where X manages Y. (and hence Y forms the child for X).

input:

6

Rajesh

Ravi

//Tree Starts here

Ram Raj

Ram Goku

Raj Rajesh

Raj Richa

Richa Ravi

Its known that each person in the company can directly line manage a maximum of 2 other employees.

For the two employees in the first two lines, find the lowest common manager.

How to construct this tree in java to eventually do an lca?