Design an algorithm for an elevator during COVID-19.

Question

Design an algorithm for an elevator during COVID-19.

Asked at Google over a year ago

3.6k views

Asked at

3.6k views

How to answer Technical questions

Interview Guide

Top Technical interview questions

Imagine you're the product manager for Facebook Marketplace. Since many sellers don't mark items as sold, what existing functionality and metrics could you use to determine whether an item has likely sold?7 answers | 20.9k views
What happens when you enter a URL in your browser?6 answers | 10.8k views
How does TinyURL work?5 answers | 317k views
See Technical PM Interview Questions

Invite members
Invite by email

Add another

hjc · Answer 1 · 2020-09-29T06:45:12+0000

Google pm technical interview question: Design an algorithm for an elevator during COVID-19.

Clarification:

Does the elevator have standard controls? like
- On each floor, there are 1 up button, 1 down button and 1 door button to keep the door open.
- Inside the elevator, there are 1 button to keep the door open, 1 button to close the door and N floor buttons corresponding to the N floors. [Correct]
The normal user journey is:
- User arrive at floor N.
- User press the directional button.
- Elevator move to floor N, and the directal button LED is turned off.
- User enter the elevator, select the button M corresponding to the destination floor.
- Elevator move to floor M.
- Door open and user exit the elevator.
- Elevator will move to pick up the next user.
- Depending on the controller algorithm, the order of serving different users might be different.[Correct]
This question is about designing the controller algorithm of an elevator? [Yes]
How many carts will this controller control? [can be 1 or multiple, such as 3]
Can I start with designing a single controller, single cart elevator system? [Sure]
Interpreting Covid,
- we will carry only 1 passenger at any given time? [Yes]
- Do we need to sanitize the cart each time after passenger exits?[No, they will be wearing masks]

Elevator Controller Strategy

There are multiple attributes that might apply to an elevator. Such as

Speed, how quickly the elevator moves.
Waiting Time, to minimize the user waiting time.
Throughput, how many passengers can be served during a given time period
Efficiency, trying to fit as many passenger as possible during the trip
Fairness, users who presses the call button first will be served first.
Privacy, trying to fit less user during the trip to ensure quality of experience.

Goal

Can I assume the goal is to design an elevator controller algorithm, which will
- Priority 1: Privacy, Only carry maxim 1 passenger at any given time.
- Priority 2: Fairness, Make sure passengers who press the call button first are served first. [Sounds good]

Solution

Simplest system, which I will envision the system to have 1 controller object and 1 cart object
1. The controller object will keep a queue of user requests (FIFO). Each time a user presses the call button, the floor number and the direction will be enqueued. Such as (3, UP) representing an user on the 3rd floor is requesting to go up.
2. The controller will extract the next user to be served from the head of the queue, and move to the corresponding floor N.
3. After user enter the cart, user will select the destination floor M. This destination number can be read from the cart object.
4. The controller will move the user UP to floor M. (without responding to other requesting users along the way)
5. At floor M, user exit the cart. The controller will go to step 2 to serve the next user.

Corner cases

Multiple users at the same floor requesting to go to the same direction.
- This can be handled by advising users to queue up at each floor, and only one user is allowed to enter the cart.
- The next user will need to press the call button again after the cart leaves.
User request to go UP (or DOWN), but after entering the cart, he chooses a floor number which is contrary to the direction.
- The controller object can ignore the input, prompt the user to select the right numbers
Ensure user exits the cart after they arrive at the requested floor.
- The cart object can utilize weight sensor to determine if the cart is empty, and whether any user entered before the previous user exits.
- The cart object can prompt all users to exit if it detects such cases.
Multiple Users enters the cart.
- The cart object can detect in a similar manner using the weight sensor.
Sometimes on the way moving to serve next users, there are users we can serve to improve efficiency. For example,
- The cart is at floor 10, moving to floor 1 to pick up the next user A
- There is another user B, who is on floor 8, calling to move down.
- As it's certain that if the elevator pick up user B, he will always exit before the elevator stopps at floor 1.
- This will break the fairness rule, but will reduce the waiting time.
- Here I will stick strictly to the fairness rule and don't allow this scenario.

Single Controller, Multiple Cart

The same design can easily scale to multiple cart system. there will be 1 controller object and N cart object.
- When a cart is free, it will signal the controller.
- When the controller is free, it will be polling the status of all carts.
- If it finds a free cart, the controller object will extract the next passenger to serve from the top of the queue and move the cart to the requested floor.
- The cart status will be changed to busy during the trip.

Summary

The system I designed here features strict control of only 1 passenger during the whole trip. It also ensures users who press the call button first will be served first. There are cases where efficiency can be further improved, but we choose not to address it since during COVID pandemic, the privacy and fairness are far more important than efficiency.

Harsha Bornfree · Answer 2 · 2022-10-16T18:05:43+0000

Not going into clarifying questions of company and product as Google doesn't make lifts.
I'll try to aim for contactless operation (increase safety) but which may involve some trade-offs from users.

Pain-points for users (regular):

Save effort in climbing stairs
Save time in reaching destination

With Covid, we additionally have:

Keep contact with surfaces to minimum
Maintain social distancing

User journey:

Request lift to source
Enter lift and request destination
Alight at destination
Additionally:
- Know status of lift (location and direction)
- Override doors to speed up

Now we can design an algorithm and other aspects. As this question is about the algorithm, let’s not focus much on other aspects of social-distancing etc.

Other aspects:

Retrofit request button with a proximity sensor (toothpicks if we are budget conscious)
Limit capacity to 4

Algorithm

