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.
You are given a mapping links from URL strings to response strings. Each response is either another URL to follow or a terminal response of the form 'END:<result>'. Starting from the given start URL, repeatedly look up the current URL in links and process its response: if the response begins with 'END:', return the substring after 'END:' as the final result; otherwise, treat the response as the next URL and continue. If you encounter a URL that you have already visited, return 'LOOP'. If you need to follow a URL that is not a key in links (including if start is not a key), return 'INVALID'. Implement the function navigate_maze.
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
Solution
def navigate_maze(links: dict[str, str], start: str) -> str:
visited = set()
current = start
while True:
if current in visited:
return "LOOP"
visited.add(current)
next_value = links.get(current)
if next_value is None:
return "INVALID"
if next_value.startswith("END:"):
return next_value[4:]
current = next_value
Explanation
Maintain a visited set of URLs to detect cycles. Starting from start, look up the response: if it's terminal ('END:<result>'), return the result substring. Otherwise, treat it as the next URL and continue. If you encounter a URL not in the mapping, the navigation cannot proceed, so return 'INVALID'. This simulates following an API's next-link responses until completion, with robust handling of loops and dead ends.
Time complexity: O(n) where n is the number of distinct URLs visited along the path. Space complexity: O(n) for the visited set.
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'.