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 hard 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 maze score using shortest path

Quick Overview

This question evaluates competency in grid-based pathfinding, graph modeling, and algorithmic complexity analysis for computing shortest paths in discrete spaces.

hard
Airbnb
Coding & Algorithms
Software Engineer

Compute maze score using shortest path

Company: Airbnb

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given a grid-based maze game. - The maze is an `R x C` grid of characters: - `'#'` = wall (cannot pass) - `'.'` = empty cell - `'S'` = current player position (exactly one) - `'E'` = exit/goal (exactly one) - The game “score” for a state is defined as the length of the shortest path (minimum number of moves) from `S` to `E`, moving 4-directionally (up/down/left/right) and not passing through walls. - If `E` is unreachable, return `-1`. Write a function that takes the maze grid and returns the score. Clarify in your solution: - Time and space complexity - How you would adapt it if the game state were provided separately as `(startRow, startCol)` instead of embedding `'S'` in the grid.

Quick Answer: This question evaluates competency in grid-based pathfinding, graph modeling, and algorithmic complexity analysis for computing shortest paths in discrete spaces.

You are given a grid-based maze game represented as a list of strings. Each cell contains one of the following characters: '#' for a wall, '.' for an empty cell, 'S' for the player's current position, and 'E' for the exit. The maze score is defined as the length of the shortest path from 'S' to 'E', moving only up, down, left, or right, and never passing through walls. If the exit cannot be reached, return -1.

Constraints

1 <= R, C <= 200
All rows have the same length
There is exactly one 'S' and exactly one 'E'
Movement is allowed only in 4 directions: up, down, left, right

Examples

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

Expected Output: 4

Explanation: A shortest path is right, right, down, down for a total of 4 moves.

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

Expected Output: -1

Explanation: Walls block every possible route from S to E.

Input: (['SE'],)

Expected Output: 1

Explanation: The exit is directly adjacent to the start in a single-row maze.

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

Expected Output: 5

Explanation: One shortest path is (2,0)->(2,1)->(2,2)->(2,3)->(1,3)->(0,3), which uses 5 moves.

Input: (['S', '.', '.', 'E'],)

Expected Output: 3

Explanation: In this single-column maze, you move down 3 times to reach the exit.

Loading coding console...

Quick Overview

Compute maze score using shortest path

Constraints

Examples

Hints