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.

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.

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.

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.

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