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.

What difficulty level is this interview 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

Q: Merge K timestamped lists with timestamp coalescing

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 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.)

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.)

Merge K timestamped lists with timestamp coalescing

Quick Overview

Input

Output

Constraints (you may assume)

Example

Comments (0)

Merge K timestamped lists with timestamp coalescing

Quick Overview

Input

Output

Constraints (you may assume)

Example

Comments (0)