Identify Longest Consecutive Incrementing Watch-Time Sequence
Company: Netflix
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Scenario
A streaming platform records daily minutes watched per user and wants to identify engagement streaks.
##### Question
Given an unsorted integer array representing daily watch-time deltas, return the length of the longest sequence of consecutive, incrementing integers (e.g., 1,2,3…). Explain the algorithm and analyze complexity.
##### Hints
Think hash-set to achieve O(n) time and avoid re-scanning sequences.
Quick Answer: This question evaluates a candidate's ability to design and analyze efficient algorithms for detecting longest consecutive incrementing sequences in unsorted integer arrays, testing understanding of appropriate data structures and time/space complexity trade-offs.
Given an unsorted integer array deltas representing daily watch-time changes, return the length of the longest sequence of values that are consecutive and strictly increment by 1 (k, k+1, k+2, ...). The sequence is formed from values only; indices and original order do not matter. Duplicates do not extend a sequence. If the array is empty, return 0.
Constraints
- 0 <= len(deltas) <= 200000
- -10^9 <= deltas[i] <= 10^9
- Duplicates may appear and should be treated as a single value for sequence building
- Expected average time: O(n) using hashing
- Auxiliary space: O(n)
Solution
def longest_incrementing_streak(deltas: list[int]) -> int:
if not deltas:
return 0
values = set(deltas)
def longest_run(s: set) -> int:
best = 0
for x in s:
if x - 1 not in s:
y = x
length = 1
while y + 1 in s:
y += 1
length += 1
if length > best:
best = length
return best
if 0 in values:
t = 0
while (-t - 1) in values and (t + 1) in values:
t += 1
l_sym = 1 + 2 * t
pos = {x for x in values if x > 0}
l_pos = longest_run(pos) if pos else 0
return l_sym if l_sym >= l_pos else l_pos
else:
return longest_run(values)
Explanation
Use a hash set of all values for O(1) average membership checks. For each number x, only attempt to grow a sequence if x-1 is not present; this ensures each sequence is counted exactly once. From such a start, repeatedly check x+1, x+2, ... to find the sequence length. Duplicates are ignored by the set. The maximum length across all starts is the answer.
Time complexity: O(n) average-case. Space complexity: O(n).
Hints
- Insert all numbers into a hash set for O(1) average lookups.
- Only start counting from numbers x where x-1 is not in the set (start of a run).
- From each start, incrementally check x+1, x+2, ... to count the run length.
- Duplicates are naturally handled by the set and do not extend runs.