Explore an HTTP Maze
Problem Description
You are tasked with exploring a maze-like forest accessible via an HTTP API. The entrance to the forest is at GET /mirkwood.
Each location within the forest is uniquely identified by a string id. A GET request to a specific location URL will return a JSON object describing that location and its possible next moves. Your program must navigate this forest until it reaches the designated exit, then print the id of the final exit location.
API Contract
The API adheres to the following structure for a general location:
{
"id": "A",
"message": "optional text",
"neighbors": [
{ "direction": "north", "url": "/mirkwood?location=B" },
{ "direction": "east", "url": "/mirkwood?location=C" }
]
}
The exit location will be indicated by a response with a specific message and no further neighbors:
{
"id": "Z",
"message": "DONE",
"neighbors": []
}
Requirements
- Exploration Logic: Write a program that continuously sends
GETrequests to explore reachable locations. The program must terminate when it receives a response where themessagefield is exactly"DONE". - Search Strategy: Prioritize exploring shallower locations before deeper ones. Implement a Breadth-First Search (BFS) algorithm to find the exit.
- Cycle Prevention: Ensure the program avoids infinite loops if the maze contains cycles.
- Output: Print the
idof the final exit location. - Observability: Log sufficient information during exploration to aid in debugging unexpected API responses.
Follow-up: Advanced Maze Exploration
Extend your program to handle real-world API complexities:
- Transient Failures: Some
GETrequests may temporarily fail with HTTP server errors (e.g.,500,502,503). Implement a retry mechanism for these transient failures. - Locked Doors: A neighbor entry may include
"locked": trueand"required_key": "red". These doors cannot be traversed initially. - Key Collection: Locations may contain keys, indicated by a
"keys": ["red", "blue"]array. - Key-Based Access: A locked door can only be traversed after your program has collected the corresponding
required_key. - Re-exploration: The program should be able to revisit previously explored locations if newly collected keys make additional paths available.
AI interview prep
Core dilemma
Balancing efficient state management for graph traversal (visited nodes, collected keys, paths) with robust, rate-limited interaction against an unreliable external HTTP API, especially when dynamic access conditions (keys) necessitate re-evaluation of previously inaccessible paths.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Explore an HTTP Maze
Problem Description
You are tasked with exploring a maze-like forest accessible via an HTTP API. The entrance to the forest is at GET /mirkwood.
Each location within the forest is uniquely identified by a string id. A GET request to a specific location URL will return a JSON object describing that location and its possible next moves. Your program must navigate this forest until it reaches the designated exit, then print the id of the final exit location.
API Contract
The API adheres to the following structure for a general location:
{
"id": "A",
"message": "optional text",
"neighbors": [
{ "direction": "north", "url": "/mirkwood?location=B" },
{ "direction": "east", "url": "/mirkwood?location=C" }
]
}
The exit location will be indicated by a response with a specific message and no further neighbors:
{
"id": "Z",
"message": "DONE",
"neighbors": []
}
Requirements
- Exploration Logic: Write a program that continuously sends
GETrequests to explore reachable locations. The program must terminate when it receives a response where themessagefield is exactly"DONE". - Search Strategy: Prioritize exploring shallower locations before deeper ones. Implement a Breadth-First Search (BFS) algorithm to find the exit.
- Cycle Prevention: Ensure the program avoids infinite loops if the maze contains cycles.
- Output: Print the
idof the final exit location. - Observability: Log sufficient information during exploration to aid in debugging unexpected API responses.
Follow-up: Advanced Maze Exploration
Extend your program to handle real-world API complexities:
- Transient Failures: Some
GETrequests may temporarily fail with HTTP server errors (e.g.,500,502,503). Implement a retry mechanism for these transient failures. - Locked Doors: A neighbor entry may include
"locked": trueand"required_key": "red". These doors cannot be traversed initially. - Key Collection: Locations may contain keys, indicated by a
"keys": ["red", "blue"]array. - Key-Based Access: A locked door can only be traversed after your program has collected the corresponding
required_key. - Re-exploration: The program should be able to revisit previously explored locations if newly collected keys make additional paths available.