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).
Quick Answer: 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.
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
- Model the crawl as a graph traversal: each URL is a node, and each `urls` list gives outgoing edges.
- Keep retry logic separate from your visited set: a 503 means retry the same URL, while cycle detection prevents revisiting URLs discovered through links.