Amazon Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
2
of 4 vote

Though the aim of interviewee seems to encourage the candidate to ask more questions about the arrangement of the trees in the forest and other requirements.
Given the problem here there seems to be only one solution >

Start with the leftmost (if the trees are linear) or any (if the trees are in circle) tree. Shoot one tree twice. If monkey is jumping to the left adjacent tree, it will be dead in the second shot. Otherwise if the monkey jumps to the right adjacent tree every time, it will be dead after sometime later. Even if the tree formation is circular, monkey will be dead.

- Shock August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

i think solution is possible only when all trees are in linear row

- Anonymous August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for 2 trees
2 2
for 4 trees
2 3 3 2
for 6 trees
2 3 4 5 5 4 3 2
for 8 trees
2 3 4 5 6 7 7 6 5 4 3 2

- algos August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@algos
I wonder how you came to the conclusion there is a difference between odd and even number of trees in the algorithm.
Actually, you gave shoot sequences, but no algorithm to generate them. So how did you do?

The sequences you gave for even number of trees happen to be valid solutions to the problem. Are they optimal?

The original problem does not restrict the graph to only linear graphs. Do you have any idea to solve more complicated graphs?

- Glude August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there any cycles in the forest e.g. 1 is neighbor of 2, 2 is neighbor of 3, 3 is neighbor of 4 and 4 is neighbor of 1 forming a cycle?

We certainly can't know on which tree the monkey jumped after the shooting but can we know from which tree it jumped? e.g. I shoot tree 7 and the monkey jumps to some tree I don't know to which but I know it jumped from tree 5, I know the source of the jump is 5 but the destination can be any of 5's neighbors.

- Anonymous August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if there is a cycle of length more than 2 nodes in the graph, there is no solution to the problem

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks for clarifying about the cycle, what about the second doubt? can we know where the monkey was after we shoot like it jumped from tree 10 to a neighbor which neighbor that we don't know, or do we know absolutely nothing about monkey's whereabouts?

- Anonymous August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We know absolutely nothing unless we just shot it dead.

- eugene.yarovoi August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

for 5 trees below is working for all cases

2 4 3 2 4 3 2

- Anonymous August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for 5 trees below is working for all cases
2 4 3 2 4 3 2
for 7 trees below is working
2 6 5 4 3 2 6 5 4 3 2
for 9 trees
2 8 7 6 5 4 3 2 8 7 6 5 4 3 2
this logic is working for all odd number of tree cases

- Anonymous August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for even number of trees
for 2 trees
2 2
for 4 trees
2 3 3 2
for 6 trees
2 3 4 5 5 4 3 2
for 8 trees
2 3 4 5 6 7 7 6 5 4 3 2
please confirm this is correct?

- Anonymous August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

for a tree , there are how many adjacent trees?

- cobra August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

there is a finite number of trees. A given tree has n adjacent trees.

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

keep on shooting at a single tree!!

- cobra August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lets there are 10 trees are there. if you keep on shooting at tree#1 then monkey will be jumping from 9<->10... so wrong

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@anonymous: monkey just jumps to adjacent tree RANDOMLY... ur case is not a random, but specific

- cobra August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what I mean is if monkey jumps in this order from 9->10 and 10->9, then your solution won't work... if you provide the solution what ever than way it jumps it should work. Assume that given order is random.

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

anonymous gave a counter example to your proposal to shoot always at 1 tree. randomness allows for such a case to happen

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

An important thing to note is that the strategy must work against any jump sequence. The monkey shouldn't be able to evade death even if it knows in advance the entire strategy of the hunter. This is necessary, because suppose there is some death evading sequence that a monkey can do that will counter a given sequence of shots from the hunter. Even if the monkey moves randomly, it has some chance of randomly choosing that sequence and not getting shot. Since you need a strategy that always succeeds, your strategy must be a strategy that succeeds against every possible sequence of moves from the monkey.

- eugene.yarovoi August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for 5 trees below is working for all cases

2 4 3 2 4 3 2

