Quick Overview

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.

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.

Overview: 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

  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.

Loading coding console...

Show the approach

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)