Tuesday, July 21, 2015

thought-works: Object Oriented design for Elevator in a multi-storied apartment



thought-works: Object Oriented design for Elevator in a multi-storied apartment
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
Elevator
  • Moves up/down as per instruction
  • Opens/closes the door
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. 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. The elevator controller reads the next elevator request to be processed and serves it.

DP:
Strategy pattern.


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.
ElevatorController runs the show by reading the next request to process and instructing the elevator what to do.

Extend the answer to multiple elevators

Each elevator have 1 controller.
Floor based requests can be served by any elevator, thus these requests are added to a common area accessible by all controllers.

Each elevator controller runs as a separate thread and checks if it can process a floor request. Mind synchronization issues.
http://ying.ninja/?p=888

How would I design the elevators for a new 40 story office

building that had an average of 100 people per floor to most efficiently fill and empty the building given a standard 9-5 workday and traffic conditions in my city? The answer needed to be completely detailed, including expected passengers per car, time per stop, average floors stops per trip at various hours, etc.
1. Ask
  1. How many elevators are there?
  2. What is the capacity of each elevator?
  3. Is the efficiency goal focused only at the start & end of day & not in between (i.e. lunch time, breaks)?
2. General optimal critiera
  • provide even service to each floor
  • minimize how long passengers wait for an elevator to arrive
  • minimize how long passengers spend to get to their destination floor
  • serve as many passengers as possible
The first advice that I’ve read is to ask some questions before you start answering. It will show that you are strategic & don’t jump to random assumptions. So I will probably ask questions like: Is the efficiency goal focused only at the start & end of day & not in between (i.e. lunch time, breaks)? How many elevators are there? What is the capacity of each elevator?
2) Assuming that everything is average, i.e. 6 elevators, 15 people per elevator, and focus only on start and end date, then the sample data should follow a normal distribution.
730-8 – 2%
8-830 – 14%
830-9 – 34%
9-930 – 34%
930-10 – 14%
10-1030 – 2%
3) I will break this down & solve the worst case scenario first. This means, 34 people x 40 floors = 1360 people to be transported by 6 elevator x 15 = total 90 capacity during 830-9 or 9-930 am.
4) Focusing on this more manageable problem, 1360 / 90 means each elevator will make 15 full cycles (lobby to highest floor and back) 5) Since we want to minimize the cycle time for each elevator, we assign one elevator per subset of 40/6 consecutive floors. This should address the issue on minimizing time per stop. 6) That means, the final design should be a load balancing of the elevators by minimizing the travel time — Elevator A – 1st to 7th floor, B – 8th to 14th floor, and so forth. Do you guys see anything wrong with this line of thinking?
先说说我对单个电梯设计的想法(欢迎批评指正)
1 Elevator Object, 应该包含physical components: Door, Indicator Lights,
Control Panel. 一些性质(Non physical properties): Speed, Num of floors,
capacity, max weight. 所能从事的操作methods: moveto, stop, ringbell。然后电
梯应该能够handle user request, 所以还应有一个requestQueue, 电梯应该根据自己
的state 和 requestQueue做出moveto, stop的决定,所以有一component:
requestHandler(Strategy pattern),可以set不同的requestHanlder.
2 Door, properties: State, method: open, close, getState.
3 Indicator light(指示所到楼层),properties: state; method: on, off,
getState
4 Control Panel, 包含physical component: Floor Buttons, Other buttons(也可直
接把Buttons 当作 elevator的components,还没考虑哪一个方法好)
5 Button, properties: floorNum, Parent Elevator, methods: OnPress(Observer
Pattern).
6 ElevatorRequestHandler: handleRequest(Elevator ele, requestList rlist), 可
以define 一个interface, 然后又各种不同实现
7 Request: 可以define 一个abstract class, 然后有子类movingRequest,
helpRequest doorRequest etc.

A SINGLE ELEVATOR

