PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCoaches

Quick Overview

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.

  • medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

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.

Part 1: Highest Safe Floor

You are given a monotonic boolean list `safe` where `safe[i]` tells whether floor `i + 1` is safe for an elevator. There exists a threshold `T` such that every floor `1..T` is safe (`True`) and every floor `T+1..n` is unsafe (`False`). Return the highest safe floor number `T`. If no floor is safe, return `0`. Your algorithm should use binary search.

Constraints

  • 0 <= len(safe) <= 200000
  • The list is monotonic: all `True` values come before all `False` values
  • Floor numbers are 1-based

Examples

Input: []

Expected Output: 0

Explanation: There are no floors, so the highest safe floor is 0.

Input: [True]

Expected Output: 1

Explanation: The only floor is safe.

Input: [False, False, False]

Expected Output: 0

Explanation: No floor is safe.

Input: [True, True, True, False, False]

Expected Output: 3

Explanation: Floors 1, 2, and 3 are safe, and floor 4 is the first unsafe floor.

Input: [True, True, True]

Expected Output: 3

Explanation: All floors are safe, so the threshold is the last floor.

Hints

  1. This is equivalent to finding the index of the last `True` value.
  2. If you know how to find the first `False`, you can derive the answer from that too.

Part 2: Shortest Path on a Combination Lock

A lock has four wheels, each showing a digit from `0` to `9`. A state is a 4-character string such as `'0294'`. In one move, you may increment or decrement exactly one wheel by 1, with wraparound (`9 -> 0` and `0 -> 9`). Given a start state, a target state, and a list of blocked states that cannot be visited, return the minimum number of moves needed to reach the target. Return `-1` if it is impossible.

Constraints

  • `start` and `target` are 4-character strings of digits
  • 0 <= len(deadends) <= 10000
  • All blocked states are unique

Examples

Input: ('0000', '0202', ['0201', '0101', '0102', '1212', '2002'])

Expected Output: 6

Explanation: A shortest valid path reaches the target in 6 moves.

Input: ('0000', '8888', ['0001', '0010', '0100', '1000', '0009', '0090', '0900', '9000'])

Expected Output: -1

Explanation: All immediate neighbors of the start are blocked, so no move is possible.

Input: ('1234', '1234', [])

Expected Output: 0

Explanation: The start is already the target.

Input: ('0000', '9000', [])

Expected Output: 1

Explanation: Decrementing the first wheel once wraps from 0 to 9.

Input: ('0000', '0001', ['0000'])

Expected Output: -1

Explanation: The start state itself is blocked, so the search cannot begin.

Hints

  1. Each lock state is a node in an unweighted graph, so think BFS.
  2. From one state, there are exactly 8 next states: for each of 4 wheels, rotate up or down.

Part 3: Nearest Exit in a 2D Grid

You are given a rectangular maze containing walls `'+'` and open cells `'.'`, plus a starting cell `entrance`. You may move up, down, left, or right through open cells only. An exit is any open boundary cell other than the starting cell itself. Return the minimum number of steps needed to reach any exit, or `-1` if no exit exists.

Constraints

  • 1 <= number of rows, columns <= 200
  • `maze[entrance[0]][entrance[1]]` is `'.'`
  • Moves are allowed only in the four cardinal directions

Examples

Input: ([['+','+','.','+'],['.','.','.','+'],['+','+','+','.']], (1, 2))

Expected Output: 1

Explanation: The cell `(0, 2)` is an exit and is one step away.

Input: ([['+','+','+'],['.','.','.'],['+','+','+']], (1, 0))

Expected Output: 2

Explanation: The entrance is on the boundary but does not count; the nearest other exit is `(1, 2)`.

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

Expected Output: -1

Explanation: The only open cell is the entrance, so there is no valid exit.

Input: ([['+','+','+'],['+','.','+'],['+','+','+']], (1, 1))

Expected Output: -1

Explanation: The entrance is completely enclosed by walls.

Hints

  1. Because every move costs the same, BFS gives the shortest path.
  2. Do not count the entrance as an exit even if it lies on the boundary.

Part 4: Seeded Minesweeper Board Generation

Generate a Minesweeper board with exactly `N` mines in a `rows x cols` grid, then fill each non-mine cell with the number of adjacent mines in the 8 surrounding cells. In a real game, the mine positions would be chosen uniformly at random. To make this problem deterministic for testing, use this exact seeded shuffle to choose distinct mine cells: start with `cells = [0, 1, ..., rows*cols-1]` and `x = seed`. For `i` from `rows*cols-1` down to `1`, update `x = (x * 31 + 7) % 9973`, set `j = x % (i + 1)`, and swap `cells[i]` with `cells[j]`. The first `N` values in `cells` are mine positions. Convert a flat index `p` to `(p // cols, p % cols)`. Return a 2D list containing `'*'` for mines and integers for counts.

Constraints

  • 1 <= rows, cols <= 50
  • 0 <= N <= rows * cols
  • Use the exact seeded shuffle described in the statement

Examples

Input: (1, 1, 0, 5)

Expected Output: [[0]]

Explanation: A 1x1 board with no mines contains a single 0.

Input: (2, 2, 4, 0)

Expected Output: [['*', '*'], ['*', '*']]

Explanation: When every cell is a mine, the whole board is filled with `'*'`.

Input: (2, 3, 2, 1)

Expected Output: [[2, '*', 2], [2, '*', 2]]

Explanation: The seeded shuffle places mines at flat indices 1 and 4, which are the two middle-column cells.

Input: (3, 3, 3, 2)

Expected Output: [['*', 1, 0], [2, 3, 2], [1, '*', '*']]

Explanation: The seeded shuffle places mines at flat indices 8, 7, and 0.

Hints

  1. A flat index `p` maps to row `p // cols` and column `p % cols`.
  2. After marking all mines, loop over the mines and increment each valid neighbor if it is not a mine.
Last updated: May 7, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement Minesweeper and Word Search - Uber (medium)
  • Implement Store Autocomplete - Uber (medium)
  • Implement Cache Eviction And Seat Assignment - Uber (medium)
  • Schedule Non-Overlapping Meetings Efficiently - Uber (hard)
  • Evaluate an Arithmetic Expression - Uber