Write elevator program, using event driven programming

  • 0

    You have several functions to control elevator:

    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

  • 0

    @ghassem Welcome to the new Discuss! Could you please add more information to the problem description, perhaps with at least one example? Thanks.

  • 0

    If applicable, could you please add company to the tags section? Please see here for instructions on how to do so, thanks.

  • 0

    Do we know the numbers of floors in the buildings? Or moveUpd just return false when we reach the top? Can we assume that moveUp moves the elevator to the next floor, respectively moveDown? On which floor is situated the elevator in the beginning ?
    You mentioned event driven programming , what does it mean - Observer pattern, event busses and so on? Is it multithreading system?

  • 0

    'Design an elevator' is a popular system design interview question.

  • 0

    @yrxwin Yes, just need more details.
    Thank you

  • 0

    @elmirap I would say the following are reasonable assumptions:

    1. The number of floors in the building is given to you and is fixed.
    2. The elevator is initially situated on the lobby (first floor). When all passengers have departed their destination floors, the elevator returns to the lobby.
    3. Yes, we can assume that moveUp moves the elevator to the next floor, similar with moveDown.

  • 0

    @1337c0d3r thank you. So in this system we shoudn't take into account users who are standing outside , at the floor and push button go into the elevator or I am wrong?

  • 2

    We can divide into three main components:

    1. User

      • User presses the floor button (can be up or down direction) to summon the elevator.
      • User presses the elevator button to go to the destination floor.
    2. Button

      • An elevator has buttons (ElevatorButton) inside allowing user to choose the destination floor.
      • Each floor has two buttons (FloorButton) to summon the elevator to go up or down from that floor.
      • When the user presses the button, it illuminates.
      • When the elevator reaches the desired floor, the button stops illuminating.
      • Calls placeRequest() to insert into the ElevatorRequest queue when button is pressed.
    3. Elevator

      • Open or close door.
      • Moves up/down.
      • Stores states such as direction (up/down), speed, currentFloor.

    We need a queue to store all request, this can all be encapsulated in an ElevatorRequests class. When a user presses a button, this request has to be served and is added to the processing queue. Elevator requests can be scheduled using different scheduling algorithms. ElevatorController controls the elevator by giving it instructions such as move up/down, or start/shutdown. The elevator controller reads the next elevator request and serves it.

    This diagram may help :)

    0_1462439050435_elevator-class diagram.png

  • 0

    @nixed thank you very much for your work. Nevertheless, I decided to make a little "research "on the topic

  • 0

    Thanks @nixed for sharing your approach! How can we extend this to multiple elevators?

  • 0

    @elmirap you're welcome! Please do share your ideas after your research.

  • 0

    @1337c0d3r Great question.

    Single elevator

    • One Elevator Controller.
    • Floor button requests and Elevator button requests are all stored in a common area.

    Multiple elevator

    • Multiple Elevator Controllers. Each elevator corresponds to an elevator controller 1-1.
    • Floor button requests can be attended by any elevator. (Global).
    • Elevator button requests is served by the elevator in which the button is pressed (Internal to that elevator only). So either there is a mapping between ElevatorButton and an Elevator, or each ElevatorButton has an extra field to assign to a specific Elevator.
    • We can run each elevator controller on a separate thread, be careful of race condition when processing a floor request, ie: Removing a FloorRequest should be guarded with a lock so no two elevator controllers (two threads) are removing the same FloorRequest at the same time.

  • 0

    @nixed Great analysis. For the multiple elevators scenario, where should the global and internal queue be added respectively?

  • 0

    @1337c0d3r The global queue can be added in FloorRequest, while the internal queue can be added in the ElevatorController.

  • 0

    To be more complicated, consider about the accelerate thing:
    On the move of the elevator going up from 1 to 10 floor, a user press up button on the fifth floor. If the elevator is currently at 4, it can not stop due to the distance is too short for it to stop, unless it is at 3 or lower.
    So there should a parameter that indicate the smallest distance for the elevator to stop if we consider about the accelerate thing.

  • 0

    If there are multiple elevators, the controllers I think should not work independently. Some thing may happen like that:
    Controller 1 tolds Controller 2: Task A is assigned to me, but currently it seems more convenient for you, so how about helping me doing task A?

  • 0

    @xidui Yes, sure. This can be a more difficult follow up. There are bunch of edge cases that can come up. I think what's most important is to come up with a workable solution during the duration of an interview.

    Here is a workable algorithm (sure, it's not the most efficient one but it is easy to design and implement):

    1. Create a queue which stores the FloorRequests' pickup floor.

    2. Create another queue which stores the ElevatorRequests' destination floor.

    3. Elevator has these states:

      1. Status:
        • EMPTY
        • OCCUPIED
      2. Direction:
        • UP
        • DOWN
        • HOLD (when opening/closing door)
    4. While status is OCCUPIED and ElevatorRequest queue is not empty, pop it and serves the destination floor immediately. (Change direction, etc...)..

    5. If the status becomes EMPTY:

      • Assume user entering destination floor correctly by exiting at the destination floor he/she pressed, the ElevatorRequest queue should be empty. Then look at FloorRequest's queue and if it's not empty, serves it immediately. Otherwise return to the lobby.

    The above simplistic design has a serious flaw, that is it might cause starvation, ie: The FloorRequest queue may not be served indefinitely as long as ElevatorRequest's queue is non-empty all the time.

  • 0

    @xidui I assume you are talking about the FloorRequest queue, which is global. This is up to the scheduling algorithm to decide which elevator is best served the current task at hand.

  • 0
    This post is deleted!

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.