- Anonymous August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

looks like there is solution only for up to 3 trees (shoot tree#2 two times monkey will fall).... if number of trees are more than 3 then there is no solution.

- Anonymous August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you show how shooting at tree #2 twice will result in killing monkey???

- skeptic August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is only if # of trees are 3...
first shoot tree#2 -
if monkey is on tree#2 it will fall... done
else if monkey is on tree#1 or tree#3 then it will jump to adjacent tree that tree#2
again shoot tree#2, now the monkey is on tree#2 so it will fall

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

There is a solution for more than 3 trees.
There is however a configuration with 3 trees that has no solution.

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

probably with 3 trees with cycle there might not be solution... if 3 trees are on straight line then there is solution...
can you tell us how long is the shooting order lets for 5 trees?

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for 4 trees below is the solution
shooting order is: 2 3 3 2 2

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

solution for 5 trees is the below sequence
2 3 3 4 4 3 3 2 2

for 7 trees it will be
2 3 3 4 4 5 5 6 6 5 5 4 4 3 3 2 2
ans so on...
folks can you check the validity of this sequence?

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wow..gr8.. hats off..

- email.suman.roy August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For 4 trees, the sequence 2 3 3 2 is enough
For 5 and 7 trees, your solution doesn't work

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

monkey:2 1 2 3 2 4 3 2 1 2 1 2 1 2 1 2 1
gun @ :2 3 3 4 4 5 5 6 6 5 5 4 4 3 3 2 2
I think nt working..

- email.suman.roy August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Glude: for 4 trees 2 3 3 2 is not enough...
counter example..
1->2->1->2->1

so it much require 2 3 3 2 2
and 5 trees it working with above sequence

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Guys... for all the suggestions you provided are under the assumption that each tree has only two adjacent trees ..

- cobra August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Glude: the conditions you provided is not enough.. For linear configuration, i accept your answers..
Trees are configured in what manner?.. circular or star shaped or like matrix..???

- cobra August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Suman Roy:
monkey:2 1 2 3 2 4 3 2 1 2 1 2 1 2 1 2 1
gun @ :2 3 3 4 4 5 5 6 6 5 5 4 4 3 3 2 2
I think nt working..

in the above you are jumping from 2->4 directly that wrong... you can go from 2->3 or 2->1 right? please correct me if I am wrong...

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think we should consider the worst case here.
2 2 3 4 5 6.....n-1 n

in the worst case it will be n shots to shoot the monkey. Otherwise there could be multiple solution/configurations.

- mr August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If three trees are not in a same line. They form three nodes of a triangle. Then it is possible you never shoot the monkey.
A

B C

you keep shooting at A, monkey just jumps between b and c,

- miaomiao August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@mr: your solution wont work...lets take a counter example below...

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

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Anonymous : for 4 trees in a line, your counter example 1 -> 2 -> 1 -> 2 -> 1 doesn't work against sequence 2 3 3 2.

Here is why :

shoot 2 => monkey 1 -> 2
shoot 3 => monkey 2 -> 1
shoot 3 => monkey 1 -> 2
shoot 2 => monkey dead, you can't do the last move from 2 -> 1

I still think 2 3 3 2 works against every possible move of the monkey and I can prove it.

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ cobra : the tree configuration is not specified in the problem description. that means the configuration can be anything. Your goal is to define the type of configurations that do not accept a solution, and for the configurations which do, find an algorithm to produce a shot sequence that is a solution.

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Glude: for 4 trees 2 3 3 2 is enough...
can you confirm the solutions provided above for 5 and 7 trees are correct? if not can you give me a counter example?

- Anonymous August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ Anonymous

"solution for 5 trees is the below sequence
2 3 3 4 4 3 3 2 2"

shoot 2 => monkey 1 -> 2
shoot 3 => monkey 2 -> 1
shoot 3 => monkey 1 -> 2
shoot 4 => monkey 2 -> 3
shoot 4 => monkey 3 -> 4
shoot 3 => monkey 4 -> 5
shoot 3 => monkey 5 -> 4
shoot 2 => monkey 4 -> 5
shoot 2 => monkey 5 -> 4, Monkey wins

"for 7 trees it will be
2 3 3 4 4 5 5 6 6 5 5 4 4 3 3 2 2"

=> This sequence has the exact same flaw

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Glude
seriously big thanks to you for pointing this minute mistake which slipped off while doing this puzzle.

Pretty interesting.

- mr August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

if there is a condition that the monkey will not come back to same tree(something like the tree being shot all together)....then we can attempt at a Binary Search order shoot?

- sam August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

there is no such condition...

- Glude August 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

problem statement is unambigious

- Rocky August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Women are unamigos.

- Anonymous August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I am assuming the trees are in linear configuration as other configurations does not seem to have solution. If there are n trees, keep shooting each tree twice starting from tree number 2 to tree number (n -1). So the number of shots required will be (2 * (n-2)) . It should work because, if the monkey is in tree 1 and you shoot tree 2 twice it should hit. If it is not in tree 1 then shooting tree 2 twice will make sure that it is not there in either 1 or 2. Similarly we can proceed till tree (n -1). May be we can reduce the number of shots required. That needs to be explored.

- amgp August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are saying that if you shoot at tree 2 twice, the monkey cannot be in tree 1 nor 2.
What if at your second shot on tree 2, the monkey jumps from 3 to 2?
it doesn't work

- Glude August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

first i thot eugene soln wud work ..but thanks to Glude...
so it looks like the prob with above soln was .. that if are going shooting towards right ie ...2-3-3-4-4 etc.. nd if the clever monkey jumps onto 4th tree on our second shot to tree 4th tree.... then we wud continue shooting towards right nd monkey would fly around on left side... same can happen wen we go back towards left...
So i think to avoid this .. we can do the following ---
2-1-3-2-4-3-5-4 (for 5 trees)

to explain the logic -- we want the monkey to b on our right side only nd not to cross to our left... so if trees are p - q - r - s
and we shoot at q .... to cross to our left ,... the monkey might b on q now ... ( and can jump to p or r .... so shoot p now ... ( this way monkey can never cross us)
shoot current(q) .. shoot prev(p) ... shoot next (r) .... shootprev(q)... shootnext(s)
i hope its clear nd it works :) ( yes i assumed its linear tree distribution )

- back2normality August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You say "first i thot eugene soln wud work, but ... ".

I haven't offered any solutions yet.

- eugene.yarovoi August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

both terrible mistakes ,,, my bad eugene :)
my soln wont b able to hold him down ( ie he still can cross to the left )
new soln which comes to my mind is --- if 1 - 2 - 3 - 4 -5 .... n are the trees..
shoot - 22334455..
this way he cant go to left...

