Design an Elevator

Design Elevator system. And then write an algorithm for that Design such that, the user request should be completed in logN time in a N story building with M elevators,
Also discuss elevator Algorithm or data structures used for elevators.

Data Structure Design
A good structure to use for this algorithm is three priority queues:

For the current direction with entries past the current point,
For the opposite direction, and
for the current direction prior to the current point.
Your implementation would first decide the direction, then pick a queue into which to place the requested pair of {from, to} values.

http://stackoverflow.com/questions/12009556/datastructure-for-elevator-mechanism
http://www.i-programmer.info/programmer-puzzles/203-sharpen-your-coding-skills/4561-sharpen-your-coding-skills-elevator-puzzle.html?start=1

OO Design Button Class
A typical lift has buttons(Elevator buttons) inside the cabin to let the user who got in the lift to select his/her desired floor.Similarly each floor has buttons (Floor buttons) to summon the lift to go floors above and floor below respectively. The buttons illuminate indicating the request is accepted. And the lift reaches the requested floor the button stops illuminating.

Use cases: User

• presses the floor button to summon the lift
• presses the elevator button to make the lift move to the desired floor

Floor Button/Elevator Button

• illuminates when pressed
• places a elevator request when pressed

Button is abstract class defining common behavior like illuminate, doNotIlluminate. FloorButton, ElevatorButton extend Button type and define placeRequest() which is invoked when the button is pressed. Both the floor button presses and elevator button presses adds requests at a common place.

Elevator Class:

• Opens/close the door
• ElevatorState: It has a direction (up, down, stand, maintenance), 
• a current floor
• a list of floor requests sorted in the direction. 
• It receives request from elevator Controller
• Passenger it has boarded, also we need to have addPassenger function, and load it can take

ElevatorState enum: 

Each elevator has a set of states. 

• Maintenance: the elevator does not react to external signals (only to its own signals).
• Stand: the elevator is fixed on a floor. If it receives a call. And the elevator is on that floor, the doors open. If it is on another floor, it moves in that direction.
• Up: the elevator moves up. Each time it reaches a floor, it checks if it needs to stop. If so it stops and opens the doors. It waits for a certain amount of time and closes the door (unless someting is moving through them. Then it removes the floor from the request list and checks if there is another request. If so the elevator starts moving again. If not it enters the state stand.
• Down: like up but in reverse direction.

There are additional signals:

• alarm. The elevator stops. And if it is on a floor, the doors open, the request list is cleared, the requests moved back to the bank.
• door open. Opens the doors if an elevator is on a floor and not moving.
• door closes. Closed the door if they are open.

ElevatorRequests:

Each button press results in an elevator request which has to be served. Each of these requests is tracked at a global place. ElevatorRequests, the class which stores elevator requests can use different strategies to schedule the elevator requests. 

ElevatorController:

The elevator is controlled by a controller class which we call ElevatorController. The elevator controller instructs the elevator what to do and also can shutdown/start up the elevator of the building.  serves it. 

ElevatorController runs the show by reading the next request to process and instructing the elevator what to do.  The elevator controller reads the next elevator request to be processed and and schedules to all active elevators (not in maintenance) using requestSchedulingAlgoritm() method.

The scheduling will be like:

• if available pick a standing elevator for this floor.
• else pick an elevator moving to this floor.
• else pick a standing elevator on an other floor.
• else pick the elevator with the lowest load.

How can we extend this to multiple elevators in a sky scraper
In the single elevator scenario, there is an elevator and an elevator controller and a common area where the floor requests and the elevator button request are stored and processed as per the scheduling algorithm.

To extend this to multiple elevators, each elevator will have a corresponding elevator controller. Floor based requests can be served by any elevator where as elevator button requests will be served by the elevator in which the button is pressed.

FloorButton's placeRequest adds a request to the common area which is accessible to all controller. ElevatorButton's placeRequest adds a request to the controller's internal queue as only one elevator is supposed to serve it.

Each elevator controller runs as a separate thread and checks on if it can process a floor request along with processing requests made by its own elevator button presses.

http://thought-works.blogspot.in/2012/11/object-oriented-design-for-elevator-in.html
http://k2code.blogspot.in/2014/04/design-elevator-system.html

• How would you optimize an elevator system for a building with 50 floors and 4 elevators ? Optimize in terms of lowest wait times for the users.

http://www.quora.com/What-are-ways-to-optimize-the-service-algorithm-for-an-elevator
http://dan-nolan.com/how-i-would-optimize-the-elevators-in-our-office-building/

More Reading/Discussion Points:
http://www.hiringlibrary.com/object-oriented-design-interview-for-parking-lot-or-elevator/
http://codereview.stackexchange.com/questions/5723/oop-elevator-design-evaluation
http://massivetechinterview.blogspot.in/2015/07/thought-works-object-oriented-design.html