在过去的一周内，谷歌的面试中出现了几道非常具有挑战性的算法题目。这些题目不仅考察了候选人的编程能力，还特别关注了他们的逻辑思维、数据结构的运用以及在复杂场景下处理边界条件的能力。对于正在准备谷歌或其他大厂技术面试的同学来说，这些题目是一次非常宝贵的锻炼机会。如果你能够高效地解决这些问题，那么在真实的面试中脱颖而出将不再是难事！
今天，我们将分享谷歌近期的三道面试真题，这些题目涵盖了会议安排、去重消息处理以及DNS时间段管理。每道题目都模拟了真实面试中的对话与思维过程，帮助大家更好地理解面试官的思路和期望。如果你在这些题目上遇到困难，不用担心，我们的面试辅导团队可以帮助你攻克这些难关，提升你的面试表现。准备好迎接挑战了吗？让我们一起来看看这些高频真题吧！
Over the past week, Google’s interviews have featured some exceptionally challenging algorithm questions. These questions not only assess candidates’ coding skills but also focus on their logical thinking, application of data structures, and handling of edge cases in complex scenarios. For those preparing for Google or other tech giant interviews, these problems offer a valuable opportunity for practice. If you can tackle them efficiently, standing out in the real interview will be within reach!
Today, we’ll be sharing three of Google’s recent interview questions, covering topics like meeting scheduling, duplicate message handling, and DNS time slot management. Each problem simulates the real interview process with dialogues and thought processes, helping you better understand the expectations and reasoning of interviewers. Struggling with these problems? Don’t worry – our interview coaching team is here to help you conquer these challenges and improve your interview performance. Ready for the challenge? Let’s dive into these high-frequency real interview questions!
面试一：安排会议时间
问题描述
面试官：你有一个会议列表，每个会议都有开始和结束时间，由于你很忙，所以会议可能会重叠。此外，你有一个“禁止安排”时间段（DNS时间段），在这个时间段你不参加任何会议。任何与DNS时间段重叠的会议需要被自动调整，使其不再与DNS时间段重叠。返回一个不重叠的时间区间列表，这些区间表示你在开会的时间段。
示例输入：
- 会议：[ (1, 7), (5, 10), (12, 30), (22, 30), (40, 50), (60, 70)]
- DNS：[18, 25]
示例输出：
- 不重叠会议时间段：[ (1, 10), (12, 18), (25, 30), (40, 50), (60, 70) ]
Interview 1: Scheduling Meeting Times
Problem Description
Interviewer:
You have a list of meetings in your calendar, each with a start and end time. Due to your busy schedule, some of these meetings may overlap. Additionally, there is a "Do Not Schedule" (DNS) time period during which you do not attend any meetings. Any meeting that overlaps with the DNS period must be automatically adjusted so that it no longer overlaps with the DNS period. Return a list of non-overlapping time intervals representing the times you are in meetings.
Example Input:
Meetings: [(1, 7), (5, 10), (12, 30), (22, 30), (40, 50), (60, 70)]
DNS: [18, 25]
Example Output:
Non-overlapping meeting intervals: [(1, 10), (12, 18), (25, 30), (40, 50), (60, 70)]
澄清问题
候选人：这个问题的意思是，任何与DNS时间段重叠的会议都必须调整吗？
面试官：是的，所有重叠的部分都必须从会议时间段中移除。
候选人：我们假设这些时间区间都是左闭右开的，即包含起始点但不包含结束点，对吗？
面试官：对，所有区间都遵循左闭右开的方式。
Clarifying Questions
Candidate:
Does this mean that any meeting that overlaps with the DNS period must be adjusted?
Interviewer:
Yes, any part of the meeting that overlaps with the DNS period must be removed.
Candidate:
Are we assuming that these intervals are left-inclusive and right-exclusive, meaning that the start time is included but the end time is not?
Interviewer:
Correct, all intervals are left-inclusive and right-exclusive.
解决思路
候选人：我的思路是先遍历所有会议时间段，然后检查每个会议是否与DNS时间段重叠。如果有重叠，我们要将会议分成不重叠的部分。我会先处理会议的前半部分，然后处理后半部分，确保DNS时间段中的部分完全被移除。
面试官：那你的算法复杂度是多少？
候选人：我的算法需要遍历所有的会议时间段，因此时间复杂度是O(n)，其中n是会议的数量。对每个会议时间段进行检查和调整的复杂度也是O(1)，所以总体时间复杂度是O(n)。
面试官：好，你能考虑一下边界条件吗？
候选人：是的，边界条件包括会议时间完全在DNS时间段之外、会议时间完全包含DNS时间段，或者会议时间完全被DNS时间段覆盖。我会为这些情况分别处理。
Approach and Thought Process
Candidate:
My idea is to first iterate through all the meeting intervals and check if they overlap with the DNS period. If there is an overlap, I'll split the meeting into non-overlapping parts. I will first handle the portion of the meeting before the DNS period, then handle the portion after the DNS period, ensuring that the DNS period is fully excluded.
Interviewer:
What would the complexity of your algorithm be?
Candidate:
My algorithm needs to traverse all the meeting intervals, so the time complexity would be O(n), where n is the number of meetings. Checking and adjusting each meeting is done in O(1), so the overall time complexity remains O(n).
Interviewer:
Can you consider edge cases?
Candidate:
Yes, edge cases would include meetings that fall entirely outside of the DNS period, meetings that completely encompass the DNS period, or meetings that are fully covered by the DNS period. I would handle these cases separately.
对话与追问
面试官：那么，如果有多个重叠的会议时间段，你如何处理这些区间呢？
候选人：如果有多个会议时间段重叠在一起，我会先调整其中的一个时间段，然后处理下一个，保证调整后的时间段与其他会议和DNS时间段都不重叠。
面试官：如果会议之间没有间隔，调整后的区间会合并吗？
候选人：会的，如果两个时间段相邻或者存在重叠，我会将它们合并为一个连续的时间段。
面试官：很好，继续吧。
Dialogue and Follow-Up Questions
Interviewer:
What would you do if there are multiple overlapping meeting intervals? How would you handle them?
Candidate:
If multiple meetings overlap, I would adjust one interval at a time, ensuring that each adjusted interval does not overlap with other meetings or with the DNS period.
Interviewer:
What if there are no gaps between meetings? Would you merge the adjusted intervals?
Candidate:
Yes, if two intervals are adjacent or overlapping, I would merge them into one continuous interval.
Interviewer:
Good, continue.
面试二：多个DNS时间段
问题描述
面试官：现在我们假设你有多个DNS时间段，这些时间段可能会互相重叠。你需要设计一个算法来处理会议时间区间，确保它们不与任意一个DNS时间段重叠。同时，你还需要将重叠的DNS时间段合并为一个。
示例输入：
- 会议：[ (1, 7), (5, 10), (12, 30), (22, 30), (40, 50), (60, 70) ]
- DNS：[ (18, 25), (20, 28), (65, 75) ]
示例输出：
- 不重叠会议时间段：[ (1, 10), (12, 18), (28, 30), (40, 50), (60, 65) ]
- 合并后的DNS时间段：[ (18, 28), (65, 75) ]
Interview 2: Multiple DNS Periods
Problem Description
Interviewer:
Now, let's assume you have multiple DNS periods, and these periods may overlap with each other. You need to design an algorithm that adjusts the meeting intervals to ensure they do not overlap with any DNS period. Additionally, you must merge any overlapping DNS periods into one.
Example Input:
Meetings: [(1, 7), (5, 10), (12, 30), (22, 30), (40, 50), (60, 70)]
DNS: [(18, 25), (20, 28), (65, 75)]
Example Output:
Non-overlapping meeting intervals: [(1, 10), (12, 18), (28, 30), (40, 50), (60, 65)]
Merged DNS intervals: [(18, 28), (65, 75)]
澄清问题
候选人：多个DNS时间段可能会互相重叠，如果它们重叠，我们需要合并它们，对吧？
面试官：没错，重叠的DNS时间段需要合并为一个，之后的会议时间段必须根据合并后的DNS时间段进行调整。
候选人：那么会议时间段和DNS时间段都是有序的吗，还是我们需要手动排序？
面试官：你可以假设输入是无序的，因此你需要在算法中先进行排序。
Clarifying Questions
Candidate:
The DNS periods may overlap, and if they do, we need to merge them, correct?
Interviewer:
Exactly. Any overlapping DNS periods must be merged into one, and the meeting intervals must be adjusted based on the merged DNS periods.
Candidate:
Are the meeting intervals and DNS periods sorted, or do I need to sort them?
Interviewer:
You can assume that the input is unsorted, so you'll need to sort it within your algorithm.
解决思路
候选人：首先，我会对DNS时间段进行排序，并依次检查它们是否重叠。如果有重叠的时间段，我会将它们合并。然后，我会使用与前一道题类似的思路，遍历会议时间段，调整每个与合并后的DNS时间段重叠的会议。
面试官：合并后的DNS时间段列表可以有多个吗？
候选人：可以，有多个不重叠的DNS时间段时，每个会议时间段都要分别与这些时间段进行比较和调整。
Approach and Thought Process
Candidate:
First, I would sort the DNS periods and check for any overlaps. If there are overlapping periods, I would merge them. Then, I would apply a similar approach to the previous problem: iterate through the meeting intervals and adjust any that overlap with the merged DNS periods.
Interviewer:
Can there be multiple merged DNS intervals?
Candidate:
Yes, if there are multiple non-overlapping DNS periods, I would compare and adjust the meetings against each merged DNS interval.
对话与追问
面试官：你认为合并DNS时间段的时间复杂度是多少？
候选人：首先，我需要对DNS时间段进行排序，这部分的时间复杂度是O(m log m)，其中m是DNS时间段的数量。合并过程的时间复杂度是O(m)，因为我们只需要一次遍历即可完成合并。
面试官：那么处理会议时间段的时间复杂度呢？
候选人：处理会议时间段的时间复杂度是O(n)，其中n是会议的数量。每个会议时间段只需要被检查和调整一次。
面试官：不错，继续。
Dialogue and Follow-Up Questions
Interviewer:
What would be the time complexity of merging the DNS intervals?
Candidate:
First, I would need to sort the DNS periods, which would take O(m log m), where m is the number of DNS periods. Merging the periods is O(m) since we only need one traversal to complete the merge.
Interviewer:
And the time complexity for handling the meetings?
Candidate:
Handling the meetings would take O(n), where n is the number of meetings. Each meeting would only need to be checked and adjusted once.
Interviewer:
Good, proceed.
面试三：去除重复消息
问题描述
面试官：假设你有一个机器人会实时发送消息，由于短时间内有大量重复消息出现，因此需要你在10秒内去除重复消息，确保用户不会看到重复的内容。你能设计一个系统来实现这个功能吗？
Interview 3: Removing Duplicate Messages
Problem Description
Interviewer:
Imagine you have a robot that sends messages in real-time, but due to the large volume of messages in a short period, many messages are duplicates. You need to design a system that removes any duplicate messages within a 10-second window, ensuring the user doesn't see repeated content. Can you implement a solution for this?
澄清问题
候选人：这些消息会频繁发送，那么每一条消息都有唯一的ID吗？还是我们通过内容来判断是否重复？
面试官：消息内容相同的被视为重复，没有唯一ID。
候选人：那么消息的发送频率如何呢？我们应该怎样界定这10秒的窗口？
面试官：你可以假设消息的频率是随机的，但它们可能会在短时间内大量涌入。10秒的窗口是从消息出现的时间开始计算的。
Clarifying Questions
Candidate:
Are we working with messages that have unique IDs, or do we judge whether messages are duplicates based on their content?
Interviewer:
Messages are considered duplicates if they have the same content. There are no unique IDs.
Candidate:
How frequently are the messages sent? How do we define the 10-second window?
Interviewer:
You can assume the message frequency is random, but many messages may arrive in a short period. The 10-second window begins when a message is first seen.
解决思路
候选人：我会设计一个滑动窗口机制，用来跟踪过去10秒内已经发送的消息。每当有新消息到来时，我会检查它是否已经在滑动窗口中。如果存在，我会丢弃这条消息；否则，我会将它添加到窗口中并展示给用户。
面试官：这个滑动窗口是如何实现的呢？
候选人：我会使用一个队列来存储过去10秒内的消息，每当有新消息到来时，我会将它加入队列并移除队列中超过10秒的消息。这样可以保证窗口中只有最新的消息。
Approach and Thought Process
Candidate:
I would design a sliding window mechanism to keep track of messages that have been sent within the past 10 seconds. When a new message arrives, I would check whether it's already in the sliding window. If it is, I would discard it. If not, I would add it to the window and display it to the user.
Interviewer:
How would you implement this sliding window?
Candidate:
I would use a queue to store the messages received in the past 10 seconds. Each time a new message arrives, I would add it to the queue and remove any messages that are older than 10 seconds, ensuring that only recent messages are kept in the window.
对话与追问
面试官：如果消息频率非常高，队列可能会变得很大。你认为如何优化呢？
候选人：我们可以将队列的大小控制在一定范围内，比如只存储过去10秒内的有效消息。当新消息到来时，及时清理旧消息。同时，可以使用哈希表来快速查找消息内容，避免在队列中遍历查找。
面试官：很好，那么这个系统的时间复杂度和空间复杂度分别是多少？
候选人：时间复杂度是O(1)，因为每次操作都只涉及插入和删除。空间复杂度取决于过去10秒内的消息数量，假设有k条消息，空间复杂度就是O(k)。
面试官：很好，你的解答非常清晰。
Dialogue and Follow-Up Questions
Interviewer:
If messages arrive at a high frequency, the queue might become large. How would you optimize this?
Candidate:
To optimize the system, I would limit the size of the queue to only store messages from the past 10 seconds. Additionally, I could use a hash table to quickly look up message content, reducing the need to search the queue for duplicates.
Interviewer:
What is the time and space complexity of this system?
Candidate:
The time complexity is O(1) for both insertion and deletion, as we are only managing the most recent messages. The space complexity depends on the number of messages received in the past 10 seconds. If we assume there are k messages, the space complexity would be O(k).
Interviewer:
Excellent. Your explanation was very clear.
如果您需要面试辅助或面试代面服务，帮助您进入梦想中的大厂，请随时联系我。
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.
