Quick Overview

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.

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.

Overview: 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

Hints

  1. Model the navigation as following edges in a directed graph where each node has at most one outgoing edge.
  2. Use a visited set to detect if a URL is revisited (cycle).
  3. Check for terminal responses with a prefix test on 'END:'.
  4. If a next URL is not found in the mapping, return 'INVALID'.

Loading coding console...

Show the approach

Approach

The problem is graph traversal where each URL has exactly one out-edge: it either points to another URL or terminates with an END: response. Because every node has at most one successor, we're walking a single deterministic chain, so a simple loop suffices — no recursion or BFS/DFS machinery needed.

Approach: Keep a visited set of URLs we've already processed and a current pointer that starts at start. Each iteration does three checks in order:

  1. Cycle check — if current is already in visited, we've come back to a URL we saw before, so the chain loops forever: return "LOOP".
  2. Mark current as visited, then next_value = links.get(current).
  3. Dead-end check — if next_value is None, current isn't a key in links (this also covers the case where start itself is missing): return "INVALID".
  4. Terminal check — if next_value.startswith("END:"), the response is terminal; return everything after the 4-character "END:" prefix via next_value[4:].
  5. Otherwise next_value is the next URL; set current = next_value and continue.

Why it's correct: The visited set guarantees termination — each URL is processed at most once, so we either hit an END: value, fall off into a missing key, or revisit a node (the only way an infinite chain manifests). The ordering matters: we check for a loop before looking the node up, so a self-cycle is caught rather than mistaken for a dead end. Using links.get() rather than in + indexing folds the membership test and lookup into one operation.

Time complexity:
O(n) where n is the number of distinct URLs along the path; each URL is visited at most once and string operations (`get`, `startswith`, slice) are bounded by URL/value length.
Space complexity:
O(n) for the `visited` set, which holds at most n distinct URLs before a terminal/invalid/loop result is returned.