Solve Maze and Suffix Problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Solve the following two coding problems.
## Problem A: Find the shortest path through a maze with keys and doors
You are given a 2D grid representing a maze.
Each cell contains one of the following characters:
- `S`: starting position
- `E`: exit position
- `.`: empty cell
- `#`: wall
- `a` to `z`: key
- `A` to `Z`: locked door
You may move one cell at a time in four directions: up, down, left, and right. You cannot move through walls. You may pass through a door only if you have already collected the corresponding lowercase key. For example, you can pass through `B` only after collecting `b`.
Return the minimum number of steps required to move from `S` to `E`. If the exit cannot be reached, return `-1`.
Your solution should correctly handle revisiting the same grid cell with different sets of collected keys.
Example:
```text
grid = [
"S.a",
"##A",
"..E"
]
```
The shortest valid path must collect key `a` before passing through door `A`.
Constraints:
- `1 <= rows, cols <= 100`
- The number of distinct keys is at most `6`.
## Problem B: Optimize suffix queries over a word container
You are given an array `words` and an array `queries`.
For each query string, return the index of the word in `words` that has the longest common suffix with the query.
Tie-breaking rules:
1. Prefer the word with the longest common suffix.
2. If multiple words have the same suffix length, prefer the shorter word.
3. If there is still a tie, prefer the smaller index.
A brute-force implementation compares every query with every word. Identify the bottleneck and implement a more efficient approach. You may consider designs such as a reversed trie or a hash-based suffix map. Add your implementation to a benchmark harness and compare runtime and memory usage against the brute-force version.
Example:
```text
words = ["battle", "little", "kettle", "cat"]
queries = ["settle", "flat", "rattle"]
```
Expected behavior:
- `"settle"` matches suffix `"ttle"` with `"little"` and `"kettle"`; choose the shorter word if applicable, then the smaller index.
- `"flat"` matches suffix `"at"` with `"cat"`.
- `"rattle"` matches suffix `"ttle"` with multiple candidates and uses the tie-breaking rules.
Constraints:
- `1 <= words.length, queries.length <= 100000`
- The total number of characters across all words and queries can be large, so an `O(words.length * queries.length * average_length)` solution is not acceptable for production-scale input.
Quick Answer: This two-part question evaluates stateful graph traversal and shortest-path reasoning under key-and-door constraints, alongside efficient string-suffix matching and scalable data-structure design, testing competencies in state management, graph/search algorithms, string algorithms, and algorithmic optimization.
Part 1: Shortest Path in a Maze with Keys and Doors
You are given a rectangular grid of characters representing a maze. Exactly one cell contains 'S' (the start) and exactly one cell contains 'E' (the exit). Other cells may contain '.' for open space, '#' for a wall, lowercase letters 'a' to 'z' for keys, and uppercase letters 'A' to 'Z' for locked doors.
You may move one cell at a time in four directions: up, down, left, and right. You cannot move through walls. You may enter a door only if you have already collected its matching lowercase key. When you step on a key, you keep it forever.
Return the minimum number of steps needed to reach 'E' from 'S'. If the exit cannot be reached, return -1.
Important: reaching the same cell with different sets of collected keys must be treated as different states.
Constraints
- 1 <= number of rows, number of columns <= 100
- grid is rectangular
- The grid contains exactly one 'S' and one 'E'
- The number of distinct keys in the grid is at most 6
Examples
Input: ['S.a', '##A', '..E']
Expected Output:
Explanation: You must collect key 'a' before passing through door 'A'. One shortest path has length 4.
Input: ['SE']
Expected Output:
Explanation: The exit is adjacent to the start.
Hints
- A plain BFS over cells is not enough. Your state should include both position and which keys you currently hold.
- Since there are at most 6 distinct keys, you can encode the collected keys as a bitmask.
Part 2: Longest Common Suffix Query
You are given two arrays of strings: words and queries.
For each query, return the index of the word in words that has the longest common suffix with that query.
Tie-breaking rules:
1. Prefer the word with the longer common suffix.
2. If multiple words have the same suffix length, choose the shorter word.
3. If there is still a tie, choose the smaller index.
If no word shares a non-empty suffix with the query, treat the common suffix length as 0 and apply the same tie-breaking rules.
A brute-force solution that compares every query against every word is too slow. Implement an efficient solution.
Constraints
- 1 <= len(words), len(queries) <= 100000
- 1 <= len(word), len(query) <= 100000
- Strings consist of lowercase English letters
- The total number of characters across all words and queries is at most 200000
Examples
Input: (['battle', 'little', 'kettle', 'cat'], ['settle', 'flat', 'rattle'])
Expected Output:
Explanation: 'settle' matches 'kettle' on suffix 'ettle' of length 5. 'flat' matches 'cat' on 'at'. 'rattle' matches 'battle' on 'attle' of length 5.
Input: (['abcd', 'bcd', 'xcd', 'zzcd'], ['yycd', 'abcd'])
Expected Output:
Explanation: For 'yycd', the best suffix length is 2 ('cd'). Among candidates, 'bcd' and 'xcd' are the shortest, so choose smaller index 1. For 'abcd', the full word matches index 0.
Hints
- Suffix comparisons become prefix comparisons if you reverse every string.
- For each node of a reversed trie, store the best index among all words passing through that node using the tie-break rules for equal suffix length.