Crawl an HTTP-served maze to its exit with 503 retries, dead ends and cycles

You are given the base URL of a "maze" served over HTTP. Write a program that explores the maze until it finds the exit, and returns the exit's message. - A `GET` on the base URL returns JSON listing the IDs of the next steps: ```json {"next_steps": ["ABC123", "XYZ789"]} ``` - For each step ID, `GET {base_url}/{step_id}` returns a response of the same shape, listing further next steps. - A dead end returns an empty list: `{"next_steps": []}`. - The exit is a step whose response contains a `message` field instead of more next steps. - The server is flaky: some requests fail with `503 Service Temporarily Unavailable`, and you need to retry them. - The maze can contain cycles, so the same step ID can be reachable along several paths. This is 60 minutes of live coding against the real server. The traversal itself is a standard graph search; most of the effort goes into the HTTP client, the retry logic and parsing the JSON correctly. ```hint Hide the flakiness Write one function that turns a step ID into parsed JSON and absorbs every retry, so the search code never sees a 503. ``` ```hint When is a step "seen" Decide whether a step ID is recorded as visited when you first discover it or when you fetch it, and what each choice costs in repeated requests. ``` ### Constraints and Clarifications - Any language with an HTTP client is fine. - Step IDs are opaque strings; treat the maze as a directed graph whose nodes are step IDs and whose edges are the `next_steps` entries. - A `GET` does not change server state, so repeating one is safe. ### Clarifying Questions - How many times should a 503 be retried, and should there be a delay between attempts? Does the server send a `Retry-After` header? - Can other failures occur, such as timeouts, other status codes, an unknown step ID, or a body that is not valid JSON, and how should each be handled? - Is there exactly one exit? Should the program return only the message, or also the path of step IDs that leads to it? - Roughly how many steps can the maze have, and how long can a path from the start get? - Can the response for the base URL itself be the exit? ### What a Strong Answer Covers - A fetch helper with bounded retries on 503, a delay that grows between attempts, a request timeout, and a clear error when retries run out - A traversal with a visited set that terminates on cycles and dead ends and stops as soon as the exit appears - Correct classification of every response as exit, dead end or more steps, including malformed or unexpected bodies - A deliberate choice between breadth-first and depth-first search, and between recursion and an explicit stack or queue, with the consequences of each - Each step fetched at most once, and an estimate of the number of requests and the running time - Code structured so the search can be tested against a fake server that injects 503s and cycles ### Follow-up Questions - Return the shortest sequence of step IDs from the start to the exit. What changes in your code? - The maze has a million steps and the server tolerates ten concurrent requests. How would you speed up the search without overloading a flaky server? - One step keeps returning 503 after every retry. Should the search fail, skip that step, or come back to it later? - A recursive version crashes on a maze where the path to the exit is very long. Why, and how do you fix it?