Katkat
Back

Solve BFS and grid tasks

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.