Breadth-First Search Questions at Samsung: What to Expect

Breadth-First Search (BFS) is a core algorithm for Samsung coding interviews. With 10 out of their 69 total tagged questions, it’s one of their most frequently assessed topics. Samsung’s problems often involve modeling real-world systems—like network routing, robot navigation, or circuit simulation—where you must find the shortest path or minimum steps in a state space. BFS is the natural tool for these scenarios because it systematically explores all possibilities level by level, guaranteeing the first solution found is the shortest in an unweighted graph.

What to Expect — Types of Problems

Samsung’s BFS questions rarely present as simple graph traversals. You’ll typically need to adapt the algorithm to a complex grid or state-based problem.

1. Grid-Based Shortest Path: The most common type. You’re given an N x M grid with obstacles (walls, fire, water) and a starting point. The goal is to find the minimum steps to reach a target or exit. Variations include moving in 4 or 8 directions, or having keys that unlock doors.
2. Multi-Source BFS: Problems where multiple starting points exist simultaneously, like multiple fires spreading or several agents starting a search. The solution initializes the queue with all sources.
3. State-Aware BFS (BFS on a Graph of States): The “node” in your search isn’t just a coordinate; it’s a state (e.g., position + keys collected + time elapsed). This expands the visited dimension beyond a simple 2D array to a higher-dimensional space (e.g., visited[x][y][key_bitmask]).
4. Simulation + BFS: The problem requires you to simulate a process (like block falling, water flow, or infection spread) and use BFS to find the outcome after a certain number of steps or the steps to reach a condition.

How to Prepare — Study Tips with One Code Example

Master the standard BFS template for a grid. Then, practice identifying the “state” you need to track. Your visited data structure must account for all unique aspects of that state to avoid cycles.

A key pattern is Multi-Source BFS. Imagine a grid where several cells are starting points (e.g., rotten oranges, fire sources). Instead of doing BFS from each source separately, you initialize the queue with all sources at distance 0. This efficiently simulates simultaneous expansion.

from collections import deque

def multi_source_bfs(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    # Initialize: push all source cells into queue
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:  # Source
                queue.append((r, c, 0))  # (row, col, distance)
    # Directions
    dirs = [(0,1), (1,0), (0,-1), (-1,0)]
    max_distance = 0
    while queue:
        r, c, dist = queue.popleft()
        max_distance = max(max_distance, dist)
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                grid[nr][nc] = 1  # Mark as visited/processed
                queue.append((nr, nc, dist + 1))
    return max_distance

Recommended Practice Order

1. Start with classic grid BFS (Number of Islands, Shortest Path in Binary Matrix).
2. Practice Multi-Source BFS (Rotting Oranges, Walls and Gates).
3. Tackle State-Aware BFS problems (Shortest Path to Get All Keys).
4. Finally, solve Samsung’s specific, often more complex, problem variations. These integrate the above patterns within intricate scenarios.

Practice Breadth-First Search at Samsung