Find exit URL via BFS API calls

Q: Find exit URL via BFS API calls

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.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Ramp.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Ramp during technical interviews.

Question

##### 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.

PracHub · Accepted Answer

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 ""

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.

Quick Overview

Solution

Explanation

Hints

Quick Overview