P5 Sliding window · P6 Merge sorted streams
FreeLesson 59 of 78
P5Sliding windowDEDAMEDIUM
Sounds like: "rolling 3-day revenue", "moving average of latency", "max sum of k consecutive"
Worked question: A rolling 3-day revenue total over daily delivered revenue for 1 to 7 April (zeros already filled in).
Approach: 1. add the new value 2. subtract the one leaving 3. O(1) per step instead of re-summing k values
from collections import deque
daily = [("04-01", 0), ("04-02", 1999), ("04-03", 0), ("04-04", 0),
("04-05", 846), ("04-06", 0), ("04-07", 0)]
window, total = deque(), 0
for day, amt in daily:
window.append(amt)
total += amt
if len(window) > 3: # drop the day leaving the window
total -= window.popleft()
print(day, f"{amt:>5}", f"3-day: {total:>5}")Output
04-01 0 3-day: 0 04-02 1999 3-day: 1999 04-03 0 3-day: 1999 04-04 0 3-day: 1999 04-05 846 3-day: 846 04-06 0 3-day: 846 04-07 0 3-day: 846
P6Merge sorted streamsDEMEDIUM
Sounds like: "merge two sorted log files", "combine web and app events in time order"
Worked question: Merge web and app event streams, each already sorted by time, into one ordered stream. Then write the merge by hand.
Approach: 1. two pointers, one per input 2. take the smaller head 3. append whatever is left
import heapq
web = [("10:00", "u1 view"), ("10:20", "u1 checkout"),
("11:00", "u3 view")]
app = [("10:05", "u1 cart"), ("10:22", "u1 purchase")]
print([e for _, e in heapq.merge(web, app)]) # lazy, O(n)
def merge_two(a, b):
i = j = 0
out = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
out.append(a[i]); i += 1
else:
out.append(b[j]); j += 1
return out + a[i:] + b[j:] # one side has leftovers
print(merge_two([1, 4, 9], [2, 3, 10, 11]))Output
['u1 view', 'u1 cart', 'u1 checkout', 'u1 purchase', 'u3 view'] [1, 2, 3, 4, 9, 10, 11]
Follow-ups interviewers ask
| They ask | You answer |
|---|---|
| "Moving average, not sum." | Divide the running total by len(window). Same O(1) update. |
| "Max of the last k values." | A running total does not work for max. Use a deque of indices kept in decreasing order (monotonic queue): still O(n). |
| "Merge 200 sorted files." | heapq.merge on 200 open file iterators: memory holds one line per file, not the files. |
Practice before you move on
- Solve the two practice questions for P5 and P6 in Coding Practice, under Python.
- Change the window in P5 to two days and compare the output.
In Coding Practice
Solve this pattern on fresh data, under Python. Hidden tests grade it.