Find exit URL via BFS API calls

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.

Resilient BFS to Find Exit Path

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

Example 1

Input: api = {
  "/": {"next_step": ["/a", "/b"], "fail_500": 1},
  "/a": {"next_step": ["/ac"], "timeout": 2},
  "/ac": "Congrats",
  "/b": {"next_step": ["/bx"]},
  "/bx": {"next_step": []}
}
Output: ac

Explanation: Root "/" fails once with 500, then expands to "/a" and "/b". Path "/a" times out twice before succeeding and revealing "/ac" which is the exit, so return "ac".

Example 2

Input: api = {
  "/": {"next_step": ["/a"], "fail_500": 2},
  "/a": {"next_step": ["/b"], "timeout": 1},
  "/b": {"next_step": ["/a"]}
}
Output: 

Explanation: After transient failures, BFS explores a cycle between "/a" and "/b" with no exit; visited-after-success prevents infinite loops, so return empty string.

Hints

1. Use a queue for BFS and a visited set, but only mark a node visited after a successful fetch.
2. On HTTP 500 or timeout, re-enqueue the same path to retry later instead of marking it visited.
3. Normalize next_step entries to absolute paths by prepending "/" when missing.

Approach

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)