For 1 lift only:
- Less than 10 floors:
  - Make lift auto-stop at alternate floors. User may have to descend 1 floor at max.
  - Reduce stop time at floor. If there are fewer people in the lift, they won’t take long to move out.
  - Lift stops at other floors if requested.
- More than 10 floors:
  - Lift auto stops at every 3rd floor. User may have to descend 2 floors at max.
  - Reduced stop time.
  - Lift stops at other floors if requested.
- If lift is empty (by weight), it clears all future destinations and waits.
- If lift is empty and is requested, it moves to destination directly. Unless someone requests midway.
For multiple lifts, we can split their operation between top and bottom half of the building.

Evaluation criteria:

Contact points : 0
Wait time
- Max:
  - Person waiting on ground requests for a lift that has just left: # of floors / 2 stop-time x 2 = # of floors stop-time if someone is alighting on the top most floor.
  - Of course this will increase if other people are requesting stops on the way. But that would happen in regular lifts also.
Effort:
- Max: Descending 1 floor or 2.
- This is a worthwhile trade-off for Covid.

productmanager1644 · Answer 3 · 2021-01-24T02:13:32+0000

CLARIFY:
1. Is there a specific type of elevator you want me to focus on (ex. passenger, food, service, etc.)? Focus on elevator carrying people but otherwise your choice.
2. Is there a specific type of environment I need to design for (office, apartment, etc.)? Your choice.
3. Are there limitations, like budget? No.
USERS OF PASSENGER ELEVATORS: I'd like to focus on elevators in an apartment building setting. There are two main types of elevators: front elevators and back / service elevators with the user groups below. I'd like to focus on the front elevators mainly used by everyday passengers because extra consideration must be considered for COVID given the question. Front elevators will receive more traffic / have a higher likelihood of seeing groups of people.
1. Everyday Passengers: People living in apartments or visitors (family, friends, etc.). Will generally only use the front elevator.
2. Servicemen: Delivery, construction, housekeeping, etc. Will only use the back / service elvator.
3. Doorman: Consistently at the building. Will generally use the back / service elevator but may also use the front one.
USER JOURNEY:
1. User pushes button on floor to go up or down.
2. Elevator arrives.
3. User checks if elevator is at capacity / if there is enough space to socially distance. (New part of the journey due to COVID.)
4. User enters elevator assuming there is enough space.
5. User pushes destination floor button.
6. Elevator goes to floor.
7. User gets off.
PAINPOINTS: Because of the COVID aspect of the question, I'd like to focus on #3: the elevator has too many people / user cannot socially distance.
1. Long waiting time for the elevator to arrive.
2. Elevator is full / at capacity due to space constraints (non-COVID related).
3. Elevator isn't full but there are too many people in it (due to COVID / social distancing reasons).
4. Elevator gets stuck.
5. Elevator is slow / makes too many stops.
SOLUTIONS: Below are high level solutions to solve the capacity problem. I'd like to design an algorith with an elevator that enforces social distancing automatically. A combination of these solutions will be used in the algorithm.
1. HEAT SENSOR: Elevator scans individuals and checks to see if the elevator is at capacity (set # of people in cart). Dogs don't trigger the sensor because the heat sensor doesn't count beings with 4 legs. (Note, special parameters could be added for dogs with 3 legs or dogs with 2 legs / wheelchairs, but these cases are rare.) Babies don't trigger the sensor because of size capacities (ex. living creatures under 2 ft).
2. SKIP FLOOR: Elevator skips newly requested floor (i.e. if the floor was requested by someone outside of the elevator) if it is at capacity.
3. WON'T MOVE: Elevator won't move if it is too full.
4. ELEVATOR ANNOUNCEMENTS: Elevator tells people to get out of the elevator at a floor if it is too full.
DETAILED SOLUTION / ALGORITHM: I am using outside floor request to mean a request to arrive from a user outside the elevator and inside floor request to mean a request to go to a certain floor from inside the elevator.
1. Elevator receives outside floor request and logs it it in its queue.
2. Elevator checks if the outside floor request is up or down - i.e. the direction it is currently moving in.
  1. If the outside floor request is in the direction the elevator is moving in, the elevator checks whether the outside floor request floor is on its way to the next floor in the queue or if it is past the next floor in the queue. (Ex. elevator is going to floor 10 and the outside floor request is floor 8 or floor 11).
    1. If the outside floor request is past the next floor request, the elevator logs it behind the next floor it is going to.
    2. If the outside floor request is before the next floor it is going to, the elevator moves that request in front of the next floor it had originally planned on going to. (Ex. instead of going to floor 10, it goes to floor 8 first if moving up.)
  2. If the outside floor request is in the opposite direction the elevator is moving in, the elevator logs it behind all the floor requests in its current direction (i.e. the elevator will go to the floor when it turns around).
3. Elevator scans capacity with heat sensor to check if elevator is at capacity.
  1. If the elevator is at capacity, the elevator goes to the next inside floor request to allow people to exit the elevator.
  2. If the elevator is not at capacity and the outside floor request is on the way to the inside floor request (ex. elevator is going to floor 10 and the outside floor request is floor 8), elevator arrives at that floor.
4. Each time someone enters the elevator, the elevator scans the elevator to see if it is at capacity.
  1. If the elevator is on a floor and too many people try to enter the elevator, it announces that the elevator is full / wait for the next elevator.
  2. If people ignore the elevator request and cram into the elevator, the elevator makes the announcement again and tells the users it won't move until the elevator capacity is reduced.
    1. Elevator won't move until the capacity is reduced.
    2. Once people exit the elevator / capacity is OK for a social distancing requirement, elevator reminds people to maintain distance (ex. 6 feet - assuming that works with the preset capacity constraints) and begins to move and follows the steps.