## Problem A hidden cell is placed uniformly at random in an N x M grid. You can query a row or a column; the oracle tells you whether the cell is in that row/column. Devise a strategy to locate the cell using the minimum worst-case number of queries, then implement it. ```python def locate_cell( n: int, m: int, oracle # callable: oracle('row', i) -> bool, oracle('col', j) -> bool ) -> tuple[int, int]: pass ``` ``` Example (n=4, m=4): Binary search on rows: ceil(log2(4))=2 queries -> narrow to 1 row Binary search on cols: 2 queries -> narrow to 1 col Total: 4 queries worst case Naive: query each row then each col -> up to n+m-1 queries = 7 ``` ## Follow-ups 1. Prove that binary search on rows then columns is optimal in terms of worst-case query count. 2. If the oracle is noisy (lies with probability p), how would you adapt the strategy? 3. How many expected queries does random probing require before finding the cell? 4. Extend to a 3D grid (N x M x D cube) — what is the optimal worst-case query count?

InterviewDB Experience

Grid Guessing: Minimum Queries to Locate a Hidden Cell in a Matrix

phone

Interview Experience

Problem A hidden cell is placed uniformly at random in an N x M grid. You can query a row or a column; the oracle tells you whether the cell is in that row/column. Devise a strategy to locate the cell using the minimum worst-case number of queries, then implement it. Follow-ups Prove that binary search on rows then columns is optimal in terms of worst-case query count. If the oracle is noisy (lies with probability p), how would you adapt the strategy? How many expected queries does random probin…

Full Details

🔒

Unlock all Decagon questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a candidate experience report from a decagon interview during the phone round.

It covers the following topics: Binary Search, Phone, Coding, Onsite, Matrix .

Topics

Binary Search Phone Coding Onsite Matrix

Grid Guessing: Minimum Queries to Locate a Hidden Cell in a Matrix

Interview Experience

Full Details

About This Question

Topics

More Decagon Interview Questions