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