Interview Query

Mouse Search

Have you seen this question before?

We have a 4x4 grid, and we know there’s a mouse trapped in one of the cells. We want to figure out which cell it’s in, but we can only ask queries of a specific form. Given a subset of the cells, we can “scan” our grid to know whether there’s a mouse within that subset or not, but not where it is exactly.

How would we figure out where the mouse is using the fewest number of scans?

Next question: Best Slot Machine
Loading comments