Implement BFS and a Job Scheduler

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.