C++ K-Way Merge of Timestamped Records with Clean Class Design and Hand-Written Tests

This C++ coding round was a variant of the classic task of merging k sorted linked lists into one sorted list. In the variant, every element carries a timestamp plus other data, and each input is sorted by timestamp. The exact change the variant made beyond the extra data was not described, so this statement gives the base form. Write a C++ component that takes k input sequences of records, each sorted by non-decreasing timestamp, and produces every record in a single sequence sorted by timestamp. The round rewarded getting the representation right as much as the merge itself: define the record type, decide what state a merging class keeps and how its interface is organized, and write your own test cases in C++ instead of relying on a judge's harness. ```text Each record: (timestamp, tag, value) input 0: (1, "a", 0.5) (4, "a", 0.7) (9, "a", 0.2) input 1: (2, "b", 3.1) (4, "b", 2.9) input 2: (empty) input 3: (3, "c", 7.4) merged, ties broken by input index: (1, "a") (2, "b") (3, "c") (4, "a") (4, "b") (9, "a") ``` ### Constraints and Clarifications - Language: C++ (assume C++17). - Not given: what the extra data is, how the inputs are delivered, how equal timestamps are ordered, and how large the inputs are. Ask, or state your assumptions; the example breaks ties by input index only for illustration. ### Clarifying Questions - Are the inputs in-memory containers, linked lists of nodes, or streams that produce records over time and may not fit in memory? - How should records with equal timestamps be ordered: by input index, by some payload field, or in any order? - What are the timestamp type and resolution, and is the payload large enough that copying it matters? - Should the result be one merged container, or an iterator-style interface that hands out the next record on demand? - Can an input be out of order, and if so, should the component detect it? ### Part 1 — Record type and class design Define the record type and the merging class: what it accepts, what it returns, what state it keeps between calls, and who owns the data. ```hint Ordered by versus carried along Decide what the merge needs to compare and what it merely moves, and what that means for the comparator and for copying. ``` #### What This Part Should Cover - A record struct with an explicit timestamp type and a payload, and an ordering that depends only on the timestamp plus a stated tie rule - An interface, a whole-result call and/or `hasNext()` and `next()`, with ownership and lifetimes stated - The class's internal state and the invariant it maintains ### Part 2 — The merge Implement the merge for k inputs holding N records in total, and state its time and space complexity. ```hint Who can come next At any moment, ask which records could possibly be the next one in the output, and how to find the smallest of them quickly. ``` #### What This Part Should Cover - A correct k-way merge, with complexity in terms of N and k - Correct use of the standard library: heap ordering direction, the comparator, and moving rather than copying records - Empty inputs, k = 0, equal timestamps, and a deterministic output order ### Part 3 — Hand-written tests in C++ Without a judge harness, write C++ test cases that build inputs, run the merger, and check its output. ```hint What would convince you List the properties every correct output has, then the inputs most likely to break your code. ``` #### What This Part Should Cover - A small self-contained test program that compiles, runs and fails loudly - Edge cases: no inputs, only empty inputs, a single input, all-equal timestamps, very unbalanced input sizes - A check against a simple reference implementation, including tie order ### What a Strong Answer Covers - Clarifies the input representation, the tie rule and the payload size before coding - A clear record type and class interface whose state and ownership are explicit - An O(N log k) merge with the heap ordered the right way and no needless payload copies - Self-written C++ tests that cover edge cases and compare against a reference - Idiomatic modern C++: const-correctness, move semantics, no dangling references or invalidated iterators ### Follow-up Questions - The inputs are now live streams that deliver records over time. How does the interface change, and when is it safe to emit a record? - One input is far larger than all the others combined. Does that change your algorithm? - k is in the thousands and the merger sits on a hot path. What would you optimize first? - How would you make the merger generic over the record type?