How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen 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 a Maze Solver | Meta Interview Question

Quick Overview

This question evaluates algorithmic problem-solving and software engineering skills, specifically graph traversal (BFS), state-space modeling for keys and doors, handling movement constraints, and debugging an existing codebase within the Coding & Algorithms domain.

You are given an existing codebase for a maze game and solver. The maze is represented as a 2D grid containing:

S : start cell
T : target cell
. : open cell
# : wall

Movement is allowed in the four cardinal directions.

Complete the following tasks progressively:

Fix the existing implementation so that the provided unit tests for basic maze traversal pass.
Implement shortest-path search using BFS . Add a function that returns the minimum number of moves from S to T , or -1 if the target is unreachable.
Add movement restrictions . Update the move logic so that certain directional constraints are enforced during traversal, such as disallowing specific moves based on the previous move or the current cell's rules.
Support keys and doors . Extend the maze so that lowercase letters such as a , b , c represent keys, and uppercase letters such as A , B , C represent doors. A door may only be passed after collecting its matching key. The solver must still return the minimum number of moves required to reach T .

Your implementation should correctly track search state, handle revisits only when beneficial, and remain compatible with the existing test-driven codebase.

Quick Overview

You are given an existing codebase for a maze game and solver. The maze is represented as a 2D grid containing:

S : start cell
T : target cell
. : open cell
# : wall

Movement is allowed in the four cardinal directions.

Complete the following tasks progressively:

Fix the existing implementation so that the provided unit tests for basic maze traversal pass.
Implement shortest-path search using BFS . Add a function that returns the minimum number of moves from S to T , or -1 if the target is unreachable.
Add movement restrictions . Update the move logic so that certain directional constraints are enforced during traversal, such as disallowing specific moves based on the previous move or the current cell's rules.
Support keys and doors . Extend the maze so that lowercase letters such as a , b , c represent keys, and uppercase letters such as A , B , C represent doors. A door may only be passed after collecting its matching key. The solver must still return the minimum number of moves required to reach T .

Your implementation should correctly track search state, handle revisits only when beneficial, and remain compatible with the existing test-driven codebase.

Extend a Maze Solver

Quick Overview

Submit Your Answer

Extend a Maze Solver

Quick Overview

Submit Your Answer