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

What role is this question designed for?

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

Extend BFS maze solver with keys and arrows

Quick Overview

This question evaluates mastery of breadth-first search, state-space modeling for grid-based traversal, and handling augmented states like keys and one-way tiles, testing competency in algorithm design and correctness within the Coding & Algorithms domain (graph algorithms).

Extend BFS maze solver with keys and arrows

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem You are given a rectangular maze represented as a 2D grid of characters. Implement and iteratively fix/extend a solver that finds a shortest path from **S** (start) to **E** (exit). Movement is 4-directional (up/down/left/right) unless restricted by special tiles. ### Base tiles - `#` = wall (cannot enter) - `.` = empty cell - `S` = start - `E` = exit ### Additional tiles (introduced by later failing tests) - `<` : from this cell, you may move **only left** on the next step - `>` : from this cell, you may move **only right** on the next step - `a`-`f` : keys you can pick up by entering the cell - `A`-`F` : locks; you may enter only if you already have the corresponding key (e.g., `a` opens `A`) ## Tasks (the test suite reveals issues incrementally) 1. **Fix output formatting:** implement a required `print`/render function for the maze and/or found path exactly as specified by the function contract (e.g., return a string with newline-delimited rows; if a path is found, overlay it using `*` except on `S`/`E`). 2. **Fix BFS correctness:** ensure your BFS does not revisit states incorrectly (record `visited` properly). 3. **Support one-way tiles:** update neighbor generation to handle `<` and `>`. 4. **Support keys and locks:** update BFS to include collected keys as part of the state. ## Input/Output Implement a function with the following behavior (language-agnostic): - **Input:** `grid: string[]` (each string is a row) - **Output:** the length of the shortest path from `S` to `E` (number of moves), or `-1` if unreachable. - Additionally, implement any required helper(s) such as `render(grid, path)` depending on the harness. ## Constraints - `1 <= rows, cols <= 200` - Grid contains exactly one `S` and one `E`. - Keys are limited to `a`-`f` (at most 6 distinct keys).

Quick Answer: This question evaluates mastery of breadth-first search, state-space modeling for grid-based traversal, and handling augmented states like keys and one-way tiles, testing competency in algorithm design and correctness within the Coding & Algorithms domain (graph algorithms).

Part 1: Render a Maze Path Exactly

You are given a rectangular maze and a path through it. Write a function that renders the maze as a single string with newline-delimited rows. Each cell in the path should be overlaid with '*' except: - never replace 'S' - never replace 'E' - never replace '#' If the path is empty, return the original maze joined by newlines. The path is given as a list of (row, col) coordinates in any length, and repeated coordinates may appear.

Constraints

1 <= rows, cols <= 200
grid is rectangular

Loading coding console...

Examples

Input: (["S..", ".#E"], [(0, 0), (0, 1), (0, 2), (1, 2)])

Expected Output: "S**\n.#E"

Explanation: The path overlays two '.' cells with '*', while 'S' and 'E' stay unchanged.

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

Expected Output: "SE"

Explanation: A path containing only start and end does not change the maze.

Input: (["S#E", "..."], [])

Expected Output: "S#E\n..."

Explanation: Empty path means the original maze is returned exactly.

Input: (["S.E"], [(0, 0), (0, 1), (0, 2), (0, 1)])

Expected Output: "S*E"

Explanation: Repeated coordinates are harmless; the middle cell is still rendered once as '*'.

Part 2: Shortest Path in a Maze with Correct BFS Visited Handling

You are given a rectangular maze containing only base tiles: - '#' = wall - '.' = empty cell - 'S' = start - 'E' = exit You can move up, down, left, or right by one cell, and you cannot move through walls. Return the length of the shortest path from 'S' to 'E', or -1 if the exit is unreachable. A correct solution must use BFS and track visited cells properly so the search does not revisit the same state unnecessarily.

Constraints

1 <= rows, cols <= 200
grid is rectangular
grid contains exactly one 'S' and one 'E'
Only '#', '.', 'S', and 'E' appear

Examples

Input: ["SE"]

Expected Output: 1

Explanation: The exit is adjacent to the start.

Input: ["S..", ".#.", "..E"]

Expected Output: 4

Explanation: One shortest path is right, right, down, down.

Input: ["S#E"]

Expected Output: -1

Explanation: The wall blocks the only possible route.

Input: ["S...", ".##.", "...E"]

Expected Output: 5

Explanation: The maze contains loops, but BFS with correct visited handling still finds the shortest route.

Hints

In an unweighted grid, BFS is the standard way to find the shortest path.
Mark a cell as visited when you enqueue it, not after you dequeue it.

Part 3: Shortest Path with One-Way Arrow Tiles

You are given a rectangular maze with these tiles: - '#' = wall - '.' = empty cell - 'S' = start - 'E' = exit - '<' = if you are standing on this cell, your next move may only be left - '>' = if you are standing on this cell, your next move may only be right You may enter an arrow tile from any direction. The restriction applies only to moves made from that cell. Return the length of the shortest path from 'S' to 'E', or -1 if unreachable.

Constraints

1 <= rows, cols <= 200
grid is rectangular
grid contains exactly one 'S' and one 'E'
Tiles may be '#', '.', 'S', 'E', '<', '>'

Examples

Input: ["S>E"]

Expected Output: 2

Explanation: From '>' you are forced to continue right into the exit.

Input: ["E<S"]

Expected Output: 2

Explanation: From '<' you are forced left, which reaches the exit.

Input: ["S<E"]

Expected Output: -1

Explanation: After stepping onto '<', you may only go back left, so the exit on the right is unreachable.

Input: ["S#..", ".>#E", "...."]

Expected Output: 6

Explanation: The arrow path is a trap, so the shortest route goes around the bottom row.

Input: ["S.E"]

Expected Output: 2

Explanation: A maze without arrows should still behave like normal BFS.

Hints

The allowed outgoing directions depend on the current cell, not the destination cell.
You can keep BFS unchanged except for the neighbor-generation logic.

Part 4: Shortest Path with Keys and Locks

You are given a rectangular maze with these tiles: - '#' = wall - '.' = empty cell - 'S' = start - 'E' = exit - 'a' to 'f' = keys that are collected permanently when you enter the cell - 'A' to 'F' = locks that can only be entered if you already have the matching key Movement is 4-directional. Important: the unique 'E' tile is always the exit, not a lock. Return the length of the shortest path from 'S' to 'E', or -1 if unreachable. A correct solution must treat '(row, col, collected_keys)' as the BFS state, because revisiting the same cell with more keys can unlock new paths.

Constraints

1 <= rows, cols <= 200
grid is rectangular
grid contains exactly one 'S' and one 'E'
At most 6 distinct keys appear
The exit tile 'E' is not treated as a lock

Examples

Input: ["SE"]

Expected Output: 1

Explanation: The exit is adjacent to the start.

Input: ["SaAE"]

Expected Output: 3

Explanation: Pick up 'a', then pass through lock 'A' to reach the exit.

Input: ["S.AE", ".##.", "a#.."]

Expected Output: 7

Explanation: You must go down to collect the key, then revisit earlier cells to pass through 'A'.

Input: ["SAE"]

Expected Output: -1

Explanation: The lock 'A' blocks the path, and no 'a' key exists.

Hints

A 6-bit bitmask is enough to represent all collected keys.
Visited should include both position and key mask; the same cell may need to be explored again after picking up a key.