Monkey Hunter algorithm - Interview question [closed]
- by Estefany Velez
Question asked in an Interview:
You are a hunter in the forest. A monkey is in the trees, but you don't know where and you can't see it. You can shoot at the trees, you have unlimited ammunition. Immediately after you shoot at a tree, if the monkey was in the tree, he falls and you win. If the monkey was not in the tree, he jumps (randomly) to an adjacent tree (he has to).
Find an algorithm to get the monkey in the fewest shots possible.
SOLUTION:
The correct answer according to me was in the comments, credit to @rtperson:
You could eliminate this possibility by shooting each tree twice as you sweep left, giving you a worst case of O(2n). EDIT: ...that is, a worst case of O(2n-1). You don't need to shoot the last tree twice.
