Densify a Sparse Timestamp Stream

Jane StreetPhone screenMedium

A feed delivers measurements as records [timestamp, code, value]: timestamp is an integer, code is a string, and value is a non-negative integer. codes lists the M distinct codes that can occur.

Implement densify(codes, batches, max_lag). batches is a list of batches, each a list of records, delivered in order. Turn the stream into dense rows: one row per timestamp that appears in any record, written [timestamp, values], where values has one entry per code in lexicographic order and holds -1 for a code with no record at that timestamp.

Return a list with one entry per batch, in order, followed by one extra entry for the end of the stream. Each entry lists the rows that become final after that batch, in increasing timestamp order. A row is final after a batch when its timestamp is below top - max_lag, where top is the largest timestamp seen in this and all earlier batches. The final entry holds every remaining row in increasing timestamp order. A batch that finalizes nothing contributes [].

Part 1: Sorted stream

In this part max_lag is 0. Timestamps never decrease across the whole stream, and within one timestamp the records appear in lexicographic order of code, each (timestamp, code) pair at most once. A timestamp may continue from one batch into the next, so a row is final only after a larger timestamp has been seen.

Example 1
codes
["b","a","c"]
batches
[[[1,"a",5],[1,"c",7],[2,"b",9]],[[2,"c",4],[4,"a",1]],[]]
max_lag
0
Output
[[[1,[5,-1,7]]],[[2,[-1,9,4]]],[],[[4,[1,-1,-1]]]]
Why: Columns follow codes sorted: a, b, c. Timestamp 1 becomes final once the first batch reveals timestamp 2, so the first entry emits [1, [5, -1, 7]]. Timestamp 2 continues into the second batch and is emitted there once timestamp 4 appears. Timestamp 4 waits for the final flush; the empty third batch contributes [].

Constraints

1 <= len(codes) <= 100
0 <= len(batches) <= 10^3
at most 10^4 records in total across batches
0 <= timestamp <= 10^9 for every record
0 <= value <= 10^9 for every record
max_lag = 0