How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Remitly.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Remitly during technical interviews.

Design an Elevator System and Scheduler

Quick Overview

This question evaluates a candidate's object-oriented design and algorithmic scheduling competencies, focusing on concurrency control, fault tolerance, queue management, tie-breaking rules, and time/space complexity analysis within an elevator control system.

Company: Remitly

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design an object-oriented elevator system. Define core classes and interfaces (elevator, controller, request, floor, buttons, sensors) and their interactions, including concurrency and fault handling. Propose a scheduling algorithm that optimizes travel time and fairness. Given pending requests for floors [1, 99, 2], show how your scheduler ensures stopping at 2 before 99 while using only a single internal queue data structure; detail the queue operations required, tie-breaking rules, and time/space complexity. Explain how your design scales to multiple elevators and supports peak traffic modes.

Quick Answer: This question evaluates a candidate's object-oriented design and algorithmic scheduling competencies, focusing on concurrency control, fault tolerance, queue management, tie-breaking rules, and time/space complexity analysis within an elevator control system.

Part 1: Elevator Controller Event Log Processor

Implement the core interaction contract of a single-elevator controller. The controller receives timestamped events from buttons, floor sensors, door sensors, fault sensors, and repair operations. Events may arrive concurrently with the same timestamp, so they must be processed using a deterministic priority order. Maintain request state, reject invalid floors, stop when a floor sensor reports a requested floor, and enter/exit a fault state correctly.

Constraints

1 <= top_floor <= 1000
0 <= len(events) <= 10000
Event times are non-negative integer strings
Initial elevator floor is 1
Concurrent event priority is FAULT, REPAIR, FLOOR_SENSOR, DOOR_SENSOR, BUTTON
A FLOOR_SENSOR event may move at most one floor from the previous known floor; otherwise it triggers a SENSOR fault
While faulted, all non-FAULT and non-REPAIR events are ignored

Examples

Input: (10, [])

Expected Output: []

Explanation: No events produce no log entries.

Input: (10, [['0', 'BUTTON', '3'], ['1', 'FLOOR_SENSOR', '2'], ['2', 'FLOOR_SENSOR', '3']])

Expected Output: ['BUTTON:3:QUEUED', 'SENSOR:2:PASS', 'SENSOR:3:STOP']

Explanation: Floor 3 is queued, floor 2 is passed, then the elevator stops at requested floor 3.

Hints

Sort events by (time, component priority, original index) before processing.
A small finite-state machine with current_floor, pending_requests, and faulted is enough.

Part 2: Fair LOOK Elevator Scheduler

Implement a scheduling algorithm for one elevator that balances travel efficiency and fairness. The elevator normally follows a LOOK/SCAN-style policy: continue in the current direction serving the nearest pending request in that direction, then reverse when no request remains ahead. To prevent starvation, any request whose wait time reaches max_wait gets priority over the direction rule.

Constraints

1 <= current_floor <= 100000
0 <= len(requests) <= 5000
1 <= floor <= 100000 for every request
0 <= wait_time <= 1000000
0 <= max_wait <= 1000000
Travel time is 1 time unit per floor
After each chosen stop, all remaining requests age by the travel distance to that stop

Examples

Input: (1, 'up', [[5, 0], [2, 0], [8, 0]], 100)

Expected Output: [2, 5, 8]

Explanation: No request is overdue, so the elevator serves upward requests in ascending floor order.

Input: (50, 'up', [[60, 0], [40, 100]], 30)

Expected Output: [40, 60]

Explanation: Floor 40 is already overdue, so fairness overrides the upward direction.

Hints

Use LOOK ordering for efficiency, but check for overdue requests before every stop selection.
For fairness ties, choose highest wait time first, then shortest distance from the current floor, then lower floor.

Part 3: Single-Queue Elevator Request Insertion Trace

Implement a scheduler that maintains exactly one internal queue of pending stops. Requests arrive one at a time. Each new request must be inserted into that single queue so that the elevator serves floors according to LOOK-style ordering from the initial current floor and direction. Return a trace of queue operations, demonstrating for example that requests [1, 99, 2] from floor 1 going up stop at 2 before 99.

Constraints

1 <= current_floor <= 100000
0 <= len(requests) <= 5000
1 <= requests[i] <= 100000
For direction 'up', floors at or above current_floor are served ascending first, then lower floors descending
For direction 'down', floors at or below current_floor are served descending first, then higher floors ascending
For direction 'idle', floors are ordered by distance from current_floor, then lower floor

Examples

Input: (1, 'up', [1, 99, 2])

Expected Output: ['append:1', 'append:99', 'insert:2:before:99', 'pop:1', 'pop:2', 'pop:99']

Explanation: Floor 2 has a smaller upward rank than 99, so it is inserted before 99.

Input: (50, 'down', [10, 40, 60])

Expected Output: ['append:10', 'insert:40:before:10', 'append:60', 'pop:40', 'pop:10', 'pop:60']

Explanation: While going down, floor 40 is served before 10. Floor 60 waits until after reversal.

Hints

Assign each floor a sortable rank based on the initial current floor and direction.
To insert a request, scan the queue until you find the first existing stop with a larger rank.

Part 4: Multi-Elevator Dispatcher with Peak Modes

Implement a dispatcher for a bank of elevators. For each hall request, choose the best available elevator using a deterministic cost function. The dispatcher must ignore out-of-service or full elevators, balance load, prefer elevators already moving toward a request when possible, and support normal, up-peak, and down-peak traffic modes.

Constraints

0 <= len(elevators) <= 1000
0 <= len(requests) <= 10000
Elevator ids are integers
1 <= floor, origin, destination <= 100000
direction is one of -1, 0, 1
0 <= load <= capacity
capacity >= 0
Requests are assigned sequentially; after assignment, the selected elevator reserves one load slot, moves its planned floor to the destination, and adopts the request direction

Examples

Input: ([], [[1, 5]], 'normal', 1)

Expected Output: [-1]

Explanation: There are no elevators available.

Input: ([[1, 1, 0, 0, 2, 0]], [], 'normal', 1)

Expected Output: []

Explanation: No requests produce no assignments.

Hints

For each request, scan all available elevators and compute a cost.
Use tuple tie-breaking: lower cost, then lower current load, then lower elevator id.

Quick Overview