Closest Bathroom / Desk on a Grid

Requirements

• 2-D grid input where each cell is one of B, D, _.
• For every D cell, output the Manhattan / step distance to the nearest B cell (4-directional movement, no obstacles in the base case).
• 1-D variant: array of {0, 1, 2} where 0 = empty, 1 = person, 2 = cake. Return the minimum distance between any person and any cake.
• Character-array variant: given an array containing values such as a, b, and c, find the nearest c for each relevant position. Start with a precomputed representation, then discuss how the contract changes when values arrive as a stream.
• Follow-up (Global Assignment): pair every person with a unique cake so the total walking distance is minimized. If there are more people than cakes, the assignment is impossible. Given a target person index, return which cake that person receives in the globally optimal assignment.
• The interviewer typically does not provide a function signature or example I/O — both must be clarified before coding.
• Own test cases expected.

Examples

1-D variant:

input  = [0, 1, 0, 0, 2, 0, 1]
output = 2   # person at index 6, cake at index 4

Notes

• The 2-D base case is the canonical multi-source BFS: seed the queue with every B cell at distance 0, then expand outward writing the first-reached distance into each D cell. One pass, O(R × C) time and space.
• A single-source BFS per desk also works but is O(D × R × C); interviewers will push toward multi-source if the brute-force version is presented first.
• The 1-D variant is a one-pass two-pointer sweep: track the most recent person index and most recent cake index; whenever the cell currently being scanned belongs to the opposite kind, update the running minimum.
• The Global Assignment follow-up is materially harder than it looks. A clean approach collects sorted person and cake indices and runs dynamic programming: dp[i][j] is the minimum total distance to match the first i people using the first j cakes. The transition either skips cake j or matches it to person i; backtracking reconstructs the queried person-to-cake assignment.
• Common stumbling points: forgetting that empty grids and grids with no D cells are valid inputs; in the 1-D variant, off-by-one when both 1 and 2 occur at the same index in different test cases.
• A point-to-point variant hands you an m x n grid of 0/1 and a start and target cell, asking for the shortest path that never steps on a 1. This is plain single-source BFS, and interviewers frequently ask you to justify why BFS rather than DFS gives the shortest path. The {0, 1, 2} array (empty / person / cake) version then asks for the nearest-opposite distance of each person and cake — the same one-pass sweep. One AI-team screen ran both back to back and stated up front that no AI tools were allowed.
• The character-array version explicitly invites a precomputation-first solution before moving to streaming semantics. Clarify whether earlier answers may be revised after a future target arrives and what output latency the stream requires.

Preparation

• Implement the 2-D multi-source BFS from scratch, then re-implement it using only an in-place distance grid (no separate visited set).
• Implement the 1-D two-pointer sweep, then prove its correctness by induction on the running minimum.
• Drill the Global Assignment follow-up: heap of (distance, person, cake) tuples plus two visited sets, then walk through a 4-person 4-cake example by hand.
• Practice driving the prompt with no signature given: ask up-front about grid bounds, whether walls exist, whether multiple bathrooms / cakes can coexist, what to return when no path exists.

One-dimensional cake assignment variant

• A precise one-dimensional variant splits the prompt into two tasks. Task 1 receives A: list[int] where 1 marks a cake plus a start index, and returns the nearest cake distance from start; return -1 when the array contains no cake and reject an out-of-range start.
• The global assignment follow-up minimizes total person-to-cake distance, not each person's nearest individual cake. If there are more people than cakes, the assignment is impossible.
• The safe solution is dynamic programming over sorted person and cake indices: dp[i][j] = minimum cost to match the first i people using the first j cakes, with transitions that either skip cake j or match it to person i. Backtrack through the table to answer which cake a queried person receives.
• Minority variant: Some reports phrase the follow-up as a greedy nearest-pair matching. Clarify whether the objective is one-to-one nearest assignment or globally minimum total distance before coding.