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.

Solve a Key-Door Corridor Maze | Meta Coding Question

Quick Overview

This question evaluates graph search and state-space reasoning by requiring shortest-path computation in a constrained one-dimensional maze with collectible keys and lockable doors, assessing skills in BFS, state encoding, and handling dynamic traversal constraints; Category: Coding & Algorithms.

Solve a Key-Door Corridor Maze

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

AI-assisted coding round. You may use an AI coding assistant, but you are responsible for debugging the implementation and validating the test cases. Implement `shortestSteps(corridor)`, where `corridor` is a one-dimensional maze represented as a string or character array. Each move can go only one position left or one position right. Cells may contain: - `S`: the starting position - `T`: the target position - `.`: an empty cell - `#`: a wall that cannot be crossed - `a`-`f`: keys that can be collected - `A`-`F`: locked doors; door `A` can be crossed only after collecting key `a`, and so on Return the minimum number of moves required to reach `T`, or `-1` if the target is unreachable. Follow-up discussion: - Explain why a BFS implementation without a visited-state set can loop forever. - Explain why the visited state must include both the current position and the set of collected keys, not just the position. - Describe how you would fix incorrect or incomplete test cases for this problem.

Quick Answer: This question evaluates graph search and state-space reasoning by requiring shortest-path computation in a constrained one-dimensional maze with collectible keys and lockable doors, assessing skills in BFS, state encoding, and handling dynamic traversal constraints; Category: Coding & Algorithms.

AI-assisted coding round: you may use an AI coding assistant, but you are responsible for debugging the implementation and validating the test cases. Implement shortestSteps(corridor). For this judge, write a function named solution(corridor). The corridor is a one-dimensional maze represented as a string or character array. From any position, you may move only one step left or one step right. Cells may contain: - 'S': the starting position - 'T': the target position - '.': an empty cell - '#': a wall that cannot be crossed - 'a' to 'f': keys that can be collected - 'A' to 'F': locked doors; door 'A' can be crossed only after collecting key 'a', and so on Once a key is collected, you keep it forever. Return the minimum number of moves required to reach 'T', or -1 if the target is unreachable. Follow-up discussion after coding: - Explain why a BFS that does not track visited states can bounce left and right forever. - Explain why the visited state must include both the current position and the set of collected keys, not just the position. - Explain how you would fix incorrect or incomplete test cases by adding boundary, unreachable, wall, door, and backtracking scenarios, then manually tracing the expected answers.

Constraints

2 <= len(corridor) <= 100000
corridor contains exactly one 'S' and exactly one 'T'
Each cell is one of: 'S', 'T', '.', '#', 'a'-'f', 'A'-'F'
There are at most 6 distinct keys, so the key state can be represented with a bitmask

Examples

Input: ("ST",)

Expected Output: 1

Explanation: The target is immediately to the right of the start, so it takes 1 move.

Input: ("S.aAT",)

Expected Output: 4

Explanation: Move right to '.', then to 'a' to collect the key, then through door 'A', then to 'T': 4 moves total.

Input: ("a.SA.T",)

Expected Output: 7

Explanation: You must go left to collect 'a', then backtrack through the starting area and pass door 'A' to reach 'T'. The path length is 7.

Input: ("SAaT",)

Expected Output: -1

Explanation: Door 'A' blocks the only path to key 'a', so the target is unreachable.

Input: ("S.#.T",)

Expected Output: -1

Explanation: The wall '#' splits the corridor, and there is no way around it in a 1D maze.

Input: (['S', '.', 'b', 'B', 'T'],)

Expected Output: 4

Explanation: This shows the function should also work for a character array input. Collect 'b', pass 'B', then reach 'T' in 4 moves.

Hints

Because every move costs 1, breadth-first search is the right starting point for finding a minimum number of moves.
Reaching the same index with different collected keys can lead to different future moves, so your visited structure should track both index and key-mask.

Quick Overview