
Seemingly IMPOSSIBLE Fox Puzzle Fox in a Hole Asked in Google Interview
video description
1. Starting with hole 2 => the fox can be in any other hole (1, 3, 4, 5.
2. Moving to hole 3 => the fox can be in three other holes (2, 4, 5.
3. Moving to hole 4 => the fox can be in three other holes (1, 3, 5.
4. Staying on hole 4 => the fox -has- to be in hole 2. (We could go grab it right now)
5. Moving to hole 3 => the fox -has- to be in hole 1. (What are you waiting for? Go grab it)
6. Moving to hole 2 => It is caught. (Finally)
My sequence is 2, 3, 4, 4, 3, 2; reversing the first half. But it's basically the same solution.
I liked my approach because I didn't have to assume anything.
However it is much simpler to generalize with the approach shown in the video.
Just start with the second slot and increment until n-1, then do that sequence again or in reverse and you are done in O(2(n-2)
Date: 2023-11-15
Related videos
Comments and reviews: 29
BigDaddyJinx
To be honest, since it wasn't specified other than -What strategy would ensure that the fox is eventually caught? -, I would start at the far left hole and if he's there' great, and if not then I FILL THE HOLE. I would continue moving to the right-most hole repeating my filling of a hole he wasn't in until he was eventually found as he would run out of left/right decisions quick enough. The best part is, if I saw that a previously filled hole was now open again, that's the first hole I would check when it's time and BOOM. fox.
Remember, they just asked what strategy would ensure capture, and didn't mention that I couldn't think outside the box. So that would be my strategy.
reply
To be honest, since it wasn't specified other than -What strategy would ensure that the fox is eventually caught? -, I would start at the far left hole and if he's there' great, and if not then I FILL THE HOLE. I would continue moving to the right-most hole repeating my filling of a hole he wasn't in until he was eventually found as he would run out of left/right decisions quick enough. The best part is, if I saw that a previously filled hole was now open again, that's the first hole I would check when it's time and BOOM. fox.
Remember, they just asked what strategy would ensure capture, and didn't mention that I couldn't think outside the box. So that would be my strategy.
reply
uberfu
Thie logic fails when the puzzle assumes that the fox will only move to a hole that it did not previously occupy. It doesn't ammter if you check an even or odd hole on the first day -- say you check Hole 2 on Day 1 and the fox was in Hole 3 -- Day 2 you check Hole 3 and the Fox moved to Hole 2. You continue chjecking Holes 4 and 5 on the following days but the fox keeps going between only Hole 2 and Hole 3 -- you will never catch the fox. A rule to the puizzle needs to be added to where the Fox does nto move to the previous Hole from the Day prior. Example if the fox was in Hole 2 on Day 1 then moves to Hole 3 on Day 2 the fox cannot/ does not move back to Hole 2 on Day 3.
reply
Thie logic fails when the puzzle assumes that the fox will only move to a hole that it did not previously occupy. It doesn't ammter if you check an even or odd hole on the first day -- say you check Hole 2 on Day 1 and the fox was in Hole 3 -- Day 2 you check Hole 3 and the Fox moved to Hole 2. You continue chjecking Holes 4 and 5 on the following days but the fox keeps going between only Hole 2 and Hole 3 -- you will never catch the fox. A rule to the puizzle needs to be added to where the Fox does nto move to the previous Hole from the Day prior. Example if the fox was in Hole 2 on Day 1 then moves to Hole 3 on Day 2 the fox cannot/ does not move back to Hole 2 on Day 3.
reply
Debojit
What if suppose I check first hole in day 1, if found, fine; if not then it is in rest 4 holes. The only possible case it can came back to hole 1 in day 2 is if in day 1 it was in hole 2 --> come back to hole 1 in day 2 as well, if found fine, if not there is no chance that the fox will be able to get back to hole 1 in day 3 --> hole 1 is out of consideration now.
In Day 3 come and check the hole 2, if found okay o. w. it must be on hole 3, 4, 5. since the fox can't came back to hole 1 in day 3.
Iteratively in this way we can eliminate all the holes staring from hole 1 untill the fox is found.
This works na.
reply
What if suppose I check first hole in day 1, if found, fine; if not then it is in rest 4 holes. The only possible case it can came back to hole 1 in day 2 is if in day 1 it was in hole 2 --> come back to hole 1 in day 2 as well, if found fine, if not there is no chance that the fox will be able to get back to hole 1 in day 3 --> hole 1 is out of consideration now.
In Day 3 come and check the hole 2, if found okay o. w. it must be on hole 3, 4, 5. since the fox can't came back to hole 1 in day 3.
Iteratively in this way we can eliminate all the holes staring from hole 1 untill the fox is found.
This works na.
reply
Awantika
If fox can only go over one hole then how could it be in odd numbered hole.
Either you choose 2 or 4 and move rightwards and left wards respectively, then we'll get the fox.
If i have chosen H2 for inspection then that time fox is either in H4 or in H2, Because as per question it'll move every night one hole only. So, it would neither be in H3, H1 nor in H5.
Then what is the basis of case 2, I know there is some reason that's why include Case2 and which I am missing. Please clear my confusion.
reply
If fox can only go over one hole then how could it be in odd numbered hole.
Either you choose 2 or 4 and move rightwards and left wards respectively, then we'll get the fox.
If i have chosen H2 for inspection then that time fox is either in H4 or in H2, Because as per question it'll move every night one hole only. So, it would neither be in H3, H1 nor in H5.
Then what is the basis of case 2, I know there is some reason that's why include Case2 and which I am missing. Please clear my confusion.
reply
Stephen
Didn't take me long to solve, I used an easier but less efficient method, well 10 methods actually.
If you start with any hole and check the hole next to it each time you wake up, in any direction, you will eventually flush out the fox - I know at first it seems like it shouldn't work, but it does, test it =)
Edit: Forgot to mention, when you get to an edge, start over from the opposite side and move in the same direction as you started with.
reply
Didn't take me long to solve, I used an easier but less efficient method, well 10 methods actually.
If you start with any hole and check the hole next to it each time you wake up, in any direction, you will eventually flush out the fox - I know at first it seems like it shouldn't work, but it does, test it =)
Edit: Forgot to mention, when you get to an edge, start over from the opposite side and move in the same direction as you started with.
reply
Kumari
Why to take six days? The fox can be caught in at most 4 days. Just fill/cover the hole each morning after inspection if you don't find the fox in that! Consequently, the number of holes will keep on decreasing and the fox will be caught. (The riddle never mentioned that you can't shut the hole)
reply
Why to take six days? The fox can be caught in at most 4 days. Just fill/cover the hole each morning after inspection if you don't find the fox in that! Consequently, the number of holes will keep on decreasing and the fox will be caught. (The riddle never mentioned that you can't shut the hole)
reply
Olga
For N = 5 holes [0, 1, 2, 3, 4, 5] you can go -1, 2, 3, 3, 2, 1- in the worst case of searches.
Then, for N holes [0, 1, 2, 3, 4,, (N-1)], you go -1, 2, 3,, (N-2, (N-2, , 3, 2, 1- in the worst case of searches. So, the worst case of searches is 2-(N-2.
The complexity of the problem is O(N.
reply
For N = 5 holes [0, 1, 2, 3, 4, 5] you can go -1, 2, 3, 3, 2, 1- in the worst case of searches.
Then, for N holes [0, 1, 2, 3, 4,, (N-1)], you go -1, 2, 3,, (N-2, (N-2, , 3, 2, 1- in the worst case of searches. So, the worst case of searches is 2-(N-2.
The complexity of the problem is O(N.
reply
Tytrox
My solution was to eliminate half of the search space in 2 moves, and then use the minimum amount of moves to get a probability of 1 of finding the fox whilst choosing the most likely hole. So for n=5, I calculate an average number of moves to find the fox of 2. 9625 for the order 2234432.
reply
My solution was to eliminate half of the search space in 2 moves, and then use the minimum amount of moves to get a probability of 1 of finding the fox whilst choosing the most likely hole. So for n=5, I calculate an average number of moves to find the fox of 2. 9625 for the order 2234432.
reply
Imre
1 hole is occupied by a fox. OK
-The first morning the fox is an even hole-. WHY?
No one said the fox first moved into an even or odd hole.
Maybe the fox moved into an even hole and went an odd hole at first night. So the first morning the fox is in an odd hole, not an even hole.
reply
1 hole is occupied by a fox. OK
-The first morning the fox is an even hole-. WHY?
No one said the fox first moved into an even or odd hole.
Maybe the fox moved into an even hole and went an odd hole at first night. So the first morning the fox is in an odd hole, not an even hole.
reply
Jayaviswanathan
According to your strategy it takes atmost 6 days
But if u start from day 1 from hole 1 and next day hole 2 and next day hole 3 and next day hole 4 and at last however it must caught at 5 th hole
atmost it must caught within 5 days (atmost 5)
reply
According to your strategy it takes atmost 6 days
But if u start from day 1 from hole 1 and next day hole 2 and next day hole 3 and next day hole 4 and at last however it must caught at 5 th hole
atmost it must caught within 5 days (atmost 5)
reply
24pavlo
On the left I'll right what hole is checked - and on the left where fox could be if it is not caught yet.
Check 2 - 1, 3, 4, 5
Check 2 - 3, 4, 5
Check 3 - 2, 4, 5
Check 4 - 1, 3, 5
Check 4 - 2
Check 3 - 1
Check 2 - No where to go
reply
On the left I'll right what hole is checked - and on the left where fox could be if it is not caught yet.
Check 2 - 1, 3, 4, 5
Check 2 - 3, 4, 5
Check 3 - 2, 4, 5
Check 4 - 1, 3, 5
Check 4 - 2
Check 3 - 1
Check 2 - No where to go
reply
Pavlo
well, that one caught me) but, such an approach is applicable to any number of holes. In fact, this is more about similar (fox can move into the certain hole only from holes before and behind) possibilities than about simultaneous ones.
reply
well, that one caught me) but, such an approach is applicable to any number of holes. In fact, this is more about similar (fox can move into the certain hole only from holes before and behind) possibilities than about simultaneous ones.
reply
Comrade
Day 1: check hole 1. If no fox, fill hole with sand.
Day 2: check hole 2. If no fox, fill hole with sand.
Day 3: check hole 3. If no fox, fill hole with sand.
Day 4: check hole 4. If no fox, fox must be in hole 5.
reply
Day 1: check hole 1. If no fox, fill hole with sand.
Day 2: check hole 2. If no fox, fill hole with sand.
Day 3: check hole 3. If no fox, fill hole with sand.
Day 4: check hole 4. If no fox, fox must be in hole 5.
reply
Graham
UNLESS I am missing something; start from one end
Say 1 if found done
check 2 if found done
check 3 if found done
check 4 if found done else fox is in hole 5
check 4 again fox found.
so 5 steps guaranteed
reply
UNLESS I am missing something; start from one end
Say 1 if found done
check 2 if found done
check 3 if found done
check 4 if found done else fox is in hole 5
check 4 again fox found.
so 5 steps guaranteed
reply
Adam
this is wrong. what if it is in 1 and it is bouncing back and forth from 1 to 2 back to oone and you started at 2 going up/to the right you would have to retrace back
start at the ends, 1 or 5 and mve back to GAURANTEE.
reply
this is wrong. what if it is in 1 and it is bouncing back and forth from 1 to 2 back to oone and you started at 2 going up/to the right you would have to retrace back
start at the ends, 1 or 5 and mve back to GAURANTEE.
reply
Gilberth
I used your strategy but with the fox beginning in a different hole and it didn't work. I created my own strategy and despite it takes one day more it guarantees that you will catch it.
reply
I used your strategy but with the fox beginning in a different hole and it didn't work. I created my own strategy and despite it takes one day more it guarantees that you will catch it.
reply
Marcus
Lol seems like a lot of people did not get the intention of the question. This is an algorithmic question, so filling up the hole, putting cloth and looking for tracks are not applicable
reply
Lol seems like a lot of people did not get the intention of the question. This is an algorithmic question, so filling up the hole, putting cloth and looking for tracks are not applicable
reply
Keith
But wait,
assume fox was in hole 1
Human: 2 Fox: 1
Human: 3 Fox: 2
Human: 4 Fox: 1 or 2
So, we moved from 2-3-4 based on above approach but couldn't catch the fox
reply
But wait,
assume fox was in hole 1
Human: 2 Fox: 1
Human: 3 Fox: 2
Human: 4 Fox: 1 or 2
So, we moved from 2-3-4 based on above approach but couldn't catch the fox
reply
Jason
what if the fox starts in hole 4 and shifts to hole 5 then back and forth between 4 and 5 ONLY. if you look in hole 5 first and work your way down you will never see the fox?
reply
what if the fox starts in hole 4 and shifts to hole 5 then back and forth between 4 and 5 ONLY. if you look in hole 5 first and work your way down you will never see the fox?
reply
sunny
Why would i do these things!
(Go out of box) keep piece of meat.
And see from which hole he is coming from -
Your strategy is taking six days mine just 2 min --
reply
Why would i do these things!
(Go out of box) keep piece of meat.
And see from which hole he is coming from -
Your strategy is taking six days mine just 2 min --
reply
Micaldom
I think a general solution would be if there are N-holes and N > 2 the order you should check is 2 -> n-1, n-1 -> 2. I think this works can't fully explain though.
reply
I think a general solution would be if there are N-holes and N > 2 the order you should check is 2 -> n-1, n-1 -> 2. I think this works can't fully explain though.
reply
Jamm
I don't like article-free English, It's very annoying! Other than that, a very nice presentation. the best I've seen (not heard. -AN even hole, AN odd hole- please!
reply
I don't like article-free English, It's very annoying! Other than that, a very nice presentation. the best I've seen (not heard. -AN even hole, AN odd hole- please!
reply
Wyatt
234234, 234432, 432234, or 432432 are where you should search (any of the 4 would work, but in any case it'll definitely be less than a week before you find him)
reply
234234, 234432, 432234, or 432432 are where you should search (any of the 4 would work, but in any case it'll definitely be less than a week before you find him)
reply
Steve
another solution, day 1 inspect hole 1, if not there inspect hole 1 on day 2 then hole2 on day 3, hole 3 on day 4 etc, worst case find fox in hole 5 on day 6
reply
another solution, day 1 inspect hole 1, if not there inspect hole 1 on day 2 then hole2 on day 3, hole 3 on day 4 etc, worst case find fox in hole 5 on day 6
reply
Charles
Check ervery day hole three and in the worst case you will catch it in 4 days
worst case 1: d1 3-2 d2 2-1 d3 1-2 d4 2-3
best case: d1 4-3 or 2-3
reply
Check ervery day hole three and in the worst case you will catch it in 4 days
worst case 1: d1 3-2 d2 2-1 d3 1-2 d4 2-3
best case: d1 4-3 or 2-3
reply
MyKazam
Question wasn-t specific enough, they never said the fox couldn-t teeter back and forth. Technically with the information there is no logical solution.
reply
Question wasn-t specific enough, they never said the fox couldn-t teeter back and forth. Technically with the information there is no logical solution.
reply
Leena
I don't understand why people are coming with loopholes, just solve it.
We teach our next generation addition not give them calculator directly.
reply
I don't understand why people are coming with loopholes, just solve it.
We teach our next generation addition not give them calculator directly.
reply
Michael
By molding plastic explosives that look like the fox and putting them in the holes, like in Caddyshack. Oh wait, that didn't actually work.
reply
By molding plastic explosives that look like the fox and putting them in the holes, like in Caddyshack. Oh wait, that didn't actually work.
reply
eirene
Just check the same hole each day. As the fox changes which hole it is in every day, eventually it will end up in the hole you are checking.
reply
Just check the same hole each day. As the fox changes which hole it is in every day, eventually it will end up in the hole you are checking.
reply
Add a review, comment
Other channel videos