Use Case:
  1. User
    1. press a button to summon the lift
    2. press a button to get to a specific floor
  2. Button
    1. floor button and level button
    2. illuminates when pressed
    3. place an ‘elevator request’ when pressed
  3. Elevator
    1. moves up/down
    2. open/close the door
ElevatorRequests Class
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. The elevator controller reads the next elevator request to be processed and serves it.
Button (Abstract) Class
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.
In conclusion, ElevatorController runs the show by reading the ElevatorRequests to process and instructing the Elevator what to do. User send request by pressingButtons.

EXTEND THE ANSWER TO MULTIPLE ELEVATORS

  1. Each elevator have 1 controller.
  2. Floor based requests can be served by any elevator, thus these requests are added to a common area accessible by all controllers.
  3. Each elevator controller runs as a separate thread and checks if it can process a floor request. Mind synchronization issues.
https://github.com/mission-peace/Design
public enum Direction {
    UP,
    DOWN
}
public class Status {
    private int currentFloor;
    private Direction direction;
    private int finalDestination;
}

public interface UserInterface {
    void request(Request request);
}

public class Request {
    private long requestTime;
    private int floor;
    private Direction direction;
}
public interface Elevator {
    void toToFloor(int floor);
    void updateIntermediateStops(List<Integer> floor);
    Status getStatus();
}

public interface RulesManager {
    void enqueue(Request request);
    int getNextDestination();
}

http://www.comscigate.com/uml/DeitelUML/Deitel01/Deitel02/
http://www.comscigate.com/uml/DeitelUML/Deitel01/Deitel02/ch08.htm
Event Handling
http://www.comscigate.com/uml/DeitelUML/Deitel01/Deitel02/ch10.htm
Elevator sends an elevatorArrived event to the Elevator's Door when the Elevator arrives at a Floor.

https://www.cs.cmu.edu/~luluo/Courses/18540PhDreport.pdf
Considering the current class diagram in hand, potential defects of our future software design are
stated as following. If a better solution is not found, the software design is going to be a failure.
· Overburden of the central object: From above analysis we can see that the
ElevatorControl object has to act as the central controller that interacts with all other
objects. All the computing and controlling tasks have to be done within this object

· Competing for computing resource: When more than one object want to get controlled
by the central object at the same time, it is inevitable that these objects compete for the
limited computing resources of the controller, and some of the objects may not get timely
control messages for it to keep normal operation, which will cause a fatal defect in realtime
system.

· Low efficiency for the whole system: Even if the computing resources in the controller
are fast/large enough such that every control need is processed and taken into action in
time, central node controlling is still not an efficient solution for a distributed system like
the elevator.

http://www.ryanbyrd.net/2013/04/18/toward-an-optimal-technical-interview-question-the-elevator-design-dilemma/

https://hellosmallworld123.wordpress.com/2014/08/03/design-an-object-oriented-elevator/
The main idea here is to have a centralized bank to schedule the activity to all cars.

The centralized bank sends command to the car and the car fulfills the command in the order specified by the centralized bank. i.e every car has a request queue and each time it takes the next request from head of the queue and goes to that floor. If the request queue is empty, then it simply stopped at the current floor.

So the idea is that centralized bank receives all the input from each floor and each car. and dispatch them to each car. If the input is from one specific car, then the same input is send back to the original car. If the request is from a floor, then the centralized bank will pick a car according to the following order: if a car is standing at that floor, it was send to that car -> if a car (or multiple cars) is moving towards this floor, pick the closest one -> otherwise pick a car standing at another floor -> otherwise pick the first car. When each car received a request, it will insert the car into its request queue. -> if the requested floor is already in the queue, ignore -> otherwise if the floor is on its way up (or down), add it to the list. -> if need to go further to reach the requested floor, add it to proper position as well. (Or we can use two queues one for go up and one for go down to make implementation easier). The whole idea is the centrialized bank dispatch request and car execute request by itself in optimized order.
http://www.1point3acres.com/bbs/thread-147010-1-1.html
一个电梯系统,我写了building,floor, button, elevator几个class。然后用了一个queue装这个elevator接下来要去几层这样。你可以设计的很复杂,也可以很简单。我写了最简单的就是,queue里面是先来后到的。
我记得还有一种比较复杂(但是智能)的设计是用状态机

