Amazon 电梯设计

楼主前段时间Amazon onsite,遇到了Amazon经典的电梯设计题目,下面是我对这个题目的总结,也是答案不是最好的,欢迎大家来补充。
 
 
我感觉对于OOP设计问题,关键要和面试官进行讨论,弄清情景situation ,who will use it,在这个situation都是有哪些对象,他们在干什么,他们之间是什么关系,然后一个对象一个对象的去分析这个对象应有的属性,和行为。多和面试官讨论,越细致越好!如果可以使用什么单例,或者factory method 来设计的话,multi threading, 就尽量的添加上这些东西。
 

elevator:

First ask the interviewer what kind of elevator?  there is only one elevator serving that building or multiple elevators serving the building simultaneously?
this situation is that: there is one elevator serving the building.  there are many floors in the buliding. Maybe there are some users in different floor pressing the button simultaneously. This results in some requests to RequestProcessCenter for processing. The  RequestProcessCenter figure out the first request that need to be processed in such an algorithm that the distance between target floor and current floor is shortest.
First describe the whole situation. and check it with your interviewer;
Second sketch out the main classes and methods on the whiteboard;
So we need the following classes:
public class User {
private name;
public pressButton(int toFloor) {
    Request req = new Request( toFloor);
    RequestProcessCenter  center = RequestProcessCenter.getInstance();
    center.addRequest(req);
}
}
public class Request {
    private int toFloor;
    public Request(int _toFloor) {
        toFloor = _toFloor;
}
public getToFloor() {
    return toFloor;
}
}
public class Elevator {
    public static Elevator instance = null;
    private int currentFloor;
    public static Elevator( ) {
        if (instance == null) {  // late loading and eager loading
                    // connection pool
            synchronized (Elevator.class) {
                instance = new Elevator();
}
}
return instance;
}
public getInstance() {
    if (instance == null) {
            synchronized (SingletonDemo.class) {
                instance = new Elevator();
}
}
return instance;
}
public getCurrentFloor() {
    return currentFloor;
}
public moveToTargetFloor(int toFloor) {
    currentFloor = toFloor;
}
public void moveUp();
public void moveDown();
}
public RequestProcessCenter implements runnable {
    public LinkedList<Request> queue;
public RequestProcessCenter( ) {
        queue = new LinkedList<Request>( );
}
public void run() {
        while ( true ) {
            processRequest( )
}
}
public void addRequest(Request request) {
    queue.add(request);
}
public void removeRequest(Request request) {
    queue.remove(request);
}
public Request getNextRequest( ) {
    Request shortestReq = null;
    int shortest = Integer.MAX_VALUE;
    int curFloor = Elevator.getInstance( ).getCurrentFloor( );
    for (Request item : queue) {
        int distance = Math.abs(curFloor – item.getToFloor( ) );
        if (distance < shortest) {
            shortest = distance;
            shortestReq = item;
}
}
return shortestReq;
}
public void processRequest( ) {
    Request req = getNextRequest( );
if (req != null) {
        int toFloor = req.getToFloor( );
        Elevator.getInstance.moveToTargetFloor( toFloor);
        queue.remove(req);
}
   
}
}
 
 
 

First there is an elevator class. It has a direction (up, down, stand, maintenance), a current floor and a list of floor requests sorted in the direction. It receives request from this elevator.

Then there is a bank. It contains the elevators and receives the requests from the floors. These are scheduled to all active elevators (not in maintenance).

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.

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.

EDIT: Some elevators don’t start at bottom/first_floor esp. in case of skyscrapers.

min_floor & max_floor are two additional attributes for Elevator.

I’ve seen many variants of this problem. One of the main differences (that determines the difficulty) is whether there is some centralized attempt to have a “smart and efficient system” that would have load balancing (e.g., send more idle elevators to lobby in morning). If that is the case, the design will include a whole subsystem with really fun design.

A full design is obviously too much to present here and there are many altenatives. The breadth is also not clear. In an interview, they’ll try to figure out how you would think. However, these are some of the things you would need:

  1. Representation of the central controller (assuming there is one).

  2. Representations of elevators

  3. Representations of the interface units of the elevator (these may be different from elevator to elevator). Obviously also call buttons on every floor, etc.

  4. Representations of the arrows or indicators on each floor (almost a “view” of the elevator model).

  5. Representation of a human and cargo (may be important for factoring in maximal loads)

  6. Representation of the building (in some cases, as certain floors may be blocked at times, etc.)

http://stackoverflow.com/questions/493276/modelling-an-elevator-using-object-oriented-analysis-and-design