最近谷歌的面试发放的真的很多，csoahelp给大家带来了新鲜的真题啦。如果需要我们对您的面试进行support，欢迎通过文章末尾的二维码联系我。
Google interviews have been coming in fast and furious lately, and csoahelp.com is here to bring you some fresh new questions straight from the interviews! If you need support with your upcoming interview, feel free to reach out to me through the QR code at the end of this article.
电梯调度问题
问题描述：
面试官：假设你负责管理一个建筑物中的四部电梯，电梯的任务是根据请求接送乘客。电梯的每个请求包含以下信息：请求时间、请求楼层、目的楼层以及请求人数。所有的电梯初始时都停在1楼。你的任务是设计一个调度系统，能够在每个请求到来时，选择最合适的电梯来执行该任务。电梯有最大承载人数限制，并且电梯在没有请求时停留在它们最后服务的楼层。
- 假设楼层总数为8，电梯的最大承载人数为10人，且每个楼层之间的移动时间为1个单位时间。
- 你需要设计一个算法，根据电梯的当前状态（包括位置、忙碌状态和承载人数），实时选择最合适的电梯来执行任务。
Elevator Dispatch Problem
Problem Description:
Interviewer: Imagine you're responsible for managing a building with four elevators. Each elevator starts on the 1st floor. You receive a series of requests to transport passengers to different floors. Each request includes the time of the request, the floor the passenger is currently on, their destination floor, and the number of passengers. Your task is to design an algorithm that efficiently assigns each request to the best available elevator, ensuring that the system operates smoothly.
- There are 8 floors in the building.
- The maximum capacity of each elevator is 10 people.
- It takes 1 unit of time to move from one floor to the next.
- Elevators remain idle on their last serviced floor until the next request.
You must build a scheduling system that can process each request as it arrives in real-time and assigns the optimal elevator to fulfill it.
澄清问题：
候选人：为了更好理解问题，我能否请您举一个具体的输入输出示例？
面试官：当然。假设一开始时间为0，所有的电梯都在1楼。如果在时间点5，有一个请求来自3楼，目的地是7楼，并且这个请求携带3个人。那么你需要选择一个电梯来执行这个任务，并更新电梯的状态。
候选人：我们是否可以假设每个请求都按顺序到达？也就是说，我们一次只处理一个请求，处理完当前请求后再处理下一个请求？
面试官：是的，假设这是一个流式操作，每次我们只收到一个请求，你无法预知未来的请求。
候选人：每个请求会附带时间戳吗？比如{时间, 请求楼层, 目的楼层, 人数}？
面试官：是的，每个请求都有一个时间戳，你需要根据当前时间和电梯的状态来决定哪个电梯更合适。
候选人：这些请求是否都从1楼开始，还是可以从其他楼层开始？
面试官：请求可以从任何楼层开始，并不局限于1楼。
候选人：电梯的最大承载人数是10吗？是否有任何特殊情况，比如电梯超载？
面试官：对的，电梯的最大承载人数为10。如果一次请求的乘客人数超过电梯的最大承载人数，那么该电梯无法处理该请求。
Clarifying Questions:
Candidate: Can you give me an example of input and output for a typical request?
Interviewer: Sure. Let’s say at time 5, you receive a request from floor 3 to go to floor 7 with 3 passengers. You need to choose an elevator that can serve this request efficiently, and then update its state accordingly.
Candidate: Is this a streaming operation where we process each request one by one as they arrive, without knowing future requests?
Interviewer: Yes, you only process one request at a time. You don’t know what requests will come in the future, so each decision is made based on the current state of the elevators.
Candidate: Does every request start from floor 1, or can it start from other floors?
Interviewer: The requests can originate from any floor, not just floor 1.
Candidate: Does the elevator have a maximum capacity of 10 people? What happens if a request exceeds this limit?
Interviewer: Correct, each elevator has a maximum capacity of 10 people. If the request exceeds the elevator’s capacity, that elevator cannot take the request.
解决思路：
候选人：我的思路是创建一个Elevator类来表示每个电梯的状态，包括它的当前楼层、是否忙碌、承载人数以及它的方向。然后我会创建一个ElevatorManager类，用来管理所有电梯。每次有请求到来时，我会遍历所有电梯，找到一个能最快到达请求楼层的电梯，并分配该任务。
面试官：能详细描述一下你的算法是如何选择最优电梯的吗？
候选人：好的。每次有请求到来时，我会遍历所有电梯，计算它们从当前楼层到请求楼层所需的时间。如果电梯目前是空闲的，我会直接计算它从当前位置到请求楼层的距离。如果电梯当前正在执行任务，我会计算它完成当前任务所需的时间，再加上它从当前位置到请求楼层的距离。然后我会选择最短时间的电梯来执行任务。
Solution Approach:
Candidate: My approach would be to create a class Elevator that tracks each elevator’s state—current floor, whether it’s busy or idle, how many people it’s carrying, and its direction of travel. I’d then create an ElevatorManager class to manage all the elevators. Every time a request comes in, the system will evaluate all elevators, calculating which one can handle the request the fastest, and assign the task to that elevator.
Interviewer: How would your algorithm choose the optimal elevator?
Candidate: I would loop through each elevator, calculating the time it would take for that elevator to reach the requested floor. If an elevator is idle, I’d simply calculate the distance between its current floor and the requested floor. If the elevator is busy, I’d calculate when it will be free and then how long it would take to reach the requested floor after completing its current task. The elevator with the shortest time would be assigned the request.
对话与追问：
面试官：在电梯服务完乘客后，它会返回到1楼，还是停留在最后的目的楼层？
候选人：我假设电梯会停留在它最后服务的楼层，等待下一个请求到来。
面试官：如果有多个请求同时到达，且它们需要不同的电梯来服务，你会如何处理？
候选人：如果有多个请求同时到达，我会依次处理每个请求，选择最合适的电梯来执行任务。我会确保每个电梯的状态更新正确，确保不会超载。
面试官：如果电梯在完成任务后仍然满载，如何处理后续的请求？
候选人：当电梯满载时，它不会再接受新请求。我会在电梯到达目的楼层后，释放它的承载人数。接下来，它可以继续接受新的任务。
面试官：如果两个请求之间的楼层没有间隔，电梯是否会直接将这两个任务合并？
候选人：不会，我会分别处理每个请求，确保每个请求被独立分配给合适的电梯。除非是同一个请求中的多个目的地，否则我不会合并任务。
Dialogue and Follow-Up Questions:
Interviewer: Once an elevator completes a task, does it return to floor 1, or does it stay on the floor where it dropped off the passengers?
Candidate: I would assume the elevator stays on the floor where it dropped off the passengers and only moves again when the next request is made.
Interviewer: What if multiple requests come in at the same time, all targeting different elevators? How would you handle that?
Candidate: I’d handle each request sequentially, ensuring that every elevator’s state is updated before moving on to the next request. This way, I ensure that no elevator becomes overburdened and that each request is handled optimally.
Interviewer: What happens if the elevator is full and still receives a new request?
Candidate: If an elevator is at full capacity, it won’t accept any new requests until it has dropped off its passengers. Once the passengers have been dropped off, the elevator’s capacity resets, and it becomes available for new requests.
Interviewer: What if two requests are for adjacent floors, would you merge those tasks for the same elevator?
Candidate: No, I would treat each request as independent, and each would be handled by the elevator that is best suited for that specific request. I wouldn’t combine tasks unless it’s part of the same request.
总结：
这道题目考察了调度系统的设计能力，要求候选人具备优化算法的思维。电梯系统需要实时处理请求，同时保证效率最大化。面试官通过一系列的澄清问题和追问，来了解候选人在应对复杂场景时的设计能力。设计一个能够快速响应、优雅处理多个请求的调度算法，正是这道题目背后的关键考点。
Summary:
This problem tests your ability to design an efficient scheduling system that manages multiple tasks in real time. The candidate demonstrated strong problem-solving skills by focusing on optimizing the elevator’s time and ensuring proper management of capacity. Through a series of clarifying questions and follow-up discussions, the candidate showed a deep understanding of edge cases and how to handle real-time decision-making. The ability to handle multiple requests while keeping the system’s performance optimal is key to solving this type of problem.
如果您需要面试辅助或面试代面服务，帮助您进入梦想中的大厂，请随时联系我。
In this Google interview, I demonstrated my understanding of common algorithmic problems and my problem-solving abilities. Each problem presented different challenges, but all could be solved through logical algorithm strategies.
If you need more interview support or interview proxy practice, feel free to contact us. We offer comprehensive interview support services to help you successfully land a job at your dream company.