http://blog.baozitraining.org/2014/07/oo.html
准确理解面试问题是成功面试的第一步,对于OO设计问题更是如此。由于题目的需求相对模糊,面试者需要通过不断的沟通和交流来确定题目中可能被遗漏的细节,从而明确需要实现的步骤和细节。


『设计电梯类』,每个人对于电梯都有一个具体的认知,但面试者自己的理解是否就和面试官一致呢?避免想当然的去假设,多问问题,明确细节,比如:


  • 电梯的容量(载重,载入数)是否考虑?
  • 电梯的运行范围是几层到几层?
  • 是一部电梯还是多个电梯?


当我们相对了解题目的具体需求之后,设计电梯类时要从OO设计基本原则入手,比如封装性,本质上就是讲class内部的状态封装在内,对外提供合理的方法接口。


从方法的角度思考相对直观:根据题目的需求,一个基本的电梯类应该提供什么样的方法呢?


  • 开门、关门
  • 移动到下一目标楼层
  • 接受去目标楼层的请求


以上都是最直观、最基本的方法,相对应的就是电梯内部的基本状态:


  • 电梯门的开关状态 (开关门会影响该状态)
  • 运行方向(移动会影响该状态,该状态也影响下一步行动);
  • 当前楼层 (移动会影响该状态,该状态也影响下一步行动)
  • 需要停的楼层集合(接受去某楼层的请求会影响该状态,该状态影响下一步行动);


如果在细一点,还可以加入『当前载重』,『当前载人数』等,可以使内部的实现更加合理。如果面试官设计的基本方法和内部状态设计没有异议,面试者一般还需要简单的实现一两个重要的方法,在本题中『移动到下一目标楼层』方法,目的在于看面试者是否有能力将接口和内部对象状态封装好。


包子Tips: 面试中很多同学喜欢临时添加变量,比如一开始没有考虑到电梯门的状态,结果到了需要实现开门、关门的方法的时候只能临时补。这样一来容易出错,二来会给面试官留下不好的印象。我们建议同学们在答题之前,最好花一点时间,把需要设计的方法、用到的内部状态想清楚,然后再深入做题,尽量做到思路清晰、连贯。


面向对象的另两个重要特性是继承和多态。设计电梯这个题目可能并不是特别适合考察这两方面,但是OO设计的思路是大概相似的:分析每一个类的外部方法和内部状态是什么,什么样的方法可以抽象成通用的接口,什么样的类之间存在继承关系等。作为一个思考的问题,大家不妨动手做一做『如何设计停车场』这个题目
http://www.columbia.edu/~cs2035/courses/ieor4405.S13/p14.pdf
Non-homogeneous stochastic arrival of customers
 Two types of calls: internal and external
 Has a speed and direction at any point in time
 Doors open and close
 Stationary on a floor until doors close
 Customers can abandon call

Point of Interest
Expected wait time of users in the system
 Maximum wait time
 Expected number of people whose wait time is
substantially greater than the expected wait time
(Quality of Service)
 Expected length of queue
 Energy used (Cost)

An NP Hard Problem
 Proved by Seckinger and Koehler for 1 elevator
without capacity constraints
 Very large state space for solution
 Large number of constraints
 Reduces to a time dependent traveling salesman problem (TDTSP)

Algorithms
 Sectors
 Each elevator has its own sector, a subset of floors, and only
services calls that originate from that sector
 Nearest Elevator
 Each passenger is assigned the nearest elevator as determined by elevator position, direction of call, and elevator direction

 Compute suitability score for
each elevator when new
passenger arrives
 (1) Towards a call, same direction
 FS = (N + 2) - d
 (2) Towards the call, opposite
