• Vehicles • Fashion • Recipes • Blogs • Hunt • Travels • Sport • Fun • Handmade • IT • Education
Mini-Games
x

x
zakruti.com » Knowledge, science, education » Logically Yours
Seemingly IMPOSSIBLE Fox Puzzle Fox in a Hole Asked in Google Interview

Seemingly IMPOSSIBLE Fox Puzzle Fox in a Hole Asked in Google Interview

FBTwitterReddit

video description

Rating: 4.0; Vote: 1
Seemingly IMPOSSIBLE Fox Puzzle -- Fox in a Hole -- Asked in Google Interview gibbeldon: I solved it differently by visualizing where the fox can be each day.
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

Comments and reviews: 29


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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