Merge Sorted Lists to Length | Dataford Interview Questions

HubSpot may need to combine two already sorted HubSpot CRM activity streams and display only the earliest k activities. Given two ascending arrays, return the first k values from their sorted merge without sorting the full combined array.

Formal Specification

Implement merge_until_k(list1, list2, k).

list1 and list2 are arrays of integers sorted in nondecreasing order.
k is a nonnegative integer.
Return an array containing at most k values from the merged sorted sequence.
If fewer than k values exist, return every available value.
Preserve duplicates. The input arrays must not be modified.

Constraints

0 <= len(list1), len(list2) <= 10^5
0 <= k <= 10^5
-10^9 <= list1[i], list2[j] <= 10^9
The total input size is at most 2 * 10^5
Both input arrays are sorted in nondecreasing order

Function Signature

def merge_until_k(list1, list2, k):

Your question is Merge Sorted Lists to Length. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem