Navigate maze via HTTP API
Company: Ramp
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Implement a program that repeatedly calls a provided HTTP API which returns the next URL in a maze; continue following the URLs until reaching the end of the maze and output the final result.
Quick Answer: This question evaluates a candidate's ability to implement programmatic traversal of linked resources via an HTTP API, testing skills in network I/O, control flow, state management, and algorithmic traversal.
Follow a chain of URL redirects until you reach a terminal response, then return its result.
You are given a dictionary `links` that maps **URL strings** to **response strings**, and a **start URL** `start`. Each response is one of two kinds:
- A **terminal response** of the form `'END:<result>'` (the literal prefix `END:` followed by some result text).
- Another **URL** to follow next (which should itself be a key in `links`).
## Task
Implement the function:
```python
def navigate_maze(links: dict[str, str], start: str) -> str:
```
Starting at `start`, repeatedly process the **current URL** as follows:
1. **Loop check (first).** If you have *already visited* the current URL during this walk, the chain cycles forever — return the string `'LOOP'`.
2. **Look up** the current URL in `links`.
- If the current URL is **not a key** in `links`, return the string `'INVALID'`. (This also applies when `start` itself is not a key.)
3. **Terminal check.** If the looked-up response **begins with** `'END:'`, return the substring that comes **after** the `'END:'` prefix as the final result.
4. **Follow.** Otherwise, treat the response as the **next URL**: make it the current URL and repeat from step 1.
## Return value
Return a single string:
- The text after `'END:'` when a terminal response is reached.
- `'LOOP'` if a previously visited URL is revisited (a cycle).
- `'INVALID'` if you ever need to follow a URL that is not present in `links` (including when `start` is missing).
## Notes
- The loop check is performed **before** looking the URL up, so a URL that points back to itself (or to any earlier URL in the walk) is reported as `'LOOP'`, not `'INVALID'`.
- The `'END:'` prefix is exactly four characters; the result is everything after it (which may be empty).
## Constraints
- `1 <= len(links) <= 100000`
- Each key in `links` is a unique URL string.
- Each value in `links` is either another URL (a key in `links`) or a terminal `'END:<result>'` string.
- `start` is a non-empty string.
## Examples
| `links` | `start` | Output |
|---|---|---|
| `{"A": "B", "B": "END:success"}` | `"A"` | `"success"` |
| `{"x": "y", "y": "z", "z": "x"}` | `"x"` | `"LOOP"` |
| `{"A": "C", "B": "END:ok"}` | `"A"` | `"INVALID"` |
| `{"start": "END:reached"}` | `"start"` | `"reached"` |
| `{"A": "END:ok"}` | `"missing"` | `"INVALID"` |
Constraints
- 1 <= len(links) <= 100000
- Each key in links is a unique URL string
- Each value in links is either another URL (a key in links) or a terminal 'END:<result>' string
- start is a non-empty string
- If a cycle is encountered, return 'LOOP'
- If a non-terminal response refers to a URL not present in links (including start not present), return 'INVALID'
Examples
Input:
Expected Output: success
Input:
Expected Output: LOOP
Input:
Expected Output: INVALID
Input:
Expected Output: reached
Input:
Expected Output: finish
Input:
Expected Output: INVALID
Hints
- Model the navigation as following edges in a directed graph where each node has at most one outgoing edge.
- Use a visited set to detect if a URL is revisited (cycle).
- Check for terminal responses with a prefix test on 'END:'.
- If a next URL is not found in the mapping, return 'INVALID'.