- back2normality August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this one is even worse/..... i think i shd quit :)

- back2normality August 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Maintain the state of monkey,who will be in one of the tree in the possible set. Try to reduce the number of elements in the set. Each shoot either kills the monkey or monkey changes its state. for e.g. n= 6, initially monkey can be in one of the tree 1-6

State shoot
[123456] 2
[23456] 3
[13456] 4
[2456] 5
[135] 5
[24] 2
[35] 3
[46] 4
[5] 5

- amzcoder August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think
[13456] 4
[2456] 5

this is correct because the state 3 would be created only when monkey is either in state 2,4 as we can see the shooting at place 4 would have killed the monkey and so 4->3 and we dont have initial state 2 before this state..

correct me if i am wrong..

- Bugger August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

for n trees in linear configuration....
start from one end and shoot a tree twice and start moving to the other end
example
for n = 10
shooting sequence will be
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
so for n trees we need 2*n shots to hit the monkey

- Anonymous August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Lets assume we have n trees. we shoot from the left to right
eg: 1 2 3 ... n
then we shoot from right to left
eg : n,n-1,n-2 ...1

Then we must hit the money somewhere.
(Another example:
let n=7
1,2,3,4,5,6,7,7,6,5,4,3,2,1
)

If anyone can provide a counterexample. I would appreciate it

