## Amazon Interview Questions

- 0of 0 votes
--Suppose that we have an array of m by n size. Each element is binary, so it can either be 1 or 0. Design an algorithm that for a given array, the return is a set arrays containing the nodes that are adjecent to each other.

For example:

1 2 3 4 5 6 7 8

---------------

1|0 0 0 0 0 0 0 1

2|0 0 0 0 1 0 0 1

3|0 0 0 1 0 0 0 0

4|0 1 1 1 1 0 0 0

5|0 0 0 0 1 0 0 0

Returns:

Array1 {(8,1) (8,2)}

Array2 {(5,2) (4,3) (2,4) (3,4) (4,4) (5,4) (5,5)}

- 0of 0 votes
Given an unsorted array of integers find a minimum number which is not present in array.

e.g -1 ,4, 5, -23,24 is array then answer should be -22.

- -1of 1 vote
System software problem in amazon labs

http://uva.onlinejudge.org/external/10/1024.pdf

- 0of 0 votes
Given set of job schedules with start and end time, write a function that returns indexes of overlapping sets.

for ex :-

input -> [1,2][5,6][1,5][7,8][1,6]

return -> [0,1,2,4]

- 1of 1 vote
Write a function that accepts root of a binary tree and print zigzag level order traversal, each level print in new line.

For example,

Given tree:

1

2 3

4 5 6 7

8 9

output:

1

2 3

7 6 5 4

8 9

- 0of 0 votes
Write a function that accepts root of a binary tree and return true if it is foldable otherwise return false. A binary tree is foldable if left subtree of root is mirror image if right subtree.

For example:

Given tree,

1

2 3

4 5 5 4

6 6

output: true

- 1of 1 vote
Write a function that accepts root of a binary tree and return true if it is foldable otherwise return false. A binary tree is foldable if left subtree of root is mirror image if right subtree.

For example:

Given tree,

1

2 3

4 5 5 4

6 6

output: trus

- 1of 1 vote
Write a function that accepts root of a binary tree and print zigzag level order traversal, each level print in new line.

For example,

Given tree:

1

2 3

4 5 6 7

8 9

output:

1

2 3

7 6 5 4

8 9

- 2of 2 votes
Write a function that accepts two character arrays each represents a floating point number and return their sum in character array.

For example function accepts "23.45" and "2.5" and return their sum "25.95".

Restriction: We cannot use predefined functions / methods or parsing. We have to go with basic operations.

- 0of 2 votes
Write code to rotate a square matrix:

Input:

1 2 3

4 5 6

7 8 9

Output:

4 1 2

7 5 3

8 9 6

- -1of 1 vote
consider a battlefield to be made up of square cells of unit dimensions. a soldier on the battlefield can move from a cell to all(8) of it's neighboring cells. soldier has a gun with with him which he can shoot the targets up to any distance along any of the 8 possible directions (north,east,west,south,north-east,north- west,south- east,south- west). also some sell are bulletproof which prevents bullets to pass but soldier can walk over them as if it were a normal cell.he can destroy the target from a bulletproof cell but not from a cell behind it.

position of a target/ soldier can be given by the cell, they are on.given the position of the target, starting position of a target and position of all the bullet proof cells. you have to tell the position of closest shooting point i.e the cell from which, the soldier can shoot the target and is closest to the starting position of the soldier. if there are more than such cells, output all of them.

Input/output specifications :

Input specifications :

I) size of the battlefield { integer pair (N,M) : battlefield will be of N*M size )

II) staring position of the soldier {integer pair (i,j)}

III) position of the target {integer pair (x,y) : position of the cell on which target is mounted}

IV) position of the all bullet proof cells { list of integer pair a#b : each element in the list is a position of bullet proof cells }

output specifications :

sequential list of integer pair i#j (cell) that are closest shoot points and must fallow row wise traversal.

Note: if the output list contains four shoot points : (2,1), (1,2), (3,2), (2,4) on a 4x4 battle field.

then the correct output will be {1#2,2#1,2#4,3#2} not {1#2,2#1,3#2,2#4}

Examples:

Input : {2,2} {2,1} {2,2} {1#1,1#2}

output : 2#1

below is the method signature in java:

public static String[] nearest_shoot_point(int[] input1,int[] input2,int[] input3String[] input4){

}

- 1of 1 vote
There are N pots. Every pots have some water in it. They may be partially filled. So there is a Overflow Number 0 associated with every pot which tell how many minimum stone pieces are require for that pot to overflow. So if for a pot 0-value is 5 it means minimum 5 stone pieces should be put in that pot to make it overflow. Initially a crow watched those pots and by seeing the water level he anticipated 0-value correctly for every pot ( that is he knew 01 to On). But when he came back in evening he found that every pot is painted from outside and he is not able to know which pot has what 0-value. Crow wants some K pots to overflow so that he can serve his child appropriately. For overflow of pots he need to search for stone in forest( assume that every stone has same size). He wants to use minimum number of stones required to overflow K pots. But only he know the 0-value of pots he doesn't know now which pot has what 0-value. So the task is that in what minimum number of stones he can make K pots overflow in worst case.

Input/Output Specifications Input Specification: 1) A array 0 corresponding to 0-value of N pots {01, 02, On} 2) Number of pots 3) K -value ( number of pots which the crow wants to overflow}

