How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Merge K timestamped lists with timestamp coalescing

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given **k** sorted lists (or linked lists) of records. Each record has: - `timestamp` (integer) - `values` (an array of integers sorted in non-decreasing order) Each individual list is sorted by `timestamp` in non-decreasing order. Your task is to merge the k lists into **one** sorted list by `timestamp`, with the following special rule: - If multiple input records (possibly from different lists) have the **same `timestamp`**, you must **coalesce** them into a **single output record** with that timestamp. - The `values` array of the coalesced record is the **sorted merge** of all `values` arrays from records with that timestamp. Return the merged list of records sorted by `timestamp`. ### Input - `lists`: an array of length `k`, where each element is a list of records `(timestamp, values)` sorted by `timestamp`. ### Output - A single list of records `(timestamp, values)` sorted by `timestamp`, where each timestamp appears at most once. ### Constraints (you may assume) - `0 <= k <= 10^4` - Total number of records across all lists: `N` (up to ~10^5) - Total number of integers across all `values` arrays: `M` (up to ~10^5) - Timestamps fit in 32-bit signed integer. ### Example Input: - L1: `(1,[1,4]) -> (3,[2])` - L2: `(1,[0,5]) -> (2,[7])` - L3: `(3,[3,3])` Output: - `(1,[0,1,4,5]) -> (2,[7]) -> (3,[2,3,3])` (Notice timestamps `1` and `3` are merged first across lists, and their `values` arrays are merged into one sorted array.)

Quick Answer: This question evaluates algorithmic skills in merging multiple sorted sequences, coalescing records by key (timestamp), merging sorted value arrays, and analyzing time and space complexity.

You are given k lists of records. Each record is represented as a tuple (timestamp, values), where timestamp is an integer and values is a list of integers sorted in non-decreasing order. Each individual input list is sorted by timestamp in non-decreasing order. Merge all k lists into one output list sorted by timestamp. If multiple records have the same timestamp, you must coalesce them into a single output record for that timestamp. The output record's values list must be the sorted merge of all values lists belonging to that timestamp. A timestamp may appear in different lists and may also repeat within the same list. The final output must contain each timestamp at most once.

Constraints

0 <= k <= 10^4
Let N be the total number of records across all lists; N <= 10^5
Let M be the total number of integers across all values arrays; M <= 10^5
Each input list is sorted by timestamp in non-decreasing order
Each values array is sorted in non-decreasing order
Timestamps fit in 32-bit signed integer

Examples

Input: ([[(1, [1, 4]), (3, [2])], [(1, [0, 5]), (2, [7])], [(3, [3, 3])]],)

Expected Output: [(1, [0, 1, 4, 5]), (2, [7]), (3, [2, 3, 3])]

Explanation: Timestamp 1 combines records from the first and second lists. Timestamp 3 combines records from the first and third lists.

Input: ([],)

Expected Output: []

Explanation: There are no input lists, so the merged result is empty.

Input: ([[(-2, [-5, 0]), (1, [2]), (1, [3, 3])], [(-2, [-4]), (0, []), (1, [1, 4])], [(-1, [7])]],)

Expected Output: [(-2, [-5, -4, 0]), (-1, [7]), (0, []), (1, [1, 2, 3, 3, 4])]

Explanation: This checks negative timestamps, an empty values array, and repeated timestamp 1 within the same list.

Input: ([[(5, [1, 1])], [], [(5, [0, 2]), (6, [3])], [(5, [])]],)

Expected Output: [(5, [0, 1, 1, 2]), (6, [3])]

Explanation: All records with timestamp 5 are coalesced, including one with an empty values array. Timestamp 6 remains separate.

Hints

Use a min-heap to keep track of the next smallest timestamp among the current heads of the k lists.
When you find the smallest timestamp t, keep removing heap entries with timestamp t and merge all of their sorted values arrays into one sorted array.

Quick Overview

This question evaluates algorithmic skills in merging multiple sorted sequences, coalescing records by key (timestamp), merging sorted value arrays, and analyzing time and space complexity.