- assume all trees are in linear row August 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

forgot to put my name there

- Vincent August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you mind to tell me how long does it take to come up this solution for u?

- Vincent August 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider monkey sits at tree 1
You shoot at,   Monkey jumps to
2                              2 
3                              3
4                              4
5                              5
6                              4
6                              3
5                              2
4                              1
3                              2
2                              3
2                              2
3                              3
.
.
.

- hari@hbiz.in August 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think the Monkey can be killed in 2(n-2) shots.

start from the second tree. take 2 shots at each tree from 2nd till n-1 tree. (for n trees).

like for n = 6, 22334455

- Hem September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

[edit: wrong solution, dont bother :)]

Its about combinations, so i think of binomial coefficients, use levels of pascal's triangle for each n > 2 and shoot from left to right or right to left like:

1
                                     1     1
n = 3                            1     2     1
n = 4                         1     3     3     1
n = 5                      1     4    6     4     1
and continue...

to clarify:

T1         T2         T3         T4          T5
n=5      1shot  -> 4 shots  -> 6 shots  -> 4 shots  -> 1shot

shoot from left to right , until that tree has 0 shots left :
shoot first tree 1 time, 2nd tree 4 times, 3rd tree 6 times....

comments are welcome

- ozantabak January 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for 5 trees solution is 1 4 6 4 1, here we have only 5 trees how you shoot tree number 6?

- Anonymous January 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

numbers are not tree ids,
they are how much you should shoot on each tree
let me clarify;

T1         T2         T3         T4          T5
n=5      1shot  -> 4 shots  -> 6 shots  -> 4 shots  -> 1shot

shoot from left to right , until that tree has 0 shots left :
shoot first tree 1 time, 2nd tree 4 times, 3rd tree 6 times....

- ozantabak January 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about the following sequences of shoots and jumps? (n = 4)
jumps: 4 - 3 - 4 - 3 - 2 - 1 - 2 - 1
shoots: 1 - 2 - 2 - 2 - 3 - 3 - 3 - 4 (according to your solution)
The monkey is alive - isn't it?

- Aleksey.M January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yep, you're totally right, i didn't see that

- ozantabak February 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote
- email.suman.roy August 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

for linear configuration of tree
start from one end and shoot at tree twice and move to other end
for n = 10
shooting sequence will be
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
we need 2*n shots for n trees

- Anonymous August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

for linear configuration of tree
start from one end and shoot at tree twice and move to other end
for n = 10
shooting sequence will be
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10
we need 2*n shots for n trees

- Anonymous August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

'10 9 10 9 10 9 10 9 10 9 10 9 10 9 10 8' how can it jump to 8 from 10. it can only jump to 9 from 10
Even i evolved at 1122334455 or 5544332211 solution only.

- Swarna August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

112233... wont work

- swar001 August 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

for 6 trees,initially monkey at 5
shots@112233445566
monk@454545654321

wont work

- Ankush August 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will work because at the shot is taken first time at 5 the monkey will be at the 5th tree , ready to jump to 4.

- hem September 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

what is the ultimate solution??

- email.suman.roy August 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

I wrote a simulation of a forest of 20x20 trees always starting the monkey in tree 0,0. I counted the times the monkey visted each tree during a million shots, using a random jump of 8 possible directions, ignoring any jump that would take it outside the forest. Over about 20 or 30 runs of this program, it looks like on average the monkey will visit some edge tree more frequently than any interior tree, with trees within 2 to 4 of a corner but still on an edge getting the most hits. But it also happens that some edge tree will be visited the least of all others, though that is a less frequent occurence and seems like it's either an exact corner or one of the trees closer to the middle of an edge. So my strategy would be to pick an edge tree near a corner and shoot at it continuously.

- Rik August 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Get a f*ing machine gun. spray them all.

- fizzybuzzer September 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Just show him f'king banana...

- j/k October 12, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More