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