System Design - Elevator System Design Interview Question
System Design questions are now regular part of the interview process at various organizations. They test the individuals ability to design, visualize, simulate real world scenarios, use correct data structures, apply design patterns. These questions are generally open ended. Usually the interviewer asks candidates to design system using white board. It may even be kind of pair programming where the interviewer also gives his inputs. The depth of the design solution needed depends on the interviewer. Some interviewer might be satisfied if only classes involved and the design overview is explained. While some may go into implementation details a lot.
So in this tutorial we will be designing an Elevator System and also implementing the actual solution.
Video
This tutorial is explained in the below Youtube Video.- Discuss how we will be simulating the elevator design
- Identify the classes involved
- Elevator Design Code - Iteration-1
- Elevator Design Code - Iteration-2
- Elevator Design Code - Iteration-3
Simulate the elevator design
We will be simulating the scenario--
A person is on a particular floor. Suppose Ground Floor. He wants to go to 5th Floor.
So he clicks on the elevator button with up direction.
We will be calling this the ExternalRequest. This Request will be having the direction and the floor on which the button has been pressed by the user i.e. source floor. The elevator will check the available requests if any and then process this request depending on some priority. The elevator reaches the source floor i.e. the 0th or the ground floor. The person enters the elevator. -
The person enters the elevator. The person then presses the 5th floor button in the elevator to indicate the elevator to go to 5th floor.
This will be the internal request. So the internal request will be having only the floor to which the person wants to go to i.e. the destination floor. The elevator moves to the fifth floor. And the person then exits the elevator. - If suppose when the elevator is moving from the ground floor to the fifth floor and it reaches the first floor. At this moment suppose another person on the second floor want's to go in the UP direction. Then the elevator will stop for this request and the person on second floor will enter the elevator. Suppose he presses the 4th floor button. Then the elevator will first stop at 4th floor which was the destination of the person which entered on the second floor. Later the elevator stops on the fifth floor and the person from the ground floor exits.
- If suppose when the elevator is moving from the ground floor to the fifth floor and it reaches the first floor. At this moment suppose another person on the second floor want's to go in the DOWN direction. Then the elevator will not stop for this request immediately. Elevator will first go to the fifth floor where the person from the ground floor will exit. Elevator will then go to the second floor. The person will enter the elevator and press 0. The elevator will then move to the zeroth floor.
Identify the classes involved
-
Enum Direction - This enum will have two values UP and DOWN.
-
Class ExternalRequest - The request made by the person from the floor when he requests for the elevator by pressing either the UP or the DOWN button. It will have the fields enum Direction and integer sourceFloor.
-
Class InternalRequest - The Request made by person when he enters the elevator. The person presses the floor number to which he wants to go. This will be the integer destinationFloor.
-
Class Request - This class will be the encapsulation for the ExternalRequest and InternalRequest. We will be passing this Request to the elevator to be processed. So this class will be having two fields - ExternalRequest and InternalRequest.
-
Enum State - This enum will have three values MOVING, STOPPED and IDLE.
-
Elevator - This class will represent the Elevator. It will have the fields currentFloor, currentState and currentDirection.
Elevator Design Code - Iteration-1
In the first iteration we will be creating the classes we have identified previously.
package com.javastructures;
class Elevator {
private int currentFloor = 0;
private Direction currentDirection = Direction.UP;
private State currentState = State.IDLE;
}
enum State {
MOVING, STOPPED, IDLE
}
enum Direction {
UP, DOWN
}
class Request implements Comparable<Request> {
private InternalRequest internalRequest;
private ExternalRequest externalRequest;
public Request(InternalRequest internalRequest, ExternalRequest externalRequest) {
this.internalRequest = internalRequest;
this.externalRequest = externalRequest;
}
public InternalRequest getInternalRequest() {
return internalRequest;
}
public void setInternalRequest(InternalRequest internalRequest) {
this.internalRequest = internalRequest;
}
public ExternalRequest getExternalRequest() {
return externalRequest;
}
public void setExternalRequest(ExternalRequest externalRequest) {
this.externalRequest = externalRequest;
}
@Override
public int compareTo(Request req) {
if (this.getInternalRequest().getDestinationFloor() == req.getInternalRequest().getDestinationFloor())
return 0;
else if (this.getInternalRequest().getDestinationFloor() > req.getInternalRequest().getDestinationFloor())
return 1;
else
return -1;
}
}
class ExternalRequest {
private Direction directionToGo;
private int sourceFloor;
public ExternalRequest(Direction directionToGo, int sourceFloor) {
this.directionToGo = directionToGo;
this.sourceFloor = sourceFloor;
}
public Direction getDirectionToGo() {
return directionToGo;
}
public void setDirectionToGo(Direction directionToGo) {
this.directionToGo = directionToGo;
}
public int getSourceFloor() {
return sourceFloor;
}
public void setSourceFloor(int sourceFloor) {
this.sourceFloor = sourceFloor;
}
}
class InternalRequest {
private int destinationFloor;
public InternalRequest(int destinationFloor) {
this.destinationFloor = destinationFloor;
}
public int getDestinationFloor() {
return destinationFloor;
}
public void setDestinationFloor(int destinationFloor) {
this.destinationFloor = destinationFloor;
}
}
public class TestElevator {
public static void main(String args[]) {
Elevator elevator = new Elevator();
//person wants to go in up direction from source floor 0
ExternalRequest er = new ExternalRequest(Direction.UP, 0);
//the destination floor is 5
InternalRequest ir = new InternalRequest(5);
Request request1 = new Request(ir, er);
}
}
Elevator Design Code - Iteration-2
In the second iteration we will be adding the logic to start the elevator and process any job if available
package com.javastructures;
import java.util.TreeSet;
class Elevator {
private Direction currentDirection = Direction.UP;
private State currentState = State.IDLE;
private int currentFloor = 0;
/**
* jobs which are being processed
*/
private TreeSet<Request> currentJobs = new TreeSet<>();
/**
* up jobs which cannot be processed now so put in pending queue
*/
private TreeSet<Request> upPendingJobs = new TreeSet<>();
/**
* down jobs which cannot be processed now so put in pending queue
*/
private TreeSet<Request> downPendingJobs = new TreeSet<>();
public void startElevator() {
while (true) {
if (checkIfJob()) {
if (currentDirection == Direction.UP) {
Request request = currentJobs.pollFirst();
processUpRequest(request);
if (currentJobs.isEmpty()) {
addPendingDownJobsToCurrentJobs();
}
}
if (currentDirection == Direction.DOWN) {
Request request = currentJobs.pollLast();
processDownRequest(request);
if (currentJobs.isEmpty()) {
addPendingUpJobsToCurrentJobs();
}
}
}
}
}
public boolean checkIfJob() {
if (currentJobs.isEmpty()) {
return false;
}
return true;
}
private void processUpRequest(Request request) {
// The elevator is not on the floor where the person has requested it i.e. source floor. So first bring it there.
int startFloor = currentFloor;
if (startFloor < request.getExternalRequest().getSourceFloor()) {
for (int i = startFloor; i <= request.getExternalRequest().getSourceFloor(); i++) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("We have reached floor -- " + i);
currentFloor = i;
}
}
// The elevator is now on the floor where the person has requested it i.e. source floor. User can enter and go to the destination floor.
System.out.println("Reached Source Floor--opening door");
startFloor = currentFloor;
for (int i = startFloor; i <= request.getInternalRequest().getDestinationFloor(); i++) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("We have reached floor -- " + i);
currentFloor = i;
if (checkIfNewJobCanBeProcessed(request)) {
break;
}
}
}
private void processDownRequest(Request request) {
int startFloor = currentFloor;
if (startFloor < request.getExternalRequest().getSourceFloor()) {
for (int i = startFloor; i <= request.getExternalRequest().getSourceFloor(); i++) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("We have reached floor -- " + i);
currentFloor = i;
}
}
System.out.println("Reached Source Floor--opening door");
startFloor = currentFloor;
for (int i = startFloor; i >= request.getInternalRequest().getDestinationFloor(); i--) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("We have reached floor -- " + i);
currentFloor = i;
if (checkIfNewJobCanBeProcessed(request)) {
break;
}
}
}
private boolean checkIfNewJobCanBeProcessed(Request currentRequest) {
if (checkIfJob()) {
if (currentDirection == Direction.UP) {
Request request = currentJobs.pollFirst();
if (request.getInternalRequest().getDestinationFloor() < currentRequest.getInternalRequest()
.getDestinationFloor()) {
currentJobs.add(request);
currentJobs.add(currentRequest);
return true;
}
currentJobs.add(request);
}
if (currentDirection == Direction.DOWN) {
Request request = currentJobs.pollLast();
if (request.getInternalRequest().getDestinationFloor() > currentRequest.getInternalRequest()
.getDestinationFloor()) {
currentJobs.add(request);
currentJobs.add(currentRequest);
return true;
}
currentJobs.add(request);
}
}
return false;
}
private void addPendingDownJobsToCurrentJobs() {
if (!downPendingJobs.isEmpty()) {
currentJobs = downPendingJobs;
currentDirection = Direction.DOWN;
} else {
currentState = State.IDLE;
}
}
private void addPendingUpJobsToCurrentJobs() {
if (!upPendingJobs.isEmpty()) {
currentJobs = upPendingJobs;
currentDirection = Direction.UP;
} else {
currentState = State.IDLE;
}
}
}
class ProcessJobWorker implements Runnable {
private Elevator elevator;
ProcessJobWorker(Elevator elevator) {
this.elevator = elevator;
}
@Override
public void run() {
/**
* start the elevator
*/
elevator.startElevator();
}
}
enum State {
MOVING, STOPPED, IDLE
}
enum Direction {
UP, DOWN
}
class Request implements Comparable<Request> {
private InternalRequest internalRequest;
private ExternalRequest externalRequest;
public Request(InternalRequest internalRequest, ExternalRequest externalRequest) {
this.internalRequest = internalRequest;
this.externalRequest = externalRequest;
}
public InternalRequest getInternalRequest() {
return internalRequest;
}
public void setInternalRequest(InternalRequest internalRequest) {
this.internalRequest = internalRequest;
}
public ExternalRequest getExternalRequest() {
return externalRequest;
}
public void setExternalRequest(ExternalRequest externalRequest) {
this.externalRequest = externalRequest;
}
@Override
public int compareTo(Request req) {
if (this.getInternalRequest().getDestinationFloor() == req.getInternalRequest().getDestinationFloor())
return 0;
else if (this.getInternalRequest().getDestinationFloor() > req.getInternalRequest().getDestinationFloor())
return 1;
else
return -1;
}
}
class ExternalRequest {
private Direction directionToGo;
private int sourceFloor;
public ExternalRequest(Direction directionToGo, int sourceFloor) {
this.directionToGo = directionToGo;
this.sourceFloor = sourceFloor;
}
public Direction getDirectionToGo() {
return directionToGo;
}
public void setDirectionToGo(Direction directionToGo) {
this.directionToGo = directionToGo;
}
public int getSourceFloor() {
return sourceFloor;
}
public void setSourceFloor(int sourceFloor) {
this.sourceFloor = sourceFloor;
}
}
class InternalRequest {
private int destinationFloor;
public InternalRequest(int destinationFloor) {
this.destinationFloor = destinationFloor;
}
public int getDestinationFloor() {
return destinationFloor;
}
public void setDestinationFloor(int destinationFloor) {
this.destinationFloor = destinationFloor;
}
}
public class TestElevator {
public static void main(String args[]) {
Elevator elevator = new Elevator();
/**
* Thread for starting the elevator
*/
ProcessJobWorker processJobWorker = new ProcessJobWorker(elevator);
Thread t2 = new Thread(processJobWorker);
t2.start();
try {
Thread.sleep(300);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
ExternalRequest er = new ExternalRequest(Direction.DOWN, 5);
InternalRequest ir = new InternalRequest(0);
Request request1 = new Request(ir, er);
}
}
Elevator Design Code - Iteration-3
In the third iteration we will be adding the logic to add jobs to the elevator
package com.javastructures;
import java.util.TreeSet;
class Elevator {
private Direction currentDirection = Direction.UP;
private State currentState = State.IDLE;
private int currentFloor = 0;
/**
* jobs which are being processed
*/
private TreeSet<Request> currentJobs = new TreeSet<>();
/**
* up jobs which cannot be processed now so put in pending queue
*/
private TreeSet<Request> upPendingJobs = new TreeSet<>();
/**
* down jobs which cannot be processed now so put in pending queue
*/
private TreeSet<Request> downPendingJobs = new TreeSet<>();
public void startElevator() {
System.out.println("The Elevator has started functioning");
while (true) {
if (checkIfJob()) {
if (currentDirection == Direction.UP) {
Request request = currentJobs.pollFirst();
processUpRequest(request);
if (currentJobs.isEmpty()) {
addPendingDownJobsToCurrentJobs();
}
}
if (currentDirection == Direction.DOWN) {
Request request = currentJobs.pollLast();
processDownRequest(request);
if (currentJobs.isEmpty()) {
addPendingUpJobsToCurrentJobs();
}
}
}
}
}
public boolean checkIfJob() {
if (currentJobs.isEmpty()) {
return false;
}
return true;
}
private void processUpRequest(Request request) {
int startFloor = currentFloor;
// The elevator is not on the floor where the person has requested it i.e. source floor. So first bring it there.
if (startFloor < request.getExternalRequest().getSourceFloor()) {
for (int i = startFloor; i <= request.getExternalRequest().getSourceFloor(); i++) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("We have reached floor -- " + i);
currentFloor = i;
}
}
// The elevator is now on the floor where the person has requested it i.e. source floor. User can enter and go to the destination floor.
System.out.println("Reached Source Floor--opening door");
startFloor = currentFloor;
for (int i = startFloor + 1; i <= request.getInternalRequest().getDestinationFloor(); i++) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("We have reached floor -- " + i);
currentFloor = i;
if (checkIfNewJobCanBeProcessed(request)) {
break;
}
}
}
private void processDownRequest(Request request) {
int startFloor = currentFloor;
if (startFloor < request.getExternalRequest().getSourceFloor()) {
for (int i = startFloor; i <= request.getExternalRequest().getSourceFloor(); i++) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("We have reached floor -- " + i);
currentFloor = i;
}
}
System.out.println("Reached Source Floor--opening door");
startFloor = currentFloor;
for (int i = startFloor - 1; i >= request.getInternalRequest().getDestinationFloor(); i--) {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("We have reached floor -- " + i);
currentFloor = i;
if (checkIfNewJobCanBeProcessed(request)) {
break;
}
}
}
private boolean checkIfNewJobCanBeProcessed(Request currentRequest) {
if (checkIfJob()) {
if (currentDirection == Direction.UP) {
Request request = currentJobs.pollLast();
if (request.getInternalRequest().getDestinationFloor() < currentRequest.getInternalRequest()
.getDestinationFloor()) {
currentJobs.add(request);
currentJobs.add(currentRequest);
return true;
}
currentJobs.add(request);
}
if (currentDirection == Direction.DOWN) {
Request request = currentJobs.pollFirst();
if (request.getInternalRequest().getDestinationFloor() > currentRequest.getInternalRequest()
.getDestinationFloor()) {
currentJobs.add(request);
currentJobs.add(currentRequest);
return true;
}
currentJobs.add(request);
}
}
return false;
}
private void addPendingDownJobsToCurrentJobs() {
if (!downPendingJobs.isEmpty()) {
System.out.println("Pick a pending down job and execute it by putting in current job");
currentJobs = downPendingJobs;
currentDirection = Direction.DOWN;
} else {
currentState = State.IDLE;
System.out.println("The elevator is in Idle state");
}
}
private void addPendingUpJobsToCurrentJobs() {
if (!upPendingJobs.isEmpty()) {
System.out.println("Pick a pending up job and execute it by putting in current job");
currentJobs = upPendingJobs;
currentDirection = Direction.UP;
} else {
currentState = State.IDLE;
System.out.println("The elevator is in Idle state");
}
}
public void addJob(Request request) {
if (currentState == State.IDLE) {
currentState = State.MOVING;
currentDirection = request.getExternalRequest().getDirectionToGo();
currentJobs.add(request);
} else if (currentState == State.MOVING) {
if (request.getExternalRequest().getDirectionToGo() != currentDirection) {
addtoPendingJobs(request);
} else if (request.getExternalRequest().getDirectionToGo() == currentDirection) {
if (currentDirection == Direction.UP
&& request.getInternalRequest().getDestinationFloor() < currentFloor) {
addtoPendingJobs(request);
} else if (currentDirection == Direction.DOWN
&& request.getInternalRequest().getDestinationFloor() > currentFloor) {
addtoPendingJobs(request);
} else {
currentJobs.add(request);
}
}
}
}
public void addtoPendingJobs(Request request) {
if (request.getExternalRequest().getDirectionToGo() == Direction.UP) {
System.out.println("Add to pending up jobs");
upPendingJobs.add(request);
} else {
System.out.println("Add to pending down jobs");
downPendingJobs.add(request);
}
}
}
enum State {
MOVING, STOPPED, IDLE
}
enum Direction {
UP, DOWN
}
class Request implements Comparable<Request> {
private InternalRequest internalRequest;
private ExternalRequest externalRequest;
public Request(InternalRequest internalRequest, ExternalRequest externalRequest) {
this.internalRequest = internalRequest;
this.externalRequest = externalRequest;
}
public InternalRequest getInternalRequest() {
return internalRequest;
}
public void setInternalRequest(InternalRequest internalRequest) {
this.internalRequest = internalRequest;
}
public ExternalRequest getExternalRequest() {
return externalRequest;
}
public void setExternalRequest(ExternalRequest externalRequest) {
this.externalRequest = externalRequest;
}
@Override
public int compareTo(Request req) {
if (this.getInternalRequest().getDestinationFloor() == req.getInternalRequest().getDestinationFloor())
return 0;
else if (this.getInternalRequest().getDestinationFloor() > req.getInternalRequest().getDestinationFloor())
return 1;
else
return -1;
}
}
class ProcessJobWorker implements Runnable {
private Elevator elevator;
ProcessJobWorker(Elevator elevator) {
this.elevator = elevator;
}
@Override
public void run() {
/**
* start the elevator
*/
elevator.startElevator();
}
}
class AddJobWorker implements Runnable {
private Elevator elevator;
private Request request;
AddJobWorker(Elevator elevator, Request request) {
this.elevator = elevator;
this.request = request;
}
@Override
public void run() {
try {
Thread.sleep(200);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
elevator.addJob(request);
}
}
class ExternalRequest {
private Direction directionToGo;
private int sourceFloor;
public ExternalRequest(Direction directionToGo, int sourceFloor) {
this.directionToGo = directionToGo;
this.sourceFloor = sourceFloor;
}
public Direction getDirectionToGo() {
return directionToGo;
}
public void setDirectionToGo(Direction directionToGo) {
this.directionToGo = directionToGo;
}
public int getSourceFloor() {
return sourceFloor;
}
public void setSourceFloor(int sourceFloor) {
this.sourceFloor = sourceFloor;
}
@Override
public String toString() {
return " The Elevator has been requested on floor - " + sourceFloor + " and the person wants go in the - "
+ directionToGo;
}
}
class InternalRequest {
private int destinationFloor;
public InternalRequest(int destinationFloor) {
this.destinationFloor = destinationFloor;
}
public int getDestinationFloor() {
return destinationFloor;
}
public void setDestinationFloor(int destinationFloor) {
this.destinationFloor = destinationFloor;
}
@Override
public String toString() {
return "The destinationFloor is - " + destinationFloor;
}
}
public class TestElevator {
public static void main(String args[]) {
Elevator elevator = new Elevator();
/**
* Thread for starting the elevator
*/
ProcessJobWorker processJobWorker = new ProcessJobWorker(elevator);
Thread t2 = new Thread(processJobWorker);
t2.start();
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
ExternalRequest er = new ExternalRequest(Direction.UP, 0);
InternalRequest ir = new InternalRequest(5);
Request request1 = new Request(ir, er);
/**
* Pass job to the elevator
*/
new Thread(new AddJobWorker(elevator, request1)).start();
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
Run the program as a Java Application -
We now process a request such that the elevator is on the Ground i.e. 0th floor and a person on 5th floor wants to go to the ground floor i.e. Oth floor
public class TestElevator {
public static void main(String args[]) {
Elevator elevator = new Elevator();
/**
* Thread for starting the elevator
*/
ProcessJobWorker processJobWorker = new ProcessJobWorker(elevator);
Thread t2 = new Thread(processJobWorker);
t2.start();
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
ExternalRequest er = new ExternalRequest(Direction.DOWN, 5);
InternalRequest ir = new InternalRequest(0);
Request request1 = new Request(ir, er);
/**
* Pass job to the elevator
*/
new Thread(new AddJobWorker(elevator, request1)).start();
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
Download Source Code
Download it -Elevator Design Code