Solve BFS and grid tasks
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
The coding rounds included several algorithmic problems:
1. **Threshold search with binary search**: You are given floors `1..n` and an API `canOperate(floor)` that returns `true` if an elevator can safely serve that floor and `false` otherwise. There exists a highest safe floor `T` such that all floors `<= T` are safe and all floors `> T` are unsafe. Find `T` using `O(log n)` calls.
2. **Shortest path on a combination lock**: A lock has four wheels, each showing a digit `0-9`. In one move, you may increment or decrement exactly one wheel by `1`, with wraparound (`9 -> 0`, `0 -> 9`). Given a start state, a target state, and a set of blocked states that cannot be visited, return the minimum number of moves needed to reach the target, or `-1` if it is impossible.
3. **Nearest exit in a 2D grid**: You are given a rectangular grid containing walls and open cells, plus a starting cell inside the grid. You may move up, down, left, or right through open cells. Return the minimum number of steps needed to reach any open boundary cell other than the starting cell, or `-1` if no exit exists.
4. **Generate a random minesweeper board**: Given `rows`, `cols`, and `N`, generate a `rows x cols` board with exactly `N` mines placed uniformly at random in distinct cells. Then fill each non-mine cell with the number of adjacent mines in the eight neighboring positions. The implementation should emphasize clean code, simple logic, and avoidance of unnecessary auxiliary data structures when possible.
Quick Answer: This collection evaluates understanding of search techniques (binary search and BFS), graph and grid traversal, state-space shortest-path reasoning, randomized placement with adjacency counting, and attention to implementation quality and complexity trade-offs.