Transform sparse time-code stream to dense rows

Q: Transform sparse time-code stream to dense rows

This is a Coding & Algorithms interview question from Jane Street for Software Engineer 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 fixed set of M distinct codes (strings). The column order of the output matrix is the lexicographic order of these codes.
A stream of input batches . Each batch is a vector<tuple<int timestamp, string code, int value>> .

Conceptually, the ideal output is an N × M matrix where:

Each row corresponds to a timestamp (rows ordered by increasing timestamp).
Each column corresponds to a code (columns ordered lexicographically by code).
If a (timestamp, code) pair has no record, its cell value is -1 .

Input stream guarantee (base version)

Across the entire stream (or equivalently within each batch, with batches emitted in order), records are produced in non-decreasing timestamp order, and for the same timestamp, in lexicographic code order.

Task

Implement a stream transformer that consumes the above input stream and produces an output stream of:

pair<int timestamp, vector<int> row>

where:

timestamp is a timestamp present in the overall input (or in a given list of timestamps, if provided).
row has length M .
row[i] is the value for the i -th code (in lexicographic order) at that timestamp , or -1 if missing.

Your transformer should emit exactly one output row per timestamp (once all records for that timestamp have been consumed).

Follow-ups

Some batches have codes out of order (i.e., within a fixed timestamp, the codes are not guaranteed to be lexicographically sorted). How would you adapt the transformer?
A small fraction of records have timestamps out of order (i.e., the global timestamp ordering is slightly violated). How would you adapt the transformer while keeping memory bounded and latency reasonable?

Clarifications / assumptions you may choose (state them clearly)

Whether the list of all M codes is given up front, or must be discovered from the stream.
Whether multiple records for the same (timestamp, code) can appear (and if so, whether to take last-write-wins, sum, or treat as invalid).

Output example (illustrative)

If codes are ["A","B","C"] and the stream contains:

(1,"A",10), (1,"C",30)
(2,"B",20)

Then output rows:

(1, [10, -1, 30])
(2, [-1, 20, -1])