Parking Space: Find the Optimal Parking Spot Minimizing Walk Distance to an Entrance

Question

## Problem

A parking lot is represented as a 2D grid where `'.'` is an empty space, `'X'` is occupied, and `'E'` is the entrance. Find the empty parking space closest to the entrance by Manhattan distance. If there are ties, return the topmost-leftmost space.

```python
def find_parking(
    lot: list[list[str]]
) -> tuple[int, int] | None:  # (row, col) or None if no spaces
    pass
```

**Example:**
```
lot = [
  ['X', 'X', '.', 'X'],
  ['X', '.', 'X', 'X'],
  ['E', 'X', '.', '.']
]
# Entrance at (2,0). Distances: (0,2)->4, (1,1)->2, (2,2)->2, (2,3)->3
# Tie between (1,1) and (2,2) at dist=2: topmost-leftmost = (1,1)
-> (1, 1)
```

## Follow-ups

1. Your BFS approach guarantees the closest space. Why would a greedy approach (sort all empty spaces by distance) give the same answer, and which is more efficient for a sparse lot?
2. How does the problem change if there are multiple entrances and you want the space minimizing the distance to the nearest entrance?
3. If the lot has obstacles blocking paths (not all routes navigable), how does the algorithm change from Manhattan distance to BFS/Dijkstra?
4. How would you extend this to reserve a space (mark as occupied) atomically in a concurrent parking system with multiple users?

Parking Space: Find the Optimal Parking Spot Minimizing Walk Distance to an Entrance

Question Details

Full Details

Topics

More from Uber