## Amazon Interview Questions

- 0of 0 votes
write a function for a BST to implement best case search.If exact search key not available in BST then return best suited key.Ex- if a tree has keys 21 15 26 30 55 7 and if my search key is 25 then this function should return 26.

- 0of 0 votes
Write a program to find the smallest number that can be formed by 0 and 9 which is divisible by a given number.

For example, if given number is 3 output should be 9,

if given number is 2 output is 90,

if given number is 10 output is 90,

- 0of 0 votes
Write a program to find the smallest number that can be formed by 0 and 9 which is divisible by a given number.

For example, if given number is 3 output should be 9,

if given number is 2 output is 90,

if given number is 10 output is 90,

if given number is 7 output is 10^23.

- 0of 0 votes
How to impliment Google map

Data Structure and algorithm.

1. Zoom in/out

2. horizontal/ vertical.

Assumtion - all the image of earth with pixel\Any other assumption is allowed

- 0of 0 votes
How google map implemented ? zoom in , zoom out, moving horizontal and moving vertically.

Give data Structure and algorithm.

Given all the data from satellite which revolve around earth in spiral way.

- 0of 0 votes
Given ten million numbers, each having 11 bits, find the most time efficient way to sort the numbers.

- 0of 0 votes
Given an array and a number, find two integers that sums to the given number.

- 0of 0 votes
Given an unsorted array of ints,sort the shortest sub-array which results in sorting of the whole array.

Ex:

i/p: [-1,0,4,3,2,1,7,8,9]

By sorting sub array [4,3,2,1] the whole Array is sorted.

i/p: [10, 15, 20, 30, 25, 40, 35, 45, 50, 60]

By sorting sub array [30, 25, 40, 35] the whole Array is sorted.

i/p: [-1,0,4,3,2,1,7,8,9,-2]

Shortest sub-arry to be sorted is [-1,0,4,3,2,1,7,8,9,-2]

- 0of 0 votes
if there is a tree

A

B C

C E

D F

G

Then write an API where new given a path lenghth

say length=5, then find the nodes havnig path length (5) traversing from all the leaf nodes and going up (by 5 levels) and print that node.

SO basically, all nodes that are 5 level up the leaf node is to be printed.

my solution:

perform a DFS , using a stack and a used a global variable counter=0

then

algo:-

if(pop)

counter++

if(push)

counter--

if(counter==5)

print node and initialise counter=0;

end....

- 1of 1 vote
string x = "1..5,8,11..14,18,20,26..29"

string y = "1,2,3,4,5,8,11,12,13,14,18,20,26,27,28,29"

Write a C++ program to expand a given string x to y.

- 0of 0 votes
A certain language uses a set of characters from a-z but not in the same sequence as in english.

Now, words from the language appear in pair to you. e.g. LMOSS,NMOSS which implies that N comes after L, but not necessarily immediately after L. Similary, other words like{NMORR,TMORR}, { KSINN, KXINN }are also available.

What should be the data structure which should be used so that we can find out the character sequence in this language.

- 1of 1 vote
We are given an unsorted array of n^2 arbitrary numbers, and we must output an n x n matrix of all the inputs such that all the rows and columns are sorted. For example, suppose n=3, n^2=9, and the 9 numbers are just the integers {1,2,...,9}

Possible ouputs include:`1 4 7 1 3 5`

`2 5 8 2 4 6`

`3 6 9 7 8 9`

Show how to sort this array with a Ω(n^2log n) lower bound.

- 1of 1 vote
Given an array of integers, but instead of all integers having the same length each can have a different number of bits. For example, the numbers 0 or 1 have 1 bit, 2, 3 have 2 bits, 4,5,6,7 have 3 bits. The TOTAL number of bits of all the integers in the array is n. Describe how to sort the array in O(n) time.

- 0of 0 votes
Mice and holes are placed in a straight line. There are n holes on this line. Each hole can accomodate only 1 mouse. A mouse can stay at his position, move one step right from x to x+1, or move one step left from x to x−1. Any of these moves consumes 1 minute.

Assign mice to holes so that the time when the last mouse gets inside a hole is minimized.

for example if there are 3 mice positions of mice are:

4 -4 2

positions of holes are:

4 0 5

the answer should be 4

because:

Assign mouse at position x=4 to hole at position x=4 : Time taken is 0 minutes

Assign mouse at postion x=-4 to hole at position x=0 : Time taken is 4 minutes

Assign mouse at postion x=2 to hole at postion x=5 : Time taken is 3 minutes

After 4 minutes all of the mice are in the holes.

- 0of 0 votes
In the following equation x, y, and n are positive integers.

1/x + 1/y = 1/n

For n = 4 there are exactly three distinct solutions:

1/5 + 1/20 = 1/4

1/6 + 1/12 = 1/4

1/8 + 1/8 = 1/4

What is the least value of n for which the number of distinct solutions exceeds one-thousand?

- 0of 0 votes
How to implement Dictionary, I gave solution using Tries then they asked how to implement using HashMap.

> What is the advantage of HashMap over Tries.

> What is the advantage of Tries over HashMap.

> How to implement dictionary using HashMap so that when i press a character it will list all the words starting with that character.

- 0of 0 votes
Given two Binary Tree, need to check both are same or not(Without using recursion). Extend the solution for Tree.

- 0of 0 votes
Knight movement on a chess board...

Given any source point and destination point. Need to find whether Knight can move to destination or not.

If yes, Then what would be the minimum movement.

Extended Question : Extend the solution when chess size is infinite.

PS : Had to solve without recursion

- -1of 1 vote
There are 3 fields in a music list. number of requests, genre name, Index. And list can take upto 1000 entries. An user can search based in genre name, index and number of requests. index and genre name can be optional. Write test cases to get the list searched by user.

- 0of 0 votes
What is the most challenging part in ur carreer?

- 0of 0 votes
your manager wants 100% automation for a product. But it is not possible. what will you do?

- 0of 0 votes
write test cases for group chat?

- 0of 0 votes
Amazon site is slow. how will you troubleshoot ?

- 0of 0 votes
Function generates random numbers every 30 sec. once in a while it takes long time to generate. how will u Debug this?

- 1of 1 vote
There are 6 hosts and there are 6 machines in each host. Admin uses dice role to allocate machine to each user. Write test cases for dice role and machine allocation.

- 0of 0 votes
A function takes 2 inputs and do some computation and stores in cache. If result is already there, it doesn’t do computation and get the results from cache, otherwise it does some computation and get the results and stores in cache. Write test cases for this.

- 4of 4 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 |a-b|, |b-c| and |c-a| are minimum

Please provide as efficient code as you can.

Can you better than this ???

- 0of 0 votes
Recursively implement a function that returns boolean value by checking if a binary tree is binary search tree or not.

- 0of 0 votes
How does one application implement similar to DropBox? How can we Mmake sure they are in sync for files. How u’ll check for files are downloaded. How u’ll download files. What protocols u’ll use?

- 0of 0 votes
Given an array of positive and negative numbers(no zeroes),i have to arrange them in such a way that the positive and negative numbers should be arranged consecutively.The number of positive and negative numbers may not be equal i.e. if there is no positive number(or negative) left,then all the remaining negative numbers(or positive) are appended to the end of the array.The order is important i.e.if input array is { 2,-1,-3,-7,-8,9,5,-5,-7},then the output array should be {2,-1,9,-3,5,-7,-8,-5,-7}.The code is done in O(n) without using another array.I came up with a solution in which i chose 0 as pivot element and separate the numbers (using quicksort) but in this case the order is not preserved.