Find exit URL via BFS API calls
Company: Ramp
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
Design and implement a function that, given a starting URL "/", performs BFS or DFS by repeatedly sending HTTP GET requests of the form GET "example.com/<path>". Each response is a JSON object either of the shape { next_step: ["...", "..."] } or the string "Congrats" when the exit page is reached. Return the exit path (e.g., "jkdf"). Your solution must
(
1) avoid infinite loops when cycles occur,
(
2) gracefully retry when a request returns HTTP 500, and
(
3) impose a timeout for slow pages while still guaranteeing eventual completion if a path exists.
Quick Answer: This question evaluates graph traversal and resilience when interacting with HTTP APIs, covering BFS/DFS reasoning, cycle detection to avoid infinite loops, retry handling for transient HTTP 500 responses, and timeout management for slow pages.
You are given a dictionary api that models a website as a directed graph. Each key is an absolute path string (e.g., "/", "/a", "/a/b"). The value for a key is either the string "Congrats" (indicating an exit page) or an object with fields: next_step (array of absolute paths), and optionally fail_500 (non-negative integer) and timeout (non-negative integer). Starting from path "/", perform a breadth-first search to find any exit page. For each path, the first fail_500 attempts must be treated as HTTP 500 errors; after those are exhausted, the next timeout attempts must be treated as timeouts; afterward, the request succeeds and returns its next_step or "Congrats". On HTTP 500 or timeout, do not mark the path as visited; retry it later while continuing BFS on other paths. Mark a path visited only after a successful response is processed to avoid infinite loops in cyclic graphs. Return the exit path without the leading "/" when found; if no exit is reachable, return the empty string.
Constraints
- 1 <= number of paths (nodes) <= 10^4
- Each value in api is either the string "Congrats" or an object with key "next_step" (list of strings) and optional keys "fail_500" and "timeout" (non-negative integers).
- All paths and next_step entries are absolute and should start with "/"; if not, treat them as if "/" were prepended.
- The starting path "/" is present in api.
- Transient error counters are per-path and finite: a path returns HTTP 500 for its first fail_500 attempts, then times out for its next timeout attempts, then succeeds.
- Return the first exit discovered in BFS order; if none is reachable, return "".
Examples
Input:
Expected Output: ac
Solution
from collections import deque, defaultdict
def find_exit(api: dict) -> str:
# Track remaining transient failures per path, initialized lazily from api
left_500 = defaultdict(int)
left_timeout = defaultdict(int)
def attempt_get(path: str):
node = api.get(path)
if node is None:
# Unknown path: treat as a page with no outgoing links
return ("ok", {"next_step": []})
if node == "Congrats":
return ("ok", "Congrats")
if isinstance(node, dict):
# Initialize counters lazily so they persist across retries
if path not in left_500:
left_500[path] = int(node.get("fail_500", 0) or 0)
if path not in left_timeout:
left_timeout[path] = int(node.get("timeout", 0) or 0)
if left_500[path] > 0:
left_500[path] -= 1
return ("500", None)
if left_timeout[path] > 0:
left_timeout[path] -= 1
return ("timeout", None)
return ("ok", node)
# Malformed entry: treat as page with no outgoing links
return ("ok", {"next_step": []})
q = deque(["/"])
visited = set()
while q:
path = q.popleft()
if path in visited:
continue
status, data = attempt_get(path)
if status != "ok":
# Transient failure: retry later
q.append(path)
continue
if data == "Congrats":
return path.lstrip("/")
# Expand neighbors
steps = data.get("next_step", []) if isinstance(data, dict) else []
if isinstance(steps, list):
for s in steps:
if not isinstance(s, str):
continue
np = s if s.startswith("/") else "/" + s
if np not in visited:
q.append(np)
visited.add(path)
return ""
Explanation
Use BFS starting at "/". Maintain a visited set, but only mark a node visited after a successful fetch to prevent cycles while still allowing retries. For each path, lazily track remaining HTTP 500 and timeout attempts; on such events, re-enqueue the path and proceed with other work. Once a fetch succeeds, either return immediately if it is an exit ("Congrats") or enqueue its neighbors. This guarantees eventual completion when a path exists because each path has finite transient failures.
Time complexity: O(V + E + R), where V is the number of reachable paths, E is the total number of next_step edges explored, and R is the total count of transient errors/timeouts across reachable paths.. Space complexity: O(V).
Hints
- Use a queue for BFS and a visited set, but only mark a node visited after a successful fetch.
- On HTTP 500 or timeout, re-enqueue the same path to retry later instead of marking it visited.
- Normalize next_step entries to absolute paths by prepending "/" when missing.