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 medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Implement Minesweeper and Word Search

Quick Overview

This multi-part prompt evaluates grid-based algorithmic skills, including randomized board construction with neighbor counting, straight-line pattern matching across eight directions, and path-based word search using horizontally/vertically adjacent cells.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Solve the following coding problems. ## Problem 1: Generate and Print a Minesweeper Board You are given integers `rows`, `cols`, and `mineCount`. Generate a `rows x cols` Minesweeper board containing exactly `mineCount` mines placed at random distinct cells. Represent the board as a 2D array of characters: - `'*'` represents a mine. - A digit `'0'` through `'8'` represents the number of adjacent mines around that cell. Adjacent cells include all 8 directions: horizontal, vertical, and diagonal. Return or print the completed board. Example: ```text Input: rows = 3, cols = 4, mineCount = 2 One possible output: 0 1 * 1 0 1 1 1 0 0 0 0 ``` Because the mines are placed randomly, multiple valid outputs are possible. Clarify how you would handle invalid input, such as `mineCount > rows * cols`. ## Problem 2: Search for a Word in a Straight Line You are given a 2D grid of characters and a target word. Determine whether the word appears in the grid in a single straight line. The word may be read in any of the 8 directions: - left to right - right to left - top to bottom - bottom to top - the 4 diagonal directions A valid match must use consecutive cells in one fixed direction. You may not turn while matching the word. Return `true` if the word exists; otherwise return `false`. Example: ```text Grid: A B C E S F C S A D E E word = "ABCC" Output: false word = "SEE" Output: true ``` ## Problem 3: Search for a Word by Adjacent Cells You are given a 2D grid of characters and a target word. Determine whether the word can be formed by moving between horizontally or vertically adjacent cells. Rules: - Each step may move up, down, left, or right. - The same cell may not be used more than once in a single word path. - Return `true` if the word can be formed; otherwise return `false`. Example: ```text Grid: A B C E S F C S A D E E word = "ABCCED" Output: true word = "SEE" Output: true word = "ABCB" Output: false ```

Quick Answer: This multi-part prompt evaluates grid-based algorithmic skills, including randomized board construction with neighbor counting, straight-line pattern matching across eight directions, and path-based word search using horizontally/vertically adjacent cells.

Part 1: Generate a Minesweeper Board from Given Mine Positions

Build the final Minesweeper board after the mine locations have already been chosen. To keep the problem deterministic and testable, you are given the exact mine coordinates instead of placing mines randomly. Each mine cell contains '*'. Every non-mine cell contains the number of adjacent mines in the 8 surrounding directions. If the input is invalid, return an empty list. Invalid input includes non-positive dimensions, duplicate mine positions, or mine coordinates that fall outside the board.

Constraints

1 <= rows, cols <= 200
0 <= len(mine_positions) <= rows * cols
Each mine position must be a distinct pair (r, c) with 0 <= r < rows and 0 <= c < cols
Return [] for invalid dimensions, duplicates, malformed coordinates, or out-of-bounds positions

Examples

Input: (3, 4, [(0, 2), (2, 3)])

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

Explanation: The counts are based on the two mines at positions (0, 2) and (2, 3).

Input: (1, 1, [(0, 0)])

Expected Output: [['*']]

Explanation: Single-cell board containing a mine.

Input: (2, 2, [])

Expected Output: [['0', '0'], ['0', '0']]

Explanation: No mines means every cell has zero adjacent mines.

Input: (2, 2, [(0, 0), (0, 0)])

Expected Output: []

Explanation: Duplicate mine coordinates are invalid.

Hints

Place all mines first, then update the 8 neighbors of each mine.
Use a set to detect duplicate mine coordinates quickly.

Part 2: Search for a Word in a Straight Line

Given a rectangular grid of characters and a target word, determine whether the word appears in one straight, unbroken line. You may start at any cell and move in any one of the 8 directions: horizontal, vertical, or diagonal. Once a direction is chosen, it must remain fixed for the entire word. Return True if the word exists; otherwise return False. An empty word should return True.

Constraints

0 <= number of rows, number of cols <= 200
The grid is rectangular if non-empty
0 <= len(word) <= 10^4
Grid cells contain single-character strings

Examples

Input: ([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'ABC')

Expected Output: True

Explanation: ABC appears horizontally from left to right in the first row.

Input: ([['C', 'A', 'T'], ['X', 'A', 'X'], ['T', 'A', 'C']], 'CAC')

Expected Output: True

Explanation: CAC appears diagonally from the top-left to the bottom-right.

Input: ([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'ABCC')

Expected Output: False

Explanation: A match would require a turn, which is not allowed.

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

Expected Output: True

Explanation: A single matching cell is a valid straight-line match.

Input: ([], 'A')

Expected Output: False

Explanation: A non-empty word cannot be found in an empty grid.

Hints

Only start searching from cells that match the first letter.
For each starting cell, try all 8 directions and check whether the whole word stays in bounds.

Part 3: Search for a Word by Adjacent Cells

Given a rectangular grid of characters and a target word, determine whether the word can be formed by moving between horizontally or vertically adjacent cells. You may not reuse the same cell more than once in a single path. Return True if the word can be formed; otherwise return False. An empty word should return True.

Constraints

0 <= number of rows, number of cols <= 6
The grid is rectangular if non-empty
0 <= len(word) <= 15
Grid cells contain single-character strings

Examples

Input: ([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'ABCCED')

Expected Output: True

Explanation: The word can be formed by moving through adjacent cells without reusing any cell.

Input: ([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'SEE')

Expected Output: True

Explanation: A valid path exists using adjacent cells.

Input: ([['A', 'B', 'C', 'E'], ['S', 'F', 'C', 'S'], ['A', 'D', 'E', 'E']], 'ABCB')

Expected Output: False

Explanation: The word would require reusing a cell, which is not allowed.

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

Expected Output: True

Explanation: Single-cell board with a matching one-letter word.

Input: ([['A', 'B'], ['C', 'D']], '')

Expected Output: True

Explanation: The empty word is always considered found.

Hints

This is a depth-first search with backtracking: mark a cell as used while exploring, then restore it.
Before searching, compare character counts in the board and in the word to quickly reject impossible cases.

Quick Overview