← Back to companies
[ OK ] Loaded —
[ INFO ]
$ cd
$ ls -lt
01
02
03
04
05
$ ls -lt
01
02
03
04
05
user@intervues:~/$
Design and implement an elevator control system for a multi-story building. Your system should efficiently manage one or more elevators, handle passenger requests, and optimize elevator movement to minimize wait times and energy consumption.
The system must coordinate multiple elevators, decide which elevator should respond to each request, manage the direction of travel (up/down), and queue requests appropriately. Consider real-world scenarios like multiple passengers requesting elevators from different floors simultaneously, elevators changing direction, and optimizing for passenger convenience.
Elevator Class: Represents an individual elevator with properties like current floor, direction (UP/DOWN/IDLE), and capacity
Request Management: Handle pickup requests (floor + direction) and destination requests (target floor)
Optimal Assignment: When multiple elevators exist, assign requests to the most suitable elevator based on:
Movement Strategy: Implement an efficient algorithm (like SCAN/LOOK) where elevators:
State Tracking: Maintain elevator state including current floor, moving/idle status, and request queue
Scalability: Design should work with 1 to N elevators and support buildings with varying floor counts
Example 1: Single Elevator Basic Operation
` Building: 10 floors, 1 elevator starting at floor 1 Request: Passenger at floor 3 wants to go to floor 8
Process:
Example 2: Multiple Requests Same Direction
` Building: 15 floors, 1 elevator at floor 1 Requests:
Process (SCAN algorithm):
Example 3: Multi-Elevator Selection
` Building: 20 floors, 2 elevators
Selection logic:
Hint 1: Core Data Structures For each elevator, maintain:
- Current floor position (integer)
- Direction state (enum: UP, DOWN, IDLE)
- Two priority queues or sorted lists: one for floors above current position, one for floors below
- When moving up, service all floors in the "up" queue in ascending order
- When moving down, service all floors in the "down" queue in descending order
For the controller, keep a list of all elevator objects and implement a scoring function to select the best elevator for each new request.
Hint 2: Request Assignment Strategy When a new request arrives, evaluate each elevator with a scoring system:
- Priority 1: Elevator already moving in the same direction and hasn't passed the pickup floor
- Priority 2: Elevator is idle (score based on distance)
- Priority 3: Elevator moving in opposite direction (will eventually return)
Calculate score = base_score - distance_to_pickup_floor. Choose elevator with highest score.
Consider using the SCAN (elevator) algorithm: move in one direction until no more requests, then reverse. This is more efficient than serving requests in random order.
Hint 3: Implementation Pattern Use an object-oriented approach:
Elevator class handles:
- State management (floor, direction)
- Adding requests to internal queues
- Moving to next floor in sequence
- Determining when to change direction
ElevatorController class handles:
- Managing multiple elevator instances
- Receiving external requests
- Dispatching requests to optimal elevator
- Coordinating overall system state
Keep the concerns separated: elevators don't choose which requests to handle; the controller makes assignment decisions.
Full Solution `` Solution Explanation:
The solution implements a complete elevator control system using object-oriented design principles:
Key Design Decisions:
SCAN Algorithm: Elevators continue in one direction until no more requests, then reverse. This is efficient and mirrors real elevator behavior.
Separate Queues: Each elevator maintains two sorted queues (up and down), allowing O(1) access to the next floor to visit.
Scoring System: The controller assigns requests based on a priority scoring system that considers:
- Elevator direction and position
- Distance to pickup floor
- Whether the elevator is already heading toward the request
State Management: Clear separation between elevator state (managed by Elevator class) and system-level decisions (managed by ElevatorController).
Time Complexity:
- Adding request: O(log R) where R is requests per elevator (due to sorting)
- Selecting elevator: O(E) where E is number of elevators
- Processing all requests: O(R × F) where F is floors traveled
Space Complexity:
- O(E × R) to store all pending requests across all elevators
This design is extensible and can easily accommodate additional features like capacity limits, priority passengers, or express elevators.
from enum import Enum
from typing import List, Tuple
import heapq
class Direction(Enum):
"""Enumeration for elevator direction states"""
UP = 1
DOWN = -1
IDLE = 0
class Elevator:
"""Represents a single elevator in the system"""
def __init__(self, id: int, max_floors: int):
self.id = id
self.current_floor = 1 # Start at ground floor
self.max_floors = max_floors
self.direction = Direction.IDLE
# Separate queues for up and down requests
# Using lists that we'll keep sorted for efficiency
self.up_queue = [] # Floors to visit going up
self.down_queue = [] # Floors to visit going down
def add_request(self, pickup_floor: int, destination_floor: int):
"""Add a new request to this elevator's queue"""
# Add pickup floor to appropriate queue
if pickup_floor > self.current_floor:
if pickup_floor not in self.up_queue:
self.up_queue.append(pickup_floor)
self.up_queue.sort()
elif pickup_floor < self.current_floor:
if pickup_floor not in self.down_queue:
self.down_queue.append(pickup_floor)
self.down_queue.sort(reverse=True)
# Add destination floor to appropriate queue
if destination_floor > self.current_floor:
if destination_floor not in self.up_queue:
self.up_queue.append(destination_floor)
self.up_queue.sort()
elif destination_floor < self.current_floor:
if destination_floor not in self.down_queue:
self.down_queue.append(destination_floor)
self.down_queue.sort(reverse=True)
def get_next_floor(self) -> int:
"""Determine the next floor to visit based on SCAN algorithm"""
if self.direction == Direction.UP and self.up_queue:
return self.up_queue[0]
elif self.direction == Direction.DOWN and self.down_queue:
return self.down_queue[0]
elif self.up_queue:
self.direction = Direction.UP
return self.up_queue[0]
elif self.down_queue:
self.direction = Direction.DOWN
return self.down_queue[0]
else:
self.direction = Direction.IDLE
return self.current_floor
def move_to_next_floor(self) -> int:
"""Move elevator to next floor in queue and return that floor"""
next_floor = self.get_next_floor()
# Move to the floor
self.current_floor = next_floor
# Remove from queue
if next_floor in self.up_queue:
self.up_queue.remove(next_floor)
if next_floor in self.down_queue:
self.down_queue.remove(next_floor)
# Update direction based on remaining queue
if self.direction == Direction.UP and not self.up_queue:
if self.down_queue:
self.direction = Direction.DOWN
else:
self.direction = Direction.IDLE
elif self.direction == Direction.DOWN and not self.down_queue:
if self.up_queue:
self.direction = Direction.UP
else:
self.direction = Direction.IDLE
return self.current_floor
def has_requests(self) -> bool:
"""Check if elevator has pending requests"""
return len(self.up_queue) > 0 or len(self.down_queue) > 0
def get_distance_to(self, floor: int) -> int:
"""Calculate distance to a given floor"""
return abs(self.current_floor - floor)
class ElevatorController:
"""Manages multiple elevators and dispatches requests optimally"""
def __init__(self, num_elevators: int, max_floors: int):
self.elevators = [Elevator(i, max_floors) for i in range(num_elevators)]
self.max_floors = max_floors
def select_optimal_elevator(self, pickup_floor: int, destination_floor: int) -> int:
"""
Select the best elevator for a request using a scoring system.
Returns the index of the selected elevator.
"""
best_elevator = 0
best_score = float('-inf')
request_direction = Direction.UP if destination_floor > pickup_floor else Direction.DOWN
for i, elevator in enumerate(self.elevators):
score = 0
distance = elevator.get_distance_to(pickup_floor)
# Case 1: Elevator is idle - score based on distance
if elevator.direction == Direction.IDLE:
score = 1000 - distance
# Case 2: Elevator moving in same direction and hasn't passed pickup floor
elif elevator.direction == request_direction:
if request_direction == Direction.UP and elevator.current_floor <= pickup_floor:
score = 2000 - distance # Highest priority
elif request_direction == Direction.DOWN and elevator.current_floor >= pickup_floor:
score = 2000 - distance # Highest priority
else:
score = 500 - distance # Will need to come back
# Case 3: Elevator moving in opposite direction
else:
score = 200 - distance # Lowest priority
if score > best_score:
best_score = score
best_elevator = i
return best_elevator
def request_elevator(self, pickup_floor: int, destination_floor: int):
"""Handle a new elevator request"""
elevator_id = self.select_optimal_elevator(pickup_floor, destination_floor)
self.elevators[elevator_id].add_request(pickup_floor, destination_floor)
def process_all_requests(self) -> List[int]:
"""Process all pending requests and return final positions"""
while any(e.has_requests() for e in self.elevators):
for elevator in self.elevators:
if elevator.has_requests():
elevator.move_to_next_floor()
return [e.current_floor for e in self.elevators]
def get_elevator_position(self, elevator_id: int) -> int:
"""Get current position of specific elevator"""
return self.elevators[elevator_id].current_floor
# Helper functions for test cases
def processElevatorRequest(num_elevators: int, max_floors: int, requests: List[List[int]]) -> str:
"""Process requests and return final position of first elevator"""
controller = ElevatorController(num_elevators, max_floors)
for pickup, dest in requests:
controller.request_elevator(pickup, dest)
final_positions = controller.process_all_requests()
return str(final_positions[0])
def getElevatorStops(num_elevators: int, max_floors: int, requests: List[List[int]]) -> str:
"""Get sequence of stops for the elevator"""
controller = ElevatorController(num_elevators, max_floors)
stops = []
for pickup, dest in requests:
controller.request_elevator(pickup, dest)
elevator = controller.elevators[0]
while elevator.has_requests():
floor = elevator.move_to_next_floor()
stops.append(floor)
return str(stops)
def selectOptimalElevator(num_elevators: int, max_floors: int,
positions: List[int], request: List[int]) -> str:
"""Return which elevator should handle a request"""
controller = ElevatorController(num_elevators, max_floors)
# Set initial positions
for i, pos in enumerate(positions):
controller.elevators[i].current_floor = pos
selected = controller.select_optimal_elevator(request[0], request[1])
return str(selected)
def calculateTotalDistance(num_elevators: int, max_floors: int,
positions: List[int], requests: List[List[int]]) -> str:
"""Calculate total floors traveled by all elevators"""
controller = ElevatorController(num_elevators, max_floors)
# Set initial positions
for i, pos in enumerate(positions):
controller.elevators[i].current_floor = pos
# Add all requests
for pickup, dest in requests:
controller.request_elevator(pickup, dest)
# Track distance
total_distance = 0
initial_positions = [e.current_floor for e in controller.elevators]
while any(e.has_requests() for e in controller.elevators):
for i, elevator in enumerate(controller.elevators):
if elevator.has_requests():
old_floor = elevator.current_floor
new_floor = elevator.move_to_next_floor()
total_distance += abs(new_floor - old_floor)
return str(total_distance)