Katkat
Back

Solve Maze and Suffix Problems

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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:

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:

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.