Design an elevator control system
Company: Google
Role: Software Engineer
Category: System Design
Difficulty: medium
Interview Round: Technical Screen
Design the software for a multi-elevator control system in a high-rise building. Specify classes, scheduling algorithms for car assignments, handling peak traffic, fairness, fault tolerance, and safety constraints. Consider real-time constraints and a simulation and testing strategy.
Overview: This question evaluates skills in software architecture, algorithm design, real-time systems, concurrency, fault tolerance, scheduling, and safety constraints specific to multi-elevator control systems.
Community answers
Answer by Josef420
from collections import defaultdict, deque
class ElevatorController:
def go_up(self):
pass
def go_down(self):
pass
class ElevatorSystem:
def init(self, stops: list[int], start_pos: int, elevator_controller: ElevatorController) -> None:
self.cur_pos: int = start_pos # current elevator position
self.remaining_targets: deque[tuple[int, int]] = deque() # remaining target stops of the elevator
self.resolved_request_ids_of_target: defaultdict[int, set[int]] = defaultdict(set) # resolved requests ids
self.remaining_targets_dict: dict[int, int] = {} # stores remaining targets in dict for O(1) performance
self.stops: set[int] = set(stops) # all available stops for input validation
self.req_id: int = 0 # current request id
self.elevator_controller: ElevatorController = elevator_controller # external elevator controller API
def add_target(self, target: int) -> None:
if target not in self.stops:
raise ValueError
if target in self.remaining_targets_dict:
return
self.req_id += 1
self.remaining_targets.append((target, self.req_id))
self.remaining_targets_dict[target] = self.req_id
def process_target_stops(self) -> None:
next_target: int | None = None
request_id: int | None = None
while self.remaining_targets and next_target is None:
entry_target, entry_request_id= self.remaining_targets.popleft()
if entry_request_id in self.resolved_request_ids_of_target[entry_target]:
self.resolved_request_ids_of_target[entry_target].remove(entry_request_id)
continue
next_target, request_id = entry_target,