Google Interview: YouTube View Statistics (Prefix Sums) + Newly Painted Area per Day

Round 1: YouTube view statistics (prefix sums)

Problem

YouTube's backend tracks video views. Given an array views where each element is the number of new views a short video got in that minute:

1. There will be many queries, each with a time range [L, R]; quickly return the total views in that range.
2. The platform wants hot-spot detection: a contiguous window whose total views exceed a threshold T is a hot period. Count how many contiguous windows have a total greater than T.

Clarify first

• Are all view counts non-negative? (New views per minute can't be below 0.)
• Input edge cases: an empty array, a tiny threshold where every window qualifies, a huge threshold where none do.

Approach

• Range queries: build a prefix sum array so a range sum becomes a difference of prefix sums — O(1) per query.
• Counting hot windows: enumerating every window is O(n²), which is slow.
• When every element is >= 0, prefix sums are non-decreasing, so two pointers or binary search bring it down to O(n) or O(n log n).

The two-pointer version below counts windows with sum <= T, then subtracts from the total number of windows:

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:   # non-negative array: shorter window, smaller sum
            s -= views[left]
            left += 1
        not_hot += right - left + 1   # windows ending at right with sum <= t
    return n * (n + 1) // 2 - not_hot

Time O(n), space O(1).

Follow-ups

• If view counts can be negative (e.g. rollbacks or corrections), prefix sums are no longer monotonic — can you still use binary search? What's the best approach then?
• With a massive number of queries, serving many users' hot-spot requests in real time, how would you optimize at the system level?
• If the data is too large for memory and you can only stream each minute's views one by one, how do you compute the result?

Reference ideas: with negatives the problem becomes counting index pairs (i, j) with P[j] - P[i] > T, solvable with merge-sort counting or a Fenwick tree (BIT) over coordinate-compressed prefix sums, in O(n log n). For massive query volume, precompute prefix sums for O(1) answers, then shard by video ID and add caching.

Round 2: Newly painted area per day

Problem

Each day you paint an interval; return how much new area was actually painted each day — areas already painted earlier don't count again.

Clarify first

Are endpoints closed or half-open? That decides whether touching intervals merge, and affects the length formula.

Approach

• Process intervals day by day, keeping the covered area as non-overlapping intervals in a sorted set.
• When inserting a new interval, find the existing intervals that overlap or touch it: subtract their lengths from the total, merge everything into one interval, and add its length back.
• The day's new area = total after the update − total before.

Implemented below with half-open intervals [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)   # first existing interval with 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

After writing it, verify with three cases: full containment, partial overlap, and spanning multiple existing intervals.

Follow-up on very large inputs: discuss coordinate compression + a segment tree, or an offline sweep line.

Tips from A-ge

• Google coding interviews aren't just about working code — confirm the problem and constraints with the interviewer first.
• After the basic solution, analyze time and space complexity proactively and run several test cases to validate the logic.
• Follow-ups are what separate candidates. Think about variations like massive data, limited memory and undo operations. When practicing, add constraints yourself to simulate interviewer follow-ups.