Maze with Keys and Doors
Updated
Problem statement
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[]) → intExamples
Example 1
grid = ["$.A.@","####.","a...."]return = 16The 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 = 8Going 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 = -1Key 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 <= 501 <= 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'. gridcontains 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 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)