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 Airbnb.

What role is this question designed for?

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

Compute shortest path to collect all keys

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given an m×n grid containing walls (#), open cells (.), a single start cell (@), up to six keys labeled 'a'–'f', and matching doors 'A'–'F' that can be passed only after obtaining their corresponding key. From any cell, you may move one step up, down, left, or right to an in-bounds non-wall cell. Return the minimum number of steps required to collect all keys, or -1 if it is impossible. Handle m, n up to 30. Describe your state representation, search strategy, pruning, and how you detect revisits efficiently. Provide time and space complexity and key test cases.

Quick Answer: This question evaluates proficiency in state-space representation, graph search and shortest-path techniques, compact state encoding (such as bitmasking), and algorithmic time/space complexity analysis within the Coding & Algorithms domain.

You are given a rectangular grid represented as a list of strings. Each cell contains one of the following characters: '#' for a wall, '.' for an open cell, '@' for the single starting cell, lowercase letters 'a' to 'f' for keys, and uppercase letters 'A' to 'F' for doors. You may move one step up, down, left, or right onto any in-bounds cell that is not a wall. A door can be entered only if you have already collected its corresponding lowercase key. Return the minimum number of steps required to collect all keys, or -1 if it is impossible. Because the set of collected keys changes what doors you can pass, reaching the same grid cell with different key sets must be treated as different search states. Your solution should be efficient for grids up to 30 x 30.

Constraints

1 <= m, n <= 30
grid[i][j] is one of '#', '.', '@', 'a' - 'f', or 'A' - 'F'
There is exactly one starting cell '@'
There are at most 6 keys, and each door matches a key with the same letter ignoring case

Examples

Input: (["@.a..","###.#","b.A.B"],)

Expected Output: 8

Explanation: You must collect 'a' first, then pass through door 'A' to eventually reach 'b'. The shortest valid route takes 8 steps.

Input: (["@..aA","..B#.","....b"],)

Expected Output: 6

Explanation: Collect 'a' in 3 steps, then move through door 'A' and continue to 'b'. The minimum is 6.

Input: (["@Aa"],)

Expected Output: -1

Explanation: Door 'A' blocks the only path to key 'a', so the key can never be collected.

Input: (["@"],)

Expected Output: 0

Explanation: There are no keys in the grid, so zero steps are needed.

Input: (["@...a","###A#","b...."],)

Expected Output: 10

Explanation: The lower row is only reachable through door 'A', so you must collect 'a' first and then go back to unlock the route to 'b'.

Solution

def solution(grid):
    from collections import deque

    if not grid or not grid[0]:
        return -1

    m, n = len(grid), len(grid[0])
    start = None
    all_keys_mask = 0

    for r in range(m):
        for c in range(n):
            ch = grid[r][c]
            if ch == '@':
                start = (r, c)
            elif 'a' <= ch <= 'f':
                all_keys_mask |= 1 << (ord(ch) - ord('a'))

    if start is None:
        return -1
    if all_keys_mask == 0:
        return 0

    sr, sc = start
    visited = [[[False] * 64 for _ in range(n)] for _ in range(m)]
    visited[sr][sc][0] = True

    queue = deque([(sr, sc, 0, 0)])  # row, col, key_mask, steps
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:
        r, c, key_mask, steps = queue.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            if nr < 0 or nr >= m or nc < 0 or nc >= n:
                continue

            cell = grid[nr][nc]
            if cell == '#':
                continue

            if 'A' <= cell <= 'F':
                needed = 1 << (ord(cell) - ord('A'))
                if (key_mask & needed) == 0:
                    continue

            new_mask = key_mask
            if 'a' <= cell <= 'f':
                new_mask |= 1 << (ord(cell) - ord('a'))
                if new_mask == all_keys_mask:
                    return steps + 1

            if not visited[nr][nc][new_mask]:
                visited[nr][nc][new_mask] = True
                queue.append((nr, nc, new_mask, steps + 1))

    return -1

Time complexity: O(m * n * 2^k), where k is the number of keys and k <= 6. Space complexity: O(m * n * 2^k).

Hints

A normal BFS over just (row, col) is not enough, because arriving at the same cell with different keys collected can lead to different future moves.
Since there are at most 6 keys, encode the collected keys as a bitmask and use (row, col, key_mask) as your BFS state and visited marker.

Quick Overview

This question evaluates proficiency in state-space representation, graph search and shortest-path techniques, compact state encoding (such as bitmasking), and algorithmic time/space complexity analysis within the Coding & Algorithms domain.