Amazon Interview Question
Software Engineer / DevelopersCountry: United States
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
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?
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.
if there is a cycle of length more than 2 nodes in the graph, there is no solution to the problem
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?
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
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: monkey just jumps to adjacent tree RANDOMLY... ur case is not a random, but specific
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 gave a counter example to your proposal to shoot always at 1 tree. randomness allows for such a case to happen
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.
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.
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
There is a solution for more than 3 trees.
There is however a configuration with 3 trees that has no solution.
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?
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?
For 4 trees, the sequence 2 3 3 2 is enough
For 5 and 7 trees, your solution doesn't work
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..
@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
Guys... for all the suggestions you provided are under the assumption that each tree has only two adjacent trees ..
@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..???
@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...
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.
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,
@ 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.
@ 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: 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
"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
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?
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.
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 )
You say "first i thot eugene soln wud work, but ... ".
I haven't offered any solutions yet.
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...
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
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
[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
for 5 trees solution is 1 4 6 4 1, here we have only 5 trees how you shoot tree number 6?
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....
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?
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
'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.
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.
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.
- Shock August 07, 2012Given 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.