Katkat
Back

Implement Minesweeper and Word Search

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate 2D grids using BFS/DFS for board traversal and randomized state generation.

Part 1: Minesweeper Board Generation

Given a grid of size m x n and an integer k representing the number of mines, implement a function to generate a board. The board should be initialized with '0'. Randomly place k mines ('M'), then update all non-mine cells with the count of adjacent mines (0-8).

def generate_minesweeper(m: int, n: int, k: int) -> List[List[str]]:

Part 2: Word Search

Given a 2D board of characters and a word string, determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically). The same letter cell may not be used more than once.

def exist(board: List[List[str]], word: str) -> bool:

Constraints

  • 1 <= m, n <= 50
  • 0 <= k <= m * n
  • word length is 1 <= len <= 100

Example 1 (Minesweeper)

Input: m=3, n=3, k=2 Output:

[['1', 'M', '1'],
 ['1', '2', '2'],
 ['0', '1', 'M']]

Example 2 (Word Search)

Input: `board = [['A','B','C'],['D','E','F']], word = "ABED" Output: True

Edge Cases

  • Minesweeper: k=0 or k=m*n.
  • Word Search: word longer than the number of cells; grid containing empty strings.

Hints

Hint 1

For Minesweeper, use a set of coordinates to ensure you place exactly k unique mines before calculating neighbors.

Hint 2

For Word Search, use backtracking with a visited array or temporarily modify the grid to track current path traversal.

Hint 3

Consider the time complexity of the word search: for each cell, you potentially start a DFS of depth equal to the length of the word.

Follow-up questions

  • How would you optimize the Minesweeper generation if the board is extremely sparse (k is very small relative to m*n)?
  • How can you modify the word search to allow diagonal movement?
  • If the grid is too large to fit into memory, how would you approach the word search problem?