Select the Nearest Eligible Elevator
Company: Pinterest
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Select the Nearest Eligible Elevator
You are given a list of elevators. Each elevator has a current integer floor and a state: `"up"`, `"down"`, or `"idle"`. A passenger is waiting at an integer floor and wants to travel either `"up"` or `"down"`.
Implement:
```text
select_elevator(elevators, passenger_floor, passenger_direction) -> int
```
Return the index of the nearest elevator that can pick up the passenger, or `-1` if none is eligible.
Eligibility rules:
- An idle elevator can serve a passenger from any floor.
- An elevator moving up can serve only an up-bound passenger at or above the elevator's current floor.
- An elevator moving down can serve only a down-bound passenger at or below the elevator's current floor.
- A moving elevator at the passenger's floor is eligible only when its state matches the passenger's direction. Being on the same floor does not override a direction mismatch.
Choose the eligible elevator with minimum absolute floor distance. Break distance ties by the smaller input index.
### Examples
```text
elevators = [
{"floor": 2, "state": "up"},
{"floor": 8, "state": "down"},
{"floor": 5, "state": "idle"}
]
passenger_floor = 6
passenger_direction = "up"
result = 2
```
Elevator 0 is eligible at distance 4, elevator 1 moves in the wrong direction, and idle elevator 2 is eligible at distance 1.
```text
elevators = [{"floor": 4, "state": "down"}]
passenger_floor = 4
passenger_direction = "up"
result = -1
```
### Constraints
- `0 <= len(elevators) <= 100000`
- Floors are integers.
- State and passenger direction strings are valid lowercase values from the sets above.
- The function does not mutate elevator state.
### Hints
- Express eligibility as a predicate before comparing distance.
- Keep the best `(distance, index)` pair seen so far.
### Discussion Extensions
- The reported follow-up introduces time-ordered passengers but does not provide passenger destinations. Explain why direction, pickup floor, and arrival time alone are insufficient to simulate future elevator positions exactly.
- What additional trip and movement rules would make that simulation deterministic?
- How would the selector change if load, capacity, or scheduled stops affected cost?
Quick Answer: Select the nearest elevator eligible for a passenger based on current floor, movement state, and requested direction. Specify same-floor behavior, idle cars, deterministic tie breaking, empty input, and what extra trip information a time-ordered simulation would require.
You are given a bank of elevators. Elevator `i` is described by two parallel arrays of equal length:
- `elevator_floors[i]` -- the integer floor the elevator is currently on.
- `elevator_states[i]` -- the elevator's state, one of `"up"`, `"down"`, or `"idle"`.
A passenger is waiting on floor `passenger_floor` and wants to travel in `passenger_direction`, which is either `"up"` or `"down"`.
Return the index of the nearest elevator that can pick the passenger up, or `-1` if no elevator is eligible.
### Eligibility
- An `"idle"` elevator can serve a passenger from any floor.
- An elevator whose state is `"up"` can serve only an up-bound passenger who is at or above the elevator's current floor.
- An elevator whose state is `"down"` can serve only a down-bound passenger who is at or below the elevator's current floor.
- A moving elevator standing on the passenger's own floor is eligible only when its state matches the passenger's direction. Sharing a floor never overrides a direction mismatch.
### Selection
Among all eligible elevators, return the index of the one with the smallest absolute floor distance `abs(elevator_floors[i] - passenger_floor)`. If several eligible elevators tie on that distance, return the smallest such index. Return `-1` when no elevator is eligible, including when the bank is empty.
Neither input array may be modified.
### Example 1
```text
elevator_floors = [2, 8, 5]
elevator_states = ["up", "down", "idle"]
passenger_floor = 6
passenger_direction = "up"
Output: 2
```
Elevator 0 is moving up and the passenger is above it (`6 >= 2`), so it is eligible at distance 4. Elevator 1 is moving down while the passenger wants to go up, so it is ineligible. Idle elevator 2 is eligible at distance 1, the smallest distance, so the answer is index 2.
### Example 2
```text
elevator_floors = [4]
elevator_states = ["down"]
passenger_floor = 4
passenger_direction = "up"
Output: -1
```
The only elevator is standing on the passenger's own floor, but it is moving down while the passenger wants to go up. Sharing a floor does not override the direction mismatch, so nothing is eligible and the answer is `-1`.
### Input shape
The interview prompt models each elevator as a record such as `{"floor": 2, "state": "up"}`. This console passes exactly the same data as two parallel arrays -- `elevator_floors[i]` and `elevator_states[i]` describe the same elevator -- and it uses that shape identically in Python, JavaScript, Java, and C++.
Constraints
- 0 <= n <= 100000, where n is the number of elevators (len(elevator_floors))
- len(elevator_states) == len(elevator_floors) == n
- -10^9 <= elevator_floors[i] <= 10^9
- -10^9 <= passenger_floor <= 10^9
- elevator_states[i] is exactly one of "up", "down", "idle"
- passenger_direction is exactly one of "up", "down"
- abs(elevator_floors[i] - passenger_floor) can reach 2 * 10^9, so hold the distance in a 64-bit integer (long in Java, long long in C++); the floors themselves fit in 32 bits
- The function must not modify elevator_floors or elevator_states
Examples
Input: ([], [], 5, "up")
Expected Output: -1
Input: ([2,8,5], ["up","down","idle"], 6, "up")
Expected Output: 2
Hints
- Decide eligibility with a small predicate that looks only at the elevator's state, the elevator's floor, the passenger's floor, and the passenger's direction. Distance should play no part in it.
- You do not need a separate branch for an elevator standing on the passenger's own floor: if the direction rule is applied before anything positional, both worked examples fall out of the same three cases.
- One left-to-right pass carrying the best (distance, index) pair seen so far is enough. Keep the distance comparison strict so an earlier index survives a tie, and start the answer at -1 so an empty or fully ineligible bank needs no special case.