Output Specification: Minimum number of stones required to make K pots overflow in worst case. Or -1 if input is invalid

Example: Let say there are two pots pot 1 has 0 value of 5 , 01= 5 pot 2 has 0 value of 58, 02= 58 Let say crow wants to make one of the pot to overflow. If he know which pot has what 0-value he would simple search for 5 stones and put then in pot 1 to make it overflow. But in real case he doesn't know which pot has what 0-value so just 5 stones may not always work. However he does know that one pot has 0-value S and other has 58. So even in worst case he can make one of the pot overflow just by using 10 stones. He would put 5 stones in one pot if it doesn't overflow he would try the remaining 5 in the other pot which would definitely overflow because one of the pot has 0-value of 5. So the answer for above question is minimum 10 stones even in worst case. Input : Input 1= {5,58} Input 2= 2 Input 3= 1 Output : 10

- 1of 3 votes
there are 1 billion stars and you are standing at the earth. From the earth , you know the distance of all 1billion stars. Find the nearest 1 million stars from the earth.

- 0of 0 votes
Given a stairs of very large size. You are standing at the 0th step. You have to perform n actions. 1st action means you can move forward to 1 step or not. 2nd action is you can move 2steps or keep standing. 3rd action is you can move 3 steps or not and so on. Given is a step no. k which is broken. You can't stand on this step. Find out after performing n actions what can be the maximum no. of steps you can go.

- 1of 1 vote
Implement a program to reverse the linear linked list in pairs. it should handle both even number of nodes and odd number of nodes. if odd number of nodes, the last node will be the last node after reversion.

Do not move the data in the nodes. Do manipulate node pointers/references. the nodes themselves need to be manipulated, not just the data in the nodes.

For example, if the initial linear linked is,

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

after reverse it should be,

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

- 1of 1 vote
Implement a function that checks if the given binary tree is binary search tree(BST). Use tree operations to solve this. do not try solving by pre-order traversal of the tree and then checking if the array is sorted.

instead, traverse the tree for checking if it is BST.

- -1of 1 vote
Write a function that takes two arguments one array of integers that ranges between 0 and 9 and second the target sum(again integer). It produces all permutations strings of the input digits that equals the target sum.

For example, if input is array 2, 3, 5 and target sum is 10, then the output should be:

22222 because 2+2+2+2+2 = ,10

2323 as 2+3+2+3 = 10

3232

55

2233

3322

532

235

352

etc.,

- 1of 1 vote
There are discounts on particular time period

suppost

Day1 - Day5 => 10%

Day2 - Day 8 => 5%

Day4 - Day6 => 20 %

find the period where maximum discounts is available.

For above example the period is Day4 - Day5 => 10+5+20

that means 35%

Provide the generalize solution. Period can be time also.

- 0of 0 votes
Given a binary tree populate the inorder successor of each node. Do it iteratively.

- 0of 0 votes
{1, 1, 0, 0, 0},

{1, 1, 0, 0, 0},

{1, 0, 0, 1, 1},

{0, 0, 0, 0, 0},

{1, 0, 1, 0, 1}

write a function to return the size of max cluster and coordinate of it, max cluster size to the above example is 5.

- 0of 0 votes
given an array with elements check if just by exchanging two elements of the array we get a sorted array.

time restriction:

O(NlogN)

space restriction: 2N

- 0of 0 votes
Assuming you have a binary tree which stores integers, count the number of nodes whose value is lower than the value of its upper nodes.

- 0of 0 votes
We've 1 book left in the inventory. and two people are trying to get the same book ( say person x and person y ). Person x has added book to the cart and about to make payment and person y has also added book to the cart. How would you solve this concurrency problem ?

- 1of 1 vote
Design a data structure to keep track of top k elements out of 2 billion records.

Each record is numberd with a key which is 30 bit and a number which is count of how many times the customer has visited us.

Come up with an data structure so that the updation of element in 2 billion records will be faster.

Getting top k element will be faster

- 3of 3 votes
Given two binary numbers each represented as a string write a method that sums up the binary numbers and returns a result in the form of binary number represented as a string. You may assume that input fits in the memory and the input strings are, in general, of different length. Optimize your solution, do not use unnecessary 'if' branching.

example:`sumBinary('0111101', '1101')`

returns

'1001010'

- -1of 1 vote
Hardest bug you faced

- 2of 2 votes
Let's assume that there's an array that has nonzero natural numbers where all the numbers repeat an even number of times, except for one value that repeats an odd number of times. Can you write me a function that takes this array, and returns the value that occurs the odd number of times?

Ex : - [ 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 ]

- 0of 0 votes
There is a data structure called mySruct and it contains a, b , c all three of type int . Which means that any data structure takes up 12 bytes . Then in the main define an array of 3 myStructs (ie taking up 36 bytes .. ) . Then define char * and make him an assignment to array( with casting ) . Then do

16 = + c * . That is, come to b in second myStruct. Then do c = 10 , and ask what 's going on?

So the answer is that arr [0] -> b becomes 10

- 0of 0 votes
Find the longest running positive sequence in an array -

Eg - [1,2,-3,2,3,4,-6,1,2,3,4,5,-8,5,6]

It should return 5, with start index : 8

- 0of 0 votes
class a{

public int x=7;

public int y=9;

void f1(){x=24;}

void static f2(){y=35;}

}

what problem in the code?

what is need to change in the code for compaling?