FastPrepMaze with Keys and Doors
Problems/Maze with Keys and Doors

Maze with Keys and Doors

Airbnb logoAirbnb● HardINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Airbnb software engineer intern interview in Atlanta, Georgia, in October 2019. It was one of two questions in a two-hour online video interview. The task was a maze given as a grid of strings, where lowercase letters are keys, uppercase letters are doors and # marks a wall, and you find the fastest path through it.

The report gives no symbols for the start and the exit, no movement rules, no limits and no examples. Here, the start is @ and the exit is $, you move one cell up, down, left or right per step, a key is picked up when you step on it and opens every door with the same letter for the rest of the trip, keys and doors use the letters a to f, and you return -1 when the exit cannot be reached. The limits and examples are our own.

Our version is about 75% the same as the reported question.

You are given a maze as an array of strings grid. Each string is one row, and each character is one cell:

  • '@' is your starting cell.
  • '$' is the exit.
  • '.' is an empty cell.
  • '#' is a wall.
  • A lowercase letter from 'a' to 'f' is a key.
  • An uppercase letter from 'A' to 'F' is a door.

In one move, you step to the cell directly above, below, left or right of you. You cannot leave the grid or step onto a wall. When you step onto a key, you pick it up and keep it for the rest of the trip. A key opens every door with the same letter in uppercase, as many times as you like: key 'a' opens all doors 'A'. You can step onto a door only while you hold its key. You may pass through any cell, including the start, any number of times.

Return the fewest moves needed to reach the exit from the start, or -1 if the exit cannot be reached.

Function

fastestPath(grid: String[]) → int

Examples

Example 1

grid = ["$.A.@","####.","a...."]return = 16
grid
012340$.A.@1####.2a....

The door A at row 0, column 2 blocks the short way to the exit, and the walls leave no way around it. The only key a is in the bottom-left corner.

Walk down and along the bottom row to the key: 6 moves. The bottom row is a dead end at the key, so walk back the same way to the start: 6 more moves. From the start, the exit is 4 moves away through the now open door. The total is 6 + 6 + 4 = 16.

Example 2

grid = ["@.A.$","#.#.#","a...."]return = 8
grid
012340@.A.$1#.#.#2a....

Going around the door takes 8 moves: right to column 1, down to the bottom row, right to column 3, up to the top row, and right to the exit.

Fetching the key a first takes 4 moves, and the trip from the key back up through the door to the exit takes 6 more, so that path has 10 moves. Keys are optional, and the fastest path skips this one.

Example 3

grid = ["@aB$"]return = -1
grid
01230@aB$

Key a opens only doors marked A. No b key exists, so door B never opens, and the exit cannot be reached.

Constraints

  • 1 <= grid.length <= 50
  • 1 <= grid[i].length <= 50
  • All rows have the same length.
  • Each grid[i][j] is one of '@', '$', '.', '#', a lowercase letter from 'a' to 'f', or an uppercase letter from 'A' to 'F'.
  • grid contains exactly one '@' and exactly one '$'.

More Airbnb Phone Screen questions

  • Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
  • Text JustificationPHONE SCREEN · Seen Nov 2026
  • Decode and Store StringsPHONE SCREEN · Seen Oct 2026
  • Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
  • Smallest Common RegionPHONE SCREEN · Seen Aug 2026
  • Longest Chain BookingPHONE SCREEN · Seen Aug 2026
  • Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
  • Parse Query StringPHONE SCREEN · Seen May 2026
  • Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023

Similar questions at other companies

  • Car to Oasis with Gas StationsBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Competitive ForagingAkuna Capital · OAAkuna Capital interview questions
  • Escape the Haunted Castle with TreasuresPersona · OAPersona interview questions
  • Swim in Rising WaterUiPath · PHONE SCREEN
  • Choose the Next Minesweeper ActionRunloop · PHONE SCREEN
  • Find the Safest Path in a GridAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Shortest Distance from All BuildingsWaymo · PHONE SCREENWaymo interview questions
  • Shortest Path in a Grid with Obstacles EliminationMercor · PHONE SCREENMercor interview questions
  • Maximum-Clearance Path From a PointGoogle · PHONE SCREENGoogle interview questions
  • Sliding PuzzleNVIDIA · PHONE SCREENNVIDIA interview questions

Interview reports that mention this question

  • Airbnb Intern Phone Interviews: 21 Experiences (Part 7 of 7)

Airbnb interview experiences

  • Airbnb SWE OA: Four-Level Banking System: 1 Experience
  • Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
  • Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
  • Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
  • Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)
All Airbnb interview questionsSee Airbnb hiring insights
Saved
class Solution {
    public int fastestPath(String[] grid) {
      // Write your code here.
    }
}
Checking account…