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