## 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.

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

for a tree , there are how many adjacent trees?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

keep on shooting at a single tree!!

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

for 5 trees below is working for all cases

2 4 3 2 4 3 2

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

We know absolutely nothing unless we just shot it dead.

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

wow..gr8.. hats off..

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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..

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@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..???

Comment hidden because of low score. Click to expand.
0

@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...

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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,

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

@ 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.

Comment hidden because of low score. Click to expand.
0

@ 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.

Comment hidden because of low score. Click to expand.
0

@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?

Comment hidden because of low score. Click to expand.
0

@ 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

Comment hidden because of low score. Click to expand.
0

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

Pretty interesting.

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?

Comment hidden because of low score. Click to expand.
0

there is no such condition...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

problem statement is unambigious

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Women are unamigos.

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.

Comment hidden because of low score. Click to expand.
0

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

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 )

Comment hidden because of low score. Click to expand.
0

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

I haven't offered any solutions yet.

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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..

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

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

Comment hidden because of low score. Click to expand.
0

forgot to put my name there

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

``````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
.
.
.``````

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

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....

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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....

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-2
of 2 vote
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

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

Comment hidden because of low score. Click to expand.
0

'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.

Comment hidden because of low score. Click to expand.
0

112233... wont work

Comment hidden because of low score. Click to expand.
0

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

wont work

Comment hidden because of low score. Click to expand.
0

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.

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

what is the ultimate solution??

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.

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

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

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

Just show him f'king banana...

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.

### 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.

### 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.

### 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.