Google 面经：YouTube 播放统计（前缀和）+ 每日新增涂色面积

Round 1：YouTube 视频播放统计（前缀和）

题目

YouTube 后台统计用户的视频播放数据。给定一个数组 views，每个元素代表该短视频每一分钟获得的新增播放量。

会收到多组查询，每组查询给出时间区间 [L, R]，需要快速返回该区间内的总播放量。
平台要做热点检测：如果某个连续时间窗口内的播放总和大于阈值 T，就判定为热点时段。请计算一共有多少个连续子窗口的播放总和大于 T。

先 Clarify

播放量是否全部非负？（每分钟新增播放不会小于 0）
输入边界：空数组、阈值很小导致全部窗口命中、阈值极大导致没有窗口命中。

解题思路

区间查询：构建前缀和数组，把区间求和转化为前缀和之差，每次查询 O(1)。
热点窗口计数：朴素做法枚举全部子窗口是 O(n²)，效率很低。
当所有元素 >= 0 时，前缀和单调递增，可以用双指针或二分加速，把复杂度降到 O(n) 或 O(n log n)。

下面的双指针写法先统计「和 <= T」的窗口数，再用总窗口数减掉：

def range_sum(prefix, l, r):
    """prefix[i] = views[0] + ... + views[i-1]"""
    return prefix[r + 1] - prefix[l]

def count_hot_windows(views, t):
    n, left, s, not_hot = len(views), 0, 0, 0
    for right, v in enumerate(views):
        s += v
        while s > t and left <= right:   # 非负数组：窗口越短和越小
            s -= views[left]
            left += 1
        not_hot += right - left + 1   # 以 right 结尾、和 <= t 的窗口数
    return n * (n + 1) // 2 - not_hot

时间 O(n)，空间 O(1)。

Follow-up

如果播放量允许出现负数（比如播放回退、统计修正），前缀和不再单调，还能不能用二分？此时最优解法是什么？
如果查询数量非常巨大，需要在线实时处理大量用户的热点请求，如何做系统层面的优化？
如果数据量超大无法全部放入内存，只能流式逐个读取每分钟的 views，怎么统计结果？

参考思路：有负数时问题变成统计满足 P[j] - P[i] > T 的下标对 (i, j)，可以用归并排序计数，或者对前缀和做坐标压缩后用树状数组（BIT），时间 O(n log n)。海量查询时预先计算前缀和，O(1) 回答，再按视频 ID 分片并加缓存。

Round 2：每日新增涂色面积

题目

给出每天涂上的一段区间，返回每一天真正新增的面积；之前已经涂过的部分不能重复计数。

先 Clarify

端点是闭区间还是半开区间？这个定义会影响「相邻」区间是否合并，也会影响长度公式。

解题思路

按天处理区间，用有序集合维护已覆盖的、互不重叠的区间。
插入新区间时，找到与它相交或相邻的旧区间：先从总面积中减掉这些旧区间的长度，再合并成一个新区间并加回它的长度。
当天新增面积 = 更新后的总面积 − 更新前的总面积。

下面按半开区间 [start, end) 实现：

from bisect import bisect_left

def daily_new_area(days):
    starts, ends, total, result = [], [], 0, []
    for s, e in days:
        if e <= s:
            result.append(0)
            continue
        before = total
        i = j = bisect_left(ends, s)   # 第一个 end >= s 的旧区间
        while j < len(starts) and starts[j] <= e:
            s, e = min(s, starts[j]), max(e, ends[j])
            total -= ends[j] - starts[j]
            j += 1
        starts[i:j], ends[i:j] = [s], [e]
        total += e - s
        result.append(total - before)
    return result

写完后用三组数据验证：完全覆盖、局部重叠、跨多个旧区间。

追问大规模输入：可以讨论坐标压缩 + 线段树，或者离线扫描线。

A 哥提醒

Google 的 coding 面试不只是写出能跑的代码，一定要先和面试官确认清楚题意与约束条件。
做完基础解法后，主动分析时间和空间复杂度，多跑几组测试 case 验证逻辑。
Follow-up 是拉开差距的关键，多想想海量数据、内存受限、撤销操作这类变化场景。平时练习时，记得主动给自己追加约束，模拟面试官的追问。