Katkat
Back

Select the Nearest Eligible Elevator

PinterestSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Implement an elevator dispatch selection algorithm that finds the nearest eligible elevator for a passenger request based on floor, direction, and tie-breaking rules.

Problem Statement

You are designing the dispatch controller for a multi-elevator bank in an office building. Given the current states of all elevators and a new passenger hall call, determine which elevator should be assigned to service the request.

Each elevator has an integer id, a floor indicating its current position, and a direction ("UP", "DOWN", or "IDLE").

A passenger call specifies a request_floor and a request_dir ("UP" or "DOWN").

An elevator is considered eligible to take the call if and only if:

  1. It is currently "IDLE" (regardless of floor).
  2. Its direction matches request_dir, and it has not yet passed the passenger floor:
    • If request_dir == "UP", the elevator must have elevator.floor = request_floor.

Among all eligible elevators, select the one with the minimum distance abs(elevator.floor - request_floor). If multiple eligible elevators have the same minimum distance, pick the one with the smallest id. If no elevators are eligible or the input list is empty, return -1.

Function Signature

class Elevator:
    def __init__(self, id: int, floor: int, direction: str):
        self.id = id
        self.floor = floor
        self.direction = direction  # "UP", "DOWN", or "IDLE"

def select_elevator(elevators: list[Elevator], request_floor: int, request_dir: str) -> int:
    pass

Input & Constraints

  • elevators: A list of Elevator objects (0 <= len(elevators) <= 1000).
  • id: Unique integer for each elevator (0 <= id <= 10^5).
  • floor: Integer (1 <= floor <= 200).
  • request_floor: Integer (1 <= request_floor <= 200).
  • direction: One of "UP", "DOWN", "IDLE".
  • request_dir: One of "UP", "DOWN".

Examples

Example 1

Input:
elevators = [
  Elevator(id=1, floor=3, direction="UP"),
  Elevator(id=2, floor=8, direction="DOWN"),
  Elevator(id=3, floor=5, direction="IDLE")
]
request_floor = 6
request_dir = "UP"

Output: 3
Explanation:
- Elevator 1 is at floor 3, moving UP (3 <= 6), distance = 3. Eligible.
- Elevator 2 is moving DOWN, direction mismatch. Ineligible.
- Elevator 3 is IDLE at floor 5, distance = 1. Eligible.
Elevator 3 is closest (distance 1 vs 3).

Example 2

Input:
elevators = [
  Elevator(id=4, floor=2, direction="UP"),
  Elevator(id=2, floor=2, direction="UP")
]
request_floor = 2
request_dir = "UP"

Output: 2
Explanation:
Both elevators are at floor 2 and moving UP (distance 0). Elevator 2 is chosen because id 2 < id 4.

Hints

Hint 1

First filter the input list down to only elevators that meet the eligibility criteria for the given request direction.

Hint 2

Be careful with cars on the same floor: an IDLE car or a car already moving in request_dir at request_floor has distance 0, but a car moving in the opposite direction is ineligible.

Hint 3

Track the minimum distance and break ties using the elevator id, or sort eligible candidates using the tuple `(distance, id)`.

Follow-up questions

  • How would you extend this logic if elevators maintain a queue of destinations (e.g., using the LOOK or SCAN scheduling algorithm) rather than just an instantaneous direction?
  • What additional information (e.g., door open/close duration, boarding delays, passenger capacity) would you need to build a discrete-event time simulation of elevator operations?
  • If millions of requests arrive concurrently across thousands of buildings, how would you design the dispatching service for low latency and high availability?