九月 Google SDE VO 两轮：数据流第 K 大 + 海量数据 Top K + 最长连续序列

面试概况

Google 的面试挑战性还是挺高的。整场流程节奏很快、不拖沓，全程非常考验 coding 基础和临场应变能力。

第一轮：BQ + Coding

BQ

1. Tell me about a time you disagreed with a teammate on a technical decision. How did you resolve it?
2. Describe a project where your initial plan failed. What did you learn and how did you pivot?
3. Tell me about a time you proactively improved an existing system or process. What impact did you make?

Coding：数据流中第 K 大的元素

实现一个类：构造函数传入 k 和初始数组 nums，add(val) 添加数值并返回当前第 K 大的元素。

思路：维护一个容量为 K 的最小堆，堆内保存最大的 K 个数字，堆顶就是第 K 大元素。初始化和 add 时元素入堆，超过 K 个就弹出堆顶。

import heapq

class KthLargest:
    def __init__(self, k, nums):
        self.k, self.heap = k, []
        for x in nums:
            self.add(x)

    def add(self, val):
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]

复杂度：初始化 O(n log K)，add O(log K)。

第二轮：纯 Coding

题 1：海量数据取距离最小的前 K 个 pair

思路：海量的 star_id + distance，N 很大、K 远小于 N，要选出距离最小的前 K 组。

• 直接排序是 O(N log N)，对全部数据建小顶堆也要 O(N log N)，海量数据下效率差。
• 维护一个大小为 K 的大顶堆：遍历数据，堆满后和堆顶比较，比堆顶小就替换，复杂度 O(N log K)。
• 同时聊了 K = 0、K > N、距离重复等边界。

import heapq

def k_closest_stars(stars, k):
    """stars: 可迭代的 (star_id, distance)，返回距离最小的 k 个，按距离升序"""
    if k <= 0:
        return []
    heap = []                          # 大顶堆：存 (-distance, star_id)
    for sid, dist in stars:
        if len(heap) < k:
            heapq.heappush(heap, (-dist, sid))
        elif dist < -heap[0][0]:
            heapq.heapreplace(heap, (-dist, sid))
    return [(sid, -nd) for nd, sid in sorted(heap, reverse=True)]

题 2：最长连续数字序列

题目：无重复数组，求最长连续序列的长度。例如 [100,4,200,1,3,2] 输出 4。

思路：所有数字存入哈希集合。遇到 num - 1 不存在的数字，说明它是一个序列的起点，从它往后统计连续长度并更新最大值，整体 O(n)。同时讨论了空数组、单元素等边界，用例全部通过。

def longest_consecutive(nums):
    s, best = set(nums), 0
    for x in s:
        if x - 1 not in s:             # 序列起点
            y = x
            while y + 1 in s:
                y += 1
            best = max(best, y - x + 1)
    return best