Checkpoint: midpoint mock round
Round two
A merge warm-up, then a streaming statistic. 45 minutes.
Take a real break before this round. Two problems, 45 minutes, same rules. Both lean on Unit 9, and one of them has a much better answer than the first one you will think of.
Warm-up: Flatten a Sorted Matrix
Each row is sorted and each column is sorted. Produce every value in one sorted sequence. Concatenating and sorting works; say what that costs before you decide whether to do it.
Loading the workspace…
Main: Running Medians
Report the median after every value arrives. Re-sorting on each arrival is the obvious approach; work out its total cost across the whole stream before you write it, then decide whether that is acceptable.
Loading the workspace…