Count super-streak segments in an event stream

Q: Count super-streak segments in an event stream

This is a Coding & Algorithms interview question from Google for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

You are given a time-ordered sequence of events. Each event has:

type (string or int)
ts (timestamp as integer milliseconds/seconds)

A streak segment is a maximal contiguous subsequence of the input where:

All events have the same type , and
For every pair of adjacent events in the segment, the time gap is within a threshold:
$ts[i] - ts[i-1] \le T$ .

A streak segment is a super streak if it satisfies all of the following:

Count condition: number of events in the segment $\ge N$
Gap condition: already enforced by the segment definition (all adjacent gaps $\le T$ )
Duration condition: total duration of the segment $= ts[last] - ts[first] \ge X$ $= t s [l a s t] - t s [f i rs t] \geq X$
- Note: a segment with a single event has duration 0.

Task

Implement a function that returns the number of super streak segments in the sequence.

Assumptions / clarifications

Input events are sorted by ts ascending.
T , N , and X are given as non-negative values.
Use inclusive gap threshold: a gap exactly equal to T is allowed.

Example (informal)

If a segment has 5 events of the same type, all adjacent gaps $\le T$ , and spans from time 10 to 25, then it is a super streak iff $5 \ge N$ and $25-10 \ge X$ .

Follow-up

How would you adapt your solution if parameters N, T, and/or X can change over time (e.g., different thresholds apply to different portions of the event sequence)?