Google Interview Question Software Engineers
Country: United States
queue will be overkill and we don't want strict FIFO. Imagine an elevator is requested from 1 floor to 20 and in between 10 floor requests it. Each elevator maintains an array (as a bitmap)
generally the right idea. and I agree with @mithya, no queue. also as @tr030114 mentioned, getting to know the current system is important before beginning to optimize it. For example, what does wait time actually mean? does it simply mean, calling for an elevator and getting into it? Coz, remember this is a really tall building and someone wanting to go to the higher floors from the ground floor might be experiencing a lot to transit time while the elevator picks and drops people on the way up. Your solution although generally good is not clearly addressing this.
Well, first of all we need to ask followup questions. How does it work in its current state. Why is it assumed that it can be optimized. What are the common complaints from users.
Based on this historical data we can tackle the problem areas.
For example, if the tenants on the top half of floors complain that it stops frequently on the bottom half, then you probably are looking at dividing the elevator system between top half and bottom half.
Top half gets two and bottom half get the remaining two elevators.
You get the idea.
Algo: opti target: minimise wait times for the users
assume elevator has constant speed, moving between floors takes time, denoted by T_transfer, if it has to stop at a floor to load or unload user(s), it takes time, denoted by T_load_unload.
Nature: a central controller for scheduling which elevator takes which user request. After scheduling, a task is added to the individual task queue (FIFO) of each elevator.
At time moment T0 a user at floor X requests going to floor Y. The controller calculates which elevator can have the shortest wait time for this user:
1) if an elevator is idle at floor X', calculate wait time is T_transfer(X'-X)
2) if an elevator is busy (currently at floor X' and current task is going to floor Y'), further two sub-cases:
2.1 Find the last "load" request in the task queue of this elevator, and then after the last "load" request find between which two "unload" requests this floor X is located (it could be after the last "unload" request in the queue), let's say between floor a and b or after floor a (a is the last "unload' request floor), so the wait time is the floor a's "unload" time T_unload(a)+T_transfer(a-X)
Find the smallest wait time among all 4 elevators, if the selected elevator is
3) An idle elevator
Add an "load" task in the queue, its absolute "load" time is recorded: T0+T_transfer(X'-X)+T_load_unload, floor: X
Add an "unload" task in the queue, its absolute "unload" time is recorded: T0+T_transfer(X'-X)+2*T_load_unload+T_transfer(X-Y), floor: X
4) A busy elevator
Add an "load" task in the proper position found (see 2 above) in the queue, its absolute "load" time is recorded: T_unload(a)+T_transfer(a-X)+T_load_unload, floor: X; moreover, any existing "unload" time after this new insertion needs to be updated by adding a constant factor T_load_unload
Add an "unload" task in the proper position (similar to 2 above) in the queue (let's say after floor c), its absolute "unload" time is T_unload(c)+T_transfer(c-Y)+T_load_unload, floor: Y; moreover, any existing "unload" time after this new insertion needs to be updated by adding a constant factor T_load_unload
Optimizing latency (wait time)
Have 4 elevators at equal distance from each other (roughly 1/4 distance of the building) and the nearest elevator which is free/coming towards your intended direction stops. As elevators keep on getting called and stopped, some of the elevators have to move (even when not being called) so it maintains roughly 1/4 floor distance from the others.
Open ended:
Optimizing for specific scenarios.
Maybe this is a business building and cafeteria is at top. During lunch times, have concept of 'express' elevator. One elevator goes from ground floor to top floor and other elevator stops at 25th floor from ground floor to top floor. People wanting to go to cafetaria, either go down the main floor or 25th floor to go to top.
First of all in a real world scenario would have to analyze historical usage data:
- are the elevators requested more frequently during certain times ?
- are the elevators requested more frequently for certain floors ?
- what's the average weight of load for each elevator on peak times ?
Let's say the peak times are around 07:30AM - 09:30AM , 11:30 AM - 1:30 PM and 4:30 PM - 6:30PM (lunch time and rush hours).
Now let's analyze the number of people on each floor of the building if this data is available, we can distribute weights to each section of the building, let's say bottom half and upper half.
Now let's think how each elevator should operate, usually it works under a FIFO model, sweeping people through requested floors up, and then going down the way, while there's still space available the elevator would be attending new requests, otherwise if fully occupied(weight max or near max) just ignore (no preemptive interruptions allowed).
Usual default start location for elevators are ground floor, but given historical data if we realize that this would benefit more people from the lower levels on certain times like lunch time and leaving time, then we can program the elevators according to the following rules:
- Default start location: for all elevators always go back to ground floor and stay there waiting for the next request.
- Default start location for peak times: only during lunch and leave peak times (11:30AM - 1:30 PM and 4:30PM - 6:30 PM), half of the elevators available (n/2) should start from the top floor, sweeping it's way down collecting passengers till full. This would prevent passengers from the upper half to wait more than usual as compared to the ones for the bottom half.
Again this will all depend on historical data modelling and planning, this is just a given example scenario.
Algo: opti target: minimise wait times for the users
assume elevator has constant speed, moving between floors takes time, denoted by T_transfer, if it has to stop at a floor to load or unload user(s), it takes time, denoted by T_load_unload.
Nature: a central controller for scheduling which elevator takes which user request. After scheduling, a task is added to the individual task queue (FIFO) of each elevator.
At time moment T0 a user at floor X requests going to floor Y. The controller calculates which elevator can have the shortest wait time for this user:
1) if an elevator is idle at floor X', calculate wait time is T_transfer(X'-X)
2) if an elevator is busy (currently at floor X' and current task is going to floor Y'), further two sub-cases:
2.1 Find the last "load" request in the task queue of this elevator, and then after the last "load" request find between which two "unload" requests this floor X is located (it could be after the last "unload" request in the queue), let's say between floor a and b or after floor a (a is the last "unload' request floor), so the wait time is the floor a's "unload" time T_unload(a)+T_transfer(a-X)
Find the smallest wait time among all 4 elevators, if the selected elevator is
3) An idle elevator
Add an "load" task in the queue, its absolute "load" time is recorded: T0+T_transfer(X'-X)+T_load_unload, floor: X
Add an "unload" task in the queue, its absolute "unload" time is recorded: T0+T_transfer(X'-X)+2*T_load_unload+T_transfer(X-Y), floor: X
4) A busy elevator
Add an "load" task in the proper position found (see 2 above) in the queue, its absolute "load" time is recorded: T_unload(a)+T_transfer(a-X)+T_load_unload, floor: X; moreover, any existing "unload" time after this new insertion needs to be updated by adding a constant factor T_load_unload
Add an "unload" task in the proper position (similar to 2 above) in the queue (let's say after floor c), its absolute "unload" time is T_unload(c)+T_transfer(c-Y)+T_load_unload, floor: Y; moreover, any existing "unload" time after this new insertion needs to be updated by adding a constant factor T_load_unload
One idea is to minimize the time an elevator is spent moving while empty. Assuming an even distribution of people throughout the building and where they want to go, this might be satisfied by spreading out all elevators evenly among floors. ie. make it so elevators always come to rest at floors 1, 17, 33, 50.
- JW March 10, 2015We can also think of "a person pressing an up/down button" as a request. Every time an elevator has dropped off its last person and there are no outstanding requests, move it to the closest floor interval mentioned above that isn't already occupied by another elevator. If there are outstanding requests, address them in a way that maximizes the number of requests handled in a given direction that aren't already "on the way" for another elevator. There is probably some formal definition for this behaviour, but this is the general idea.
We can model the requests as 2 queues, where one is for requests going up, another for going down, and elevators having pointers that move along the queues, removing requests, and adding requests to themselves for processing.
For real world scenarios, we can apply heuristics such as people tend to go from the first floor up to other floors in the morning, and opposite in the evening. This would mean the morning would have elevator resting positions shifted towards the bottom half of the building Vs the opposite in the evening. During the day when movement is more evenly distributed, the elevators can also be evenly distributed.