## Google Interview Question for Software Engineers

• 1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
3
of 3 vote

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.

We 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.

Comment hidden because of low score. Click to expand.
2

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)

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

4) A busy elevator

Comment hidden because of low score. Click to expand.
0
of 0 vote

What is optimal? Are we attempting to minimize the average waiting time of tenants? Maximize throughput?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

First Lift- serves up to 25th floor- Odd Numbers
Second Lift- serves up to 25th floor- Even Numbers
3rd Lift- serves from(nonstop until) 26th floor to 50- Odd Numbers
4th Lift- serves from (nonstop until) 26th floor to 50- Even Numbers

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

4) A busy elevator

Comment hidden because of low score. Click to expand.
0
of 0 vote

i have a different idea

Comment hidden because of low score. Click to expand.
0
of 0 vote

i have a different idea

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we should be doing something similar to Elevator/Scan disk scheduling here.
Any thoughts?

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.