Find an Exit in a URL Maze
Company: Ramp
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a starting URL for a web-based maze. Each URL represents one room in the maze. Your task is to write a program that discovers whether there is a path from the starting room to an exit room.
Assume you have a helper function or HTTP client that can request a room URL. A successful response has status code `200` and returns JSON in this shape:
```json
{
"is_exit": false,
"neighbors": ["https://maze.example/room/2", "https://maze.example/room/7"]
}
```
A room is an exit if `is_exit` is `true`. The maze may contain cycles, so your solution must not revisit the same URL indefinitely.
Implement:
```python
def find_exit(start_url: str) -> str | None:
pass
```
Return the URL of any exit room reachable from `start_url`, or `None` if no exit is reachable.
Follow-up: The maze service is unreliable and protected by per-room access keys.
Additional behavior:
1. A request may return `503 Service Unavailable`. In that case, retry the same URL a limited number of times before treating it as temporarily unreachable.
2. A request may return `401 Unauthorized`. Some successful room responses may include a key, for example:
```json
{
"is_exit": false,
"neighbors": ["https://maze.example/room/9"],
"key": "abc123"
}
```
When a key is returned, capture it and include it in future requests using a header such as:
```text
Authorization: Bearer abc123
```
Update your implementation so it can still find an exit while handling cycles, retries, `503` responses, `401` responses, and authorization keys.
Overview: This question evaluates graph traversal and state-management skills, emphasizing handling cycles, HTTP error conditions, retry logic, and propagation of authorization tokens in a networked client.
Read the full Ramp Software Engineer interview experience this question came from
Part 1: Find an Exit in a URL Maze with Cycle Detection
You are given a directed graph of URLs representing rooms in a maze. `start_url` is the room where you begin, `exits` is a list of exit-room URLs, and `edges` is a list of directed connections `[from_url, to_url]`.
The maze may contain cycles, so your algorithm must avoid revisiting rooms forever.
Write a function `solution(start_url, exits, edges)` that returns the first exit discovered by a breadth-first search (BFS), processing outgoing edges in the same order they appear in `edges`. If no exit is reachable, return `None`.
Rooms that never appear as a `from_url` still exist; they simply have no outgoing edges.
Constraints
- `0 <= len(edges) <= 2 * 10^5`
- `0 <= len(exits) <= 10^5`
- Each edge has exactly 2 strings: `[from_url, to_url]`
- The graph is directed and may contain cycles
- URLs are case-sensitive strings
Examples
Input: ('A', ['C', 'D'], [['A', 'B'], ['A', 'C'], ['B', 'D']])
Expected Output: 'C'
Explanation: BFS visits A, then B and C. C is the first exit reached.
Input: ('A', ['Z'], [['A', 'B'], ['B', 'C'], ['C', 'A']])
Expected Output: None
Explanation: The reachable part of the graph is a cycle with no exit.
Hints
- Use a queue to explore the maze level by level.
- Keep a `visited` set so a cycle like A -> B -> A does not loop forever.
Part 2: Find an Exit with Retries, 503/401 Handling, and Authorization Keys
You are given a URL maze, but now each room may be unreliable or protected by a key.
Implement `solution(start_url, exits, edges, required_keys, keys_found, failures_before_success, max_retries)`.
Behavior rules:
1. You start at `start_url` with no key.
2. `edges` gives directed room connections as `[from_url, to_url]`.
3. If `failures_before_success[url] = n`, then that room would return `503` on the first `n` attempts before any non-503 response. Since you may retry at most `max_retries` times, the room is accessible only if `n <= max_retries`.
4. If `required_keys[url] = k`, the room returns `401` unless your current key is exactly `k`.
5. If you successfully access a room and `keys_found[url] = k`, your current key becomes `k` for future requests. A new key replaces the old key.
6. A room counts as an exit only if you can successfully access it.
7. The maze may contain cycles, and the same URL may need to be revisited later with a different key.
Return the first reachable exit found by BFS over states `(url, current_key)`, processing outgoing edges in the order they appear in `edges`. Return `None` if no exit can be reached.
Constraints
- `0 <= len(edges) <= 2 * 10^5`
- `0 <= len(exits) <= 10^5`
- `0 <= max_retries <= 10^6`
- For any room not present in `required_keys`, no key is required
- For any room not present in `keys_found`, no new key is acquired there
- For any room not present in `failures_before_success`, it has 0 transient failures
- At most one key is active at a time; a newly found key replaces the previous one
- The maze may contain cycles, so visited states should include both URL and current key
Examples
Input: ('A', ['D'], [['A', 'B'], ['A', 'D'], ['B', 'A']], {'D': 'k1'}, {'B': 'k1'}, {}, 0)
Expected Output: 'D'
Explanation: You must first visit B to get key k1, then revisit A and access D.
Input: ('S', ['E'], [['S', 'M'], ['M', 'E']], {}, {}, {'M': 2, 'E': 1}, 2)
Expected Output: 'E'
Explanation: Both M and E are accessible because their 503 counts are within the retry budget.
Hints
- A URL visited without a key is not the same state as the same URL visited later with a key.
- If `failures_before_success[url] > max_retries`, that room can never be accessed successfully, so you can prune it immediately.