Solve maze tasks and compute shortest routes
Quick Overview
This multi-part question evaluates proficiency in grid-based pathfinding and shortest-path reasoning, debugging and incremental code extension, handling weighted or multi-target graph variants, ordered route planning across multiple targets, and array-based techniques for detecting duplicate and missing elements, situating it within the coding & algorithms domain that spans graph theory and array/data-structure problems. It is commonly asked to assess both practical implementation ability and algorithmic reasoning under constraints (such as large grids and input sizes), testing conceptual understanding of search and complexity trade-offs as well as practical application and optimization in code.
You are given two coding exercises from an interview loop.
Problem A: Incremental “maze” codebase tasks (AI-assisted)
You inherit an existing codebase that models a maze as a 2D grid and exposes a function to navigate from a start cell to a target cell.
-
The maze is a matrix of characters:
-
'.'= open cell -
'#'= wall -
'S'= start (exactly one) -
'T'= target (exactly one)
-
- Movement: 4-directional (up/down/left/right), each move costs 1.
You will be asked to complete 4 sequential tasks, each building on the previous one:
-
Fix bugs
in the existing pathfinding logic (e.g., incorrect boundary checks, visited-handling, or queue/stack usage) so that it correctly determines whether
Tis reachable fromS. -
Extend the function to return the
length of the shortest path
from
StoT(or-1if unreachable). - Extend it to return one valid shortest path as a list of coordinates (or moves), not just the length.
-
Add one new feature to the maze model (example features an interviewer might choose):
- support multiple targets and return the nearest,
- support weighted terrain (different move costs),
- support portals/teleporters marked by matching letters.
Clarify any ambiguous requirements with the interviewer. Implement the required functions and explain how you validated correctness.
Problem B: Route planning to visit cells in increasing order
You are given an m x n grid of integers:
-
0= blocked cell -
1= empty traversable cell -
>1= a “tree” (or work item) with a height/value
You start at (0,0) and can move 4-directionally. You must visit and “process” all cells with value > 1 in increasing order of value. Processing a tree does not change traversability.
Return the minimum total number of steps to process all trees in order, or -1 if any required tree is unreachable at the time it must be processed.
Problem C: Find the duplicate and missing number
You are given an array nums of length n that should contain every integer from 1 to n exactly once, but instead:
- one number is duplicated, and
- one number is missing.
Return [duplicate, missing].
Constraints (for all problems)
Assume m, n <= 10^3 for grid problems and n <= 10^5 for the array problem unless otherwise stated by the interviewer.