Densify a Sparse Timestamp Stream
Asked at Jane Street· Screen
Jane StreetReported by the problem's creator, not verified
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 [].
Examples
Example 1
Input: codes =
["b","a","c"], batches =[[[1,"a",5],[1,"c",7],[2,"b",9]],[[2,"c",4],[4,"a",1]],[]], max_lag =0Output:
[[[1,[5,-1,7]]],[[2,[-1,9,4]]],[],[[4,[1,-1,-1]]]]Explanation: Columns follow
codessorted: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[].