Google Intern VO 两轮复盘：Meeting Rooms II + BST 转循环双向链表

面试概况

两轮 Google Intern VO，整体来说不难，顺利收尾。

第一轮：Meeting Rooms II

面试官是个很 Nice 的白人大哥，开场先聊了 10 分钟简历，然后直接上题。

题目：给定一系列会议的 Start 和 End 时间，问最少需要多少个会议室才能安排下所有会议？

思路：经典「合并区间」变种，也是高频题。

1. 把所有会议按开始时间排序。
2. 维护一个 Min-Heap（小顶堆），堆里存每个会议室的结束时间。
3. 遍历会议：如果当前会议的 start >= 堆顶的 end，说明可以复用那个会议室，弹出堆顶并压入新的 end；否则直接压入新的 end。
4. 最后堆的大小就是答案。

import heapq

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    for start, end in intervals:
        if heap and start >= heap[0]:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

时间复杂度 O(n log n)，空间复杂度 O(n)。

第二轮：BQ + BST 转循环双向链表

这一轮节奏比较快，面试官是印度裔，口音有点重、语速很快，需要集中注意力听，但没有刻意刁难。

BQ

• Mistake：讲一次你犯错的经历，你是怎么补救的？
• Leadership：描述一次你主动承担责任、带领团队完成任务的经历。

Coding：二叉搜索树转有序循环双向链表

题目：将一个 BST 转化成一个排序的循环双向链表。要求原地修改指针，不能创建新节点。

思路：核心是中序遍历。递归维护一个 prev 指针，指向中序遍历的前一个节点：

• 访问当前节点时，prev.right = cur，cur.left = prev。
• 记录第一个访问到的节点作为 head。
• 遍历结束后把首尾相连成环。

def tree_to_doubly_list(root):
    if not root:
        return None
    head = prev = None

    def inorder(node):
        nonlocal head, prev
        if not node:
            return
        inorder(node.left)
        if prev:
            prev.right, node.left = node, prev
        else:
            head = node
        prev = node
        inorder(node.right)

    inorder(root)
    head.left, prev.right = prev, head
    return head

时间复杂度 O(n)，空间复杂度 O(h)（递归栈）。