Puzzle: Jumping Frog
11684 viewsThis question was asked in Adobe interview.
There are 5 holes in the ground in a straight line and a frog lives in them. Every night the frog jumps to a hole on either side of current hole. If it's in the corner hole(say,1st), it will jump to the only adjacent hole(ie 2nd).If it's in hole 2 , it can jump either in hole 1 or 3. You can come in the morning and can have a look at any one hole in a day. Design a strategy to capture the frog in minimum number of days..
|
|
8
|
Post Answer
|
By Guest
I used a pattern. One day I look hole1 next day hole 3, next day hole 5 then hone 2, then hole 4, likewise 1-3-5-2-4-1-3-5-2-4.... this will increase the probability to find frog in hole. Is that the correct solution? pls let me know if you know better.
Reply 32-3-4-2-3-4 Using this approach we can catch the frog, irrespective of which hole, he is residing on the first day
Reply 12The sequence could be:
Reply 72, 3, 4, 4, 3, 2
4, 3, 2, 2, 3, 4
Explanation: Let H denote the set of holes where the Frog might be hiding. On any morning, the Frog is either in an even numbered hole or an odd numbered hole. So on the first morning, either H = {1, 3, 5} or H = {2, 4}. If H = {2, 4}, then the following sequence of inspections suffices to catch the Frog: 2, 3, 4. However, if the Frog was not caught, then H must have equaled {1, 3, 5} on the first morning, so H must equal {2, 4} on the fourth morning. Therefore, repeating the sequence 4, 3, 2 from the fourth day on-wards would suffice to catch the Frog.
In general for N holes, Sequence: {2, 3, ..., N - 1, N - 1, N - 2, ..., 2},
so that the maximum number of mornings needed is 2*(N - 2) for N holes, whenever N > 2.
Agree!
Reply 02 - 2 - 4 - 4 - 3
Reply 1It will take max 6 days and min 1 days to find the frog....
Run it with some example . you will find it.
2-2-3-4 will be best solution.....will catch in 4 ays only :)
Reply 0