direction
 FS = (N + 1) - d
 (3) Away from call
 FS = 1
 N = # Floors – 1;
 d = distance between elevator and call

 Nearest Elevator with Capacity Considerations
 Similar to Nearest Elevator, but also takes into account the load in each elevator
Compute suitability score for
each elevator when new
passenger arrives
 (1) Towards a call, same direction
 FS = (N + 2) - d + C
 (2) Towards the call, opposite
direction
 FS = (N + 1) – d + C
 (3) Away from call
 FS = 1 + C
 N = # Floors – 1;
 d = distance between elevator and call
 C = excess capacity of elevator

Can we do better?
 Context Scheduling
 Ant Colony Optimization
 Forecasting
https://github.com/joeblau/sample-elevator-control-system
ElevatorDirection - An elevator can be going in one of three directions
public enum ElevatorDirection {
  ELEVATOR_UP,      // Elevator is going up
  ELEVATOR_DOWN,    // Elevator is going down
  ELEVATOR_HOLD     // Elevator is being held
}
ElevatorStatus - Each elevator has one of two status
public enum ElevatorStatus {
  ELEVATOR_OCCUPIED,  // Elevator is occupied by users inside who are request floors
  ELEVATOR_EMPTY      // Elevator is empty and can be used to request a pickup
}
public class ElevatorImpl implements Elevator {
  private Integer currentFloor;
  private Queue<Integer> destinationFloors;

  @Override
  public ElevatorDirection direction() {
    if (destinationFloors.size() > 0){
      if (currentFloor < destinationFloors.peek()){
        return ElevatorDirection.ELEVATOR_UP;
      } else if (currentFloor > destinationFloors.peek()) {
        return ElevatorDirection.ELEVATOR_DOWN;
      }
    }
    return ElevatorDirection.ELEVATOR_HOLD;
  }

  @Override
  public ElevatorStatus status() {
    return (destinationFloors.size() > 0)?ElevatorStatus.ELEVATOR_OCCUPIED:ElevatorStatus.ELEVATOR_EMPTY;
  }
}
public class ElevatorControlSystem implements ElevatorControlSystemFactory {

  public static final int MAX_ELEVATORS = 16;
  Integer numberOfElevators = 0;
  Integer numberOfFloors = 0;
  ArrayList<Elevator> elevators;
  Queue<Integer> pickupLocations;
}
http://www.electrical-knowhow.com/2012/04/elevator-control-system.html

there are 3 main types for elevator control systems as follows:

1- Single Automatic operation:


  • First automated system w/o single call button on each floor and single button for each floor inside car.
  • Called if no one is using it.
  • Passenger has exclusive use of the car until rip is complete.


2- Selective collective operation:


  • Most common, remembers and answers calls in one direction then reverses. When trip complete, programmed to return to a home landing.


3- Group automatic operation: 


  • For large buildings with many elevators which are controlled with programmable microprocessors to respond. 
https://discuss.leetcode.com/topic/89/write-elevator-program-using-event-driven-programming
You have several functions to control elevator:
moveUp()
moveDown()
stopAndOpenDoor()
closeDoor()
Note:I forgot some parts, but I believe you can figure out which functions are necessary as well - However, you should think about situation that multiple users pushing buttons in different floors. So, obviously you should keep record of buttons pushed, inside and outside of the elevator, sort them, and move the way the elevator should work. You can suppose we have N>1 floors, and currently elevator is in 1 <= m <=N floor, and initialize your class with these numbers and elevator is empty.
For example, I will tell you we have 10 floors and at start the elevator is in floor 2 and empty.
Now, complete these functions using above basic elevator actions to have a fully functional elevator, you can use a class, and for example for at_floor() save the state of elevator in a class variable:
void on_push_button(int num)// When user push in each floor
{
}
void at_floor() // Gives you current floor number
{
}
http://blog.jobbole.com/74672/
http://blog.gssxgss.me/elevator-simulator-java/
Read full article from thought-works: Object Oriented design for Elevator in a multi-storied apartment

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts