FastPrepCount Hotspot Playback Windows

Count Hotspot Playback Windows

Google logoGoogle● MediumINTERNONSITE INTERVIEW
Learn

Problem statement

You are given an integer array views, where views[i] is the number of new video playbacks recorded during minute i, and an integer threshold.

Return the number of nonempty contiguous time windows whose total playback count is strictly greater than threshold.

Playback counts are nonnegative. Return the exact number of qualifying windows as a long value.

Interview extensions

  • Explain how prefix sums answer many inclusive interval-total queries [left, right] over the same playback array.
  • If playback corrections may be negative, explain why the monotone sliding-window argument no longer works and how to count qualifying windows in O(n log n) time.
  • Discuss how to serve a very large volume of online interval queries.
  • For nonnegative playback counts, explain how to process the values as a stream without storing the entire array.

Function

countHotspotWindows(views: int[], threshold: long) → long

Examples

Example 1

views = [2,1,3]threshold = 3return = 2

The qualifying windows are [1,3] with total 4 and [2,1,3] with total 6. Windows totaling exactly 3 do not qualify.

Example 2

views = [0,0]threshold = -1return = 3

All three nonempty windows have total 0, which is strictly greater than -1.

Example 3

views = [5,0,1]threshold = 4return = 3

The three qualifying windows are [5], [5,0], and [5,0,1].

Example 4

views = []threshold = 10return = 0

An empty playback history contains no nonempty time window.

Constraints

  • 0 <= views.length <= 200000
  • 0 <= views[i] <= 10^9
  • -10^18 <= threshold <= 10^18
  • The answer fits in a signed 64-bit integer.

More Google problems

See Google hiring insights
public long countHotspotWindows(int[] views, long threshold) {
  // Write your code here.
}
views[2,1,3]
threshold3
expected2
Checking account…