Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

DataStructure for Elevator Mechanism

This question was asked to me during company interview - Which data-structure is efficient for Implementing Elevator Mechanism?

I am not able to find the efficient data-structure for it even after a lot of Googling.

I can think of Priority queue to Implement it.Is priority queue an efficient data structure or more efficient data structure is there for implementing Elevator Mechanism?

Thanks!

like image 951
Ritesh Kumar Gupta Avatar asked Aug 17 '12 16:08

Ritesh Kumar Gupta


People also ask

Which data structure is used in elevator?

Each lift maintains a queue(data structure). The number of elements in the queue is the maximum number of stops a lift can have.

What algorithm is used in elevator?

The standard SCAN algorithm is even known as the elevator algorithm.

What mechanism does an elevator use?

Most buildings that are taller than four stories use traction elevators. A motor at the top of the shaft turns a sheave—essentially a pulley—that raises and lowers cables attached to the cab and a counterweight. Gears connect the motor and sheave in slower systems.


2 Answers

Since you cannot implement mechanisms in software (although you can certainly model them), I assume that the question has been about the Elevator algorithm.

The algorithm looks deceivingly simple, yet it is surprisingly very tough to implement, even with a good set of data structures in hand. A good structure to use for this algorithm is three priority queues:

  1. For the current direction with entries past the current point,
  2. For the opposite direction, and
  3. 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.

like image 94
Sergey Kalinichenko Avatar answered Nov 05 '22 18:11

Sergey Kalinichenko


What if we used two linked list one for upward direction movement requests and another for downward direction movement request.

e.g

First request: a).while lift is on 0th floor and a requests come for 3rd floor.

linked list for upward movement.

3->null.

linked list for downward movement.

null.

Second request: b). while lift has moved to 1st floor and a request comes from 2nd floor for upward movement.

linked list for upward movement.

2->3->null

linked list for downward movement.

null.

Third request: c) Suppose 2 persons enter on the 2nd floor, one presses button for 5th floor and another for 1st.

linked list for upward movement.

3->5->null

Note: Here 2 has been deleted from upward linked list as it has been reached.

linked list for downward movement.

1->null.

d)Suppose a person enters on 3rd floor and presses button for 0th floor

linked list for upward movement.

5->null

linked list for downward movement.

1->0->null.

Once 5th floor iis reached upward requests linked list becomes empty so downwards linked list can be considered for movement.

If both the linked list are empty then elevator would be at rest.

So i think linked list can also be an effective data structure for elevator

like image 39
sacrishi Avatar answered Nov 05 '22 19:11

sacrishi