Find the Exit of an HTTP URL Maze Despite Flaky 503s and Bad JSON

You are given the URL of the entrance to a maze made of HTTP endpoints. A GET request to a maze URL returns a JSON object whose key `next_stops` maps to a list of paths, for example (illustrative paths): ```json {"next_stops": ["/rooms/17", "/rooms/42"]} ``` Append each path to the host of the start URL to get the URLs you can visit next, and keep exploring. The exit is the URL whose response is: ```json {"message": "congrats"} ``` Write a program that takes the start URL and finds the exit. The interviewer gives no clarifications during this exercise. You are expected to learn how the service behaves by calling it and inspecting what comes back, and questions about error cases, such as what a `503` response means or what to do with a body that is not valid JSON, will not be answered. ```hint Treat the maze as a graph Think of each URL as a node and each entry in `next_stops` as an edge, and consider what happens when paths lead back to places you have already been. ``` ```hint Test your assumptions about failures Before deciding that a failed request marks a dead end, call the same URL again and compare the results. ``` ### Constraints and Clarifications - The maze may contain cycles and several routes to the same URL. - Error behavior is undocumented: responses may include HTTP errors such as `503` and bodies that cannot be parsed as JSON, and you must decide for yourself, from experiment, how to treat each one. - You may call the service as often as you need, but your program must always terminate. ### Clarifying Questions - Should the program return only the exit URL, or also the route from the start URL to it? - Are the paths in `next_stops` always relative to the host, or can some be full URLs? - Is a failed request (such as a `503`) permanent for that URL, or can the same URL succeed on a later attempt? Expect no answer, and decide how you will find out. - Is there a limit on the total number of requests or on the request rate? - What should the program do if it never reaches the exit? ### What a Strong Answer Covers - A graph traversal that deduplicates visited URLs and is safe with cycles - Correct construction of each next URL from the host and the path - Deliberate handling of each kind of failure (transient, permanent, malformed), with a bounded number of retries per endpoint - Discovering the service's behavior by probing and logging instead of guessing - A termination guarantee, and cost measured in requests ### Follow-up Questions - Return the shortest route from the start URL to the exit. What changes? - Make the crawler concurrent so it finishes faster. How do you keep the visited set and the retry budgets correct? - The service starts rate limiting you. How does your retry policy change? - How would you test the crawler without depending on the live service?