Drive a Car to an Unseen Destination Using Only Local Directions Without Circling
Company: Waymo
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
A car has to find its destination on a map it cannot see in advance. It only learns about the map as it drives: every time it arrives somewhere, it finds out which directions it can continue in from there. Write the search that drives the car until it reaches the destination, and make sure the car never goes around in circles.
The interviewer made this problem up and explained it verbally rather than from a written prompt, so pinning down the setup is part of the task. For concreteness, assume the car is controlled through this interface (the names are illustrative; agree on the real ones with the interviewer):
```python
class Car:
def open_directions(self) -> list[str]:
"""Directions ("N", "E", "S", "W") the car can drive from its current cell."""
def move(self, direction: str) -> None:
"""Drive one cell in an open direction."""
def at_destination(self) -> bool:
"""True when the current cell is the destination."""
```
Implement `find_destination(car) -> list[str] | None` that drives the car to the destination and returns the sequence of directions of a route from the start cell to the destination, or returns `None` after exploring every reachable cell without finding it.
```hint What identifies a place
The car cannot see the map, so decide how it can tell that it has been somewhere before.
```
```hint Coming back is a move too
When a direction leads nowhere useful, the car is physically somewhere else; plan how it returns to try the next option.
```
### Clarifying Questions
- Is the map a grid of cells with four compass directions, or a general road network with junctions?
- Does the car know its coordinates, or only the moves it has made? Can it recognize a place it has visited before?
- If the car can drive from cell A to cell B, can it always drive back from B to A (no one-way streets)?
- Is any route to the destination acceptable, or does the interviewer want the shortest one?
- Is the number of moves the car makes (including backtracking) a cost to minimize, or only correctness?
### What a Strong Answer Covers
- A model of the setup: cells, moves, and what the car can sense
- Depth-first exploration with a visited set keyed by position derived from the car's own moves
- Physical backtracking, so the car's real position always matches the search state
- A route returned from the recursion or explicit stack, and a clear result when the destination is unreachable
- Complexity measured in moves and in memory, and a guarantee of termination
- Discussion of when depth-first is the right choice for a physical agent compared with breadth-first search
### Follow-up Questions
- After the destination is found once, how would you give the car the shortest route for the next trip?
- Some streets are one-way, so the car cannot always drive back. What breaks, and what can you still guarantee?
- The car has no way to track its position (no coordinates, only landmarks it may see again). How do you avoid circling?
- The map is very large and the car should reach a destination that is probably nearby. How would you change the exploration order?
Overview: A car must reach an unseen destination while only learning which directions are open at each step. Implement the search that finds it without driving in circles, testing depth-first exploration, visited tracking, physical backtracking, and cost in moves.