How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Nuro.

What role is this question designed for?

This question is commonly asked for Backend Engineer candidates at Nuro during technical interviews.

Implement BFS and a Job Scheduler | Nuro Coding Question

Quick Overview

Solve grid reveal with BFS and design a thread-safe periodic job scheduler. The solution covers Minesweeper-style expansion, queue processing, priority-queue scheduling, locks, worker pools, cancellation, duplicate prevention, long-running tasks, clock drift, and backpressure.

Implement BFS and a Job Scheduler

Company: Nuro

Role: Backend Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

The interview report described two coding questions: grid reveal with BFS and a concurrent periodic job scheduler. ### Constraints & Assumptions - For the grid problem, follow Minesweeper-style reveal rules and use BFS. - For the scheduler, focus on thread safety, approximate periodic execution, cancellation, duplicate-run prevention, and overload handling. - Explain data structures, concurrency control, and edge cases. - Code-level pseudocode is acceptable for the scheduler if language-specific threading details are not required. ### Clarifying Questions to Ask - For the board, should already revealed cells be ignored? - Are clicks always within bounds? - For the scheduler, can the same job overlap with itself? - Should missed intervals be skipped or caught up? - What precision is expected for job timing? ### Part 1 - Grid Reveal With BFS Given a hidden minefield board and a click position, update the board according to Minesweeper reveal rules. #### What This Part Should Cover - If clicked mine, change `M` to `X`. - Use BFS from clicked empty cell. - Count adjacent mines in 8 directions. - Reveal a digit if adjacent mines exist; otherwise mark `B` and enqueue unrevealed neighbors. ### Part 2 - Concurrent Periodic Job Scheduler Design a thread-safe in-memory scheduler supporting `register`, `cancel`, `start`, and `stop`. #### What This Part Should Cover - Priority queue ordered by next run time. - Lock and condition variable for scheduler state. - Worker pool for concurrent execution. - Job map for cancellation and duplicate prevention. - Reschedule after execution with policies for long-running tasks. ### Part 3 - Handle Edge Cases And Tradeoffs How would you handle long-running tasks, cancellation, clock drift, and backpressure? #### What This Part Should Cover - Monotonic clock, no duplicate scheduled run, optional no-overlap per job, skip or coalesce missed runs, bounded worker queue, and failure isolation. ### What a Strong Answer Covers - Implements BFS reveal correctly and avoids repeated processing. - Separates scheduler polling from worker execution. - Uses thread-safe state transitions and cancellation checks. - Explains overload behavior explicitly. ### Follow-up Questions - How would you prevent the same job from running concurrently with itself? - What happens if a task throws an exception? - How would you persist jobs across process restarts? - How would you test the scheduler deterministically?

Quick Answer: Solve grid reveal with BFS and design a thread-safe periodic job scheduler. The solution covers Minesweeper-style expansion, queue processing, priority-queue scheduling, locks, worker pools, cancellation, duplicate prevention, long-running tasks, clock drift, and backpressure.

Given an `m x n` Minesweeper board and a click position, return the board after revealing per Minesweeper rules. Each cell is one of: - `'M'` — an unrevealed mine - `'E'` — an unrevealed empty square - `'B'` — a revealed blank square with no adjacent mines (in any of the 8 directions) - `'1'`..`'8'` — a revealed square showing the number of adjacent mines - `'X'` — a revealed mine Given the board and an integer click position `click = [row, col]`, reveal cells according to these rules and return the resulting board: 1. If a mine `'M'` is clicked, change it to `'X'` and the game is over — return immediately. 2. If an empty square `'E'` with **no** adjacent mines is clicked, change it to `'B'`, and recursively reveal all of its 8 neighbors that are unrevealed (`'E'`), using **BFS**. 3. If an empty square `'E'` with **at least one** adjacent mine is clicked, change it to the digit (`'1'`..`'8'`) equal to the number of adjacent mines, and do **not** reveal its neighbors. 4. Stop when there are no more squares to reveal. Return the board after the click is applied. --- This report also included a second interview question — a thread-safe in-memory **concurrent periodic job scheduler** (`register`/`cancel`/`start`/`stop`, a min-heap keyed by next-run time, a lock + condition variable separating the polling thread from a worker pool, generation/version numbers to invalidate cancelled heap entries, a monotonic clock, optional no-overlap-per-job, skip/coalesce of missed runs, a bounded worker queue for backpressure, and exception isolation so one bad task can't kill the loop). That portion is an open-ended concurrency/design problem and is not unit-testable here, so this interactive console covers only the deterministic Part 1 above.

Constraints

1 <= m, n <= 50
board[i][j] is one of 'M', 'E', 'B', 'X', or a digit '1'-'8'
click.length == 2
0 <= click[0] < m and 0 <= click[1] < n
board[click[0]][click[1]] is either 'M' or 'E' (the clicked square is unrevealed)

Examples

Input: ([['E','E','E','E','E'],['E','E','M','E','E'],['E','E','E','E','E'],['E','E','E','E','E']], [3, 0])

Expected Output: [['B','1','E','1','B'],['B','1','M','1','B'],['B','1','1','1','B'],['B','B','B','B','B']]

Explanation: Click on (3,0), a blank far from the mine. BFS floods all reachable empties, marking 'B' for cells with no adjacent mine and the digit '1' for the ring of cells touching the single mine. The mine and the two cells fully shielded from the flood by digit cells stay 'M'/'E'.

Input: ([['B','1','E','1','B'],['B','1','M','1','B'],['B','1','1','1','B'],['B','B','B','B','B']], [1, 2])

Expected Output: [['B','1','E','1','B'],['B','1','X','1','B'],['B','1','1','1','B'],['B','B','B','B','B']]

Explanation: Clicking the mine at (1,2) ends the game: 'M' becomes 'X' and the board is returned immediately with no further reveals.

Input: ([['M']], [0, 0])

Expected Output: [['X']]

Explanation: A 1x1 board whose only cell is a mine. Clicking it turns 'M' into 'X'.

Input: ([['E','M'],['E','E']], [1, 0])

Expected Output: [['E','M'],['1','E']]

Explanation: Cell (1,0) borders exactly one mine (at (0,1)), so it becomes '1' and does NOT spread. The remaining 'E' cells stay unrevealed.

Input: ([['E','E'],['E','E']], [0, 0])

Expected Output: [['B','B'],['B','B']]

Explanation: No mines anywhere, so the flood from (0,0) reveals every cell as a blank 'B'.

Hints

First handle the special case: if the clicked cell is a mine 'M', turn it into 'X' and return immediately.
Otherwise the clicked cell is 'E'. Count mines in the 8 neighboring cells. If the count is > 0, write that digit and stop spreading; if it's 0, mark it 'B' and flood-fill.
Use a BFS queue plus a visited set so each cell is enqueued at most once. Only enqueue neighbors that are still 'E' — never spill across a digit cell into a region it doesn't border.
Process the 8 directions for both mine-counting and neighbor expansion; reuse the same direction list for both.

Quick Overview