Quick Overview

This question evaluates a candidate's competency in implementing robust HTTP-based crawling and traversal logic, including response parsing, retry and error handling, and termination detection.

Find final URL by crawling until “congrats”

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a starting HTTP URL. Implement a function that repeatedly calls URLs returned by previous responses until you reach a response that indicates success. Behavior: - Make an HTTP GET request to a URL. - The response body can be one of: 1) A success marker (e.g., the body equals the string `"congrats"`). 2) A payload that contains a list of new URLs to call next (possibly alongside other fields/data). 3) Other data that does not contain any new URLs (a dead end). - Continue iterating/recursing through returned URLs until you find a URL whose response is `"congrats"`. Requirements: - Return only the final URL that produced the `"congrats"` response (you do NOT need to return the path of URLs taken). - Print/log each HTTP response you receive before deciding how to parse it and what to do next. - Handle error cases, especially HTTP 503 (Service Unavailable): implement reasonable retry behavior and error handling for malformed/unexpected response bodies. - The solution should be practical and focused on getting the core logic working first; coding style is not the priority. Clarify any assumptions you need (e.g., max retries, backoff strategy, cycle detection, concurrency).

Overview: This question evaluates a candidate's competency in implementing robust HTTP-based crawling and traversal logic, including response parsing, retry and error handling, and termination detection.

Read the full Ramp Software Engineer interview experience this question came from

You are given a starting URL and a simulated HTTP environment. Implement a function that keeps making GET requests until it finds a response body equal to the string "congrats". Simulation rules: - `web` maps each URL to either a single response body or a list of response bodies. - If `web[url]` is a list, each fetch of that URL returns the next item in the list. If the URL is fetched more times than the list length, keep returning the last item. - A response body can be: 1. The string "congrats" -> success. 2. A dictionary containing key `"urls"` with a list of next URLs to visit -> continue crawling. 3. Any other value -> dead end. 4. A dictionary `{"status": 503}` -> temporary failure; retry the same URL. Requirements and assumptions: - Return only the final URL whose response body is "congrats". - Print/log every response before deciding how to handle it. Printed output is not part of the return value. - Retry HTTP 503 immediately, up to `max_retries` extra times for that URL. - Use FIFO order (BFS) when exploring returned URLs, preserving the order in each `"urls"` list. - Use cycle detection so the same URL is not processed repeatedly through loops. - If a response is malformed or does not contain usable next URLs, treat it as a dead end. - If no URL leads to "congrats", return `None`.

Constraints

  • 0 <= len(web) <= 10^4
  • 0 <= max_retries <= 10
  • The total number of URLs across all `urls` lists is at most 2 * 10^4
  • Each URL in a `urls` list should be processed at most once, except for internal retries caused by HTTP 503

Examples

Input: ("http://start", {"http://start": {"urls": ["http://a", "http://b"], "meta": 1}, "http://a": {"message": "dead end"}, "http://b": "congrats"}, 2)

Expected Output: "http://b"

Explanation: Start returns two next URLs. `http://a` is a dead end, and `http://b` returns `congrats`, so the answer is that final URL.

Input: ("s", {"s": {"urls": ["r"]}, "r": [{"status": 503}, {"status": 503}, "congrats"]}, 2)

Expected Output: "r"

Explanation: URL `r` returns HTTP 503 twice, then succeeds on the third attempt. With `max_retries = 2`, this is allowed.

Hints

  1. Model the crawl as a graph traversal: each URL is a node, and each `urls` list gives outgoing edges.
  2. Keep retry logic separate from your visited set: a 503 means retry the same URL, while cycle detection prevents revisiting URLs discovered through links.

Loading coding console...

Show the approach

Approach

This is a BFS crawl of a simulated web graph, fetching URLs until a body equal to "congrats" is found.

fetch(url) simulation. A call_count dict tracks how many times each URL was requested. If url isn't in web, it returns {"status": 404} (a dead end). If web[url] is a list, it returns value[idx] for the current fetch index, clamping to value[-1] once the index exceeds the list (empty list → None); the per-URL counter is then incremented. A non-list value is returned directly. This is what lets a URL return 503 a few times and then "congrats".

Traversal. A deque holds URLs to visit and a seen set provides cycle detection — a URL is added to seen the moment it's enqueued, so it can never be queued twice. For each dequeued url, an inner while True loop calls fetch and prints the response, then decides:

  • {"status": 503} → if retries < max_retries, increment retries and re-fetch the same URL (immediate retry); otherwise give up on this URL and break.
  • "congrats" → success; return that url.
  • a dict with a list under "urls" → enqueue each unseen string next URL in order (preserving FIFO/BFS), then break.
  • anything else (other dicts, lists, scalars, None, 404) → dead end; break.

If the queue empties without finding "congrats", it returns None.

Why correct: retries are counted per-URL and reset on each dequeue; seen prevents reprocessing loops; FIFO order and in-list ordering are preserved; malformed/unusable responses fall through to a break, matching the dead-end rule.

Time complexity:
O(V + E + R)
Space complexity:
O(V)