Bird
Raised Fist0
Interview Prepin-place-linked-listhardAmazonFacebookGoogleMicrosoftBloomberg

Merge K Sorted Lists

Choose your preparation mode4 modes available
Try ItSolutionTrace
</>
IDE
def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:public ListNode mergeKLists(ListNode[] lists)ListNode* mergeKLists(vector<ListNode*>& lists)function mergeKLists(lists)
def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    # Write your solution here
    pass
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // Write your solution here
        return null;
    }
}
#include <vector>
using namespace std;

ListNode* mergeKLists(vector<ListNode*>& lists) {
    // Write your solution here
    return nullptr;
}
function mergeKLists(lists) {
    // Write your solution here
}
Coming soon
0/10
Common Bugs to Avoid
Wrong: Missing nodes or incomplete merged listNot processing all lists or stopping early when merging✅ Ensure all lists are pushed into the min-heap and all nodes are processed until heap is empty
Wrong: Output list missing duplicates or merged incorrectlySkipping nodes with equal values or merging duplicates incorrectly✅ Do not skip nodes with equal values; always push next nodes into the heap regardless of duplicates
Wrong: Crashes or returns non-null for empty inputNo check for empty input array or all empty lists✅ Add guard clauses to return null if input array is empty or all lists are empty
Wrong: Time limit exceeded (TLE)Using brute force sorting or repeated pairwise merges with O(kN) or O(N log N) complexity✅ Use a min-heap or divide and conquer merge to achieve O(N log k) time complexity
Wrong: Incorrect order due to greedy mergesMerging lists one by one greedily without balancing or heap✅ Use divide and conquer or min-heap to merge all lists efficiently and correctly
✓
Test Cases
t1_01basic
Input{"lists":[[1,4,5],[1,3,4],[2,6]]}
Expected"1->1->2->3->4->4->5->6"

Merging the three sorted lists results in one sorted list: 1->1->2->3->4->4->5->6

t1_02basic
Input{"lists":[[2,5,7],[3,11],[1,6,8,9]]}
Expected"1->2->3->5->6->7->8->9->11"

Merging three sorted lists results in 1->2->3->5->6->7->8->9->11

t2_01edge
Input{"lists":[]}
Expected""

Empty list array input should return an empty list (null).

t2_02edge
Input{"lists":[[],[],[]]}
Expected""

All lists empty should return an empty list (null).

t2_03edge
Input{"lists":[[5],[1],[3]]}
Expected"1->3->5"

Lists with one element each should merge correctly into a sorted list.

t2_04edge
Input{"lists":[[-10],[0],[10]]}
Expected"-10->0->10"

Lists with negative and positive single elements merge correctly.

t3_01corner
Input{"lists":[[1,4,5],[1,3,4],[2,6],[1,1,1]]}
Expected"1->1->1->1->2->3->4->4->5->6"

Merging lists with duplicates should maintain all duplicates in sorted order.

t3_02corner
Input{"lists":[[1,3,5],[2,4,6],[7,8,9]]}
Expected"1->2->3->4->5->6->7->8->9"

Greedy approach that merges only first two lists repeatedly fails; correct approach merges all lists properly.

t3_03corner
Input{"lists":[[1,2,3],[1,2,3],[1,2,3]]}
Expected"1->1->1->2->2->2->3->3->3"

Confusing 0/1 vs unbounded merges: each node must be used exactly once, no duplicates added or missed.

t4_01performance
Input{"lists":[[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499]]}
⏱ Performance - must finish in 2000ms

Merging 1 list with 500 nodes tests handling large input; must complete in 2s with O(N log k) or better.

Practice

(1/5)
1. You are given two sorted arrays and need to find the k pairs with the smallest sums formed by taking one element from each array. Which approach guarantees an optimal solution with efficient time complexity?
easy
A. Use dynamic programming to build a table of sums and select the smallest pairs from it.
B. Use a brute force approach by enumerating all pairs, then sorting them to find the smallest sums.
C. Use a min-heap to lazily generate pairs starting from the smallest possible sums, expanding only as needed.
D. Use a greedy approach by always pairing the smallest elements from each array without backtracking.

Solution

  1. Step 1: Understand problem constraints

    The problem requires finding the k smallest pairs by sum from two sorted arrays efficiently.

  2. Step 2: Evaluate approaches

    Brute force enumerates all pairs, which is inefficient. DP is not suitable since pairs are not independent subproblems. Greedy fails because pairing smallest elements once misses other smaller sums. The min-heap approach lazily expands pairs starting from the smallest sums, ensuring optimality and efficiency.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Min-heap approach matches the known optimal solution [OK]
Hint: Min-heap lazily expands pairs for optimal efficiency [OK]
Common Mistakes:
  • Assuming greedy pairing always works
  • Thinking DP applies directly
  • Believing brute force is efficient enough
2. The following code attempts to assign jobs to machines optimally. Which line contains a subtle bug that can cause incorrect scheduling?
medium
A. Line 5: Using enumerate without sorting jobs by start time.
B. Line 9: heapq.heapify(available) to initialize available machines heap.
C. Line 13: While loop condition to free machines before assignment.
D. Line 17: Calculating finish_time as start + duration.

Solution

  1. Step 1: Identify the bug

    The code uses indexed_jobs = enumerate(jobs) without sorting jobs by start time, which breaks chronological processing.

  2. Step 2: Consequences of missing sorting

    Without sorting, jobs may be assigned out of order, causing machines to be assigned incorrectly or appear busy when they should be free.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Sorting jobs by start time is essential for correct scheduling [OK]
Hint: Jobs must be sorted by start time before assignment [OK]
Common Mistakes:
  • Forgetting to sort jobs by start time
  • Not freeing machines before assigning new jobs
  • Incorrect finish time calculation
3. The following code attempts to find the smallest range covering k sorted lists using a min-heap. Identify the line containing the subtle bug that can cause incorrect results or runtime errors.
medium
A. Line popping the smallest element from the heap
B. Line checking if ele_idx + 1 == len(nums[list_idx]) to break the loop
C. Line updating current_max after pushing next_val into the heap
D. Line initializing min_range to float('inf')

Solution

  1. Step 1: Identify the role of current_max

    current_max tracks the maximum element in the current window; it must be updated when pushing a new element.

  2. Step 2: Locate missing update

    The code comment indicates current_max is not updated after pushing next_val, causing incorrect range calculation.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Without updating current_max, range may be underestimated or incorrect [OK]
Hint: Always update current_max after pushing new heap element [OK]
Common Mistakes:
  • Forgetting to update current_max after pushing new element
  • Breaking loop too early or too late
  • Misusing heap pop or initialization
4. What is the time complexity of the min-heap based algorithm to find the nth ugly number, and why?
medium
A. O(n^2) because each number can generate up to 3 new numbers and heap operations are costly.
B. O(n) because each number is processed only once and heap operations are constant time on average.
C. O(n log n) because each of the n ugly numbers is pushed and popped from the heap once, and heap operations take O(log n).
D. O(n log k) where k=3 because the heap size is limited to 3 elements at any time.

Solution

  1. Step 1: Analyze heap operations per ugly number

    Each ugly number is popped once and up to 3 new numbers are pushed. The heap size can grow up to O(n) in worst case.

  2. Step 2: Calculate total complexity

    Each push/pop operation costs O(log n), and there are O(n) such operations, so total time is O(n log n).

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Heap operations dominate with O(log n) per operation [OK]
Hint: Heap operations cost O(log n), not constant [OK]
Common Mistakes:
  • Assuming heap size is constant
  • Confusing n with k in complexity
  • Ignoring log factor in heap operations
5. Suppose jobs can be reused multiple times (i.e., the same job can be assigned repeatedly), and you want to assign jobs to machines minimizing start delays as before. Which modification to the optimal algorithm is necessary to handle this scenario correctly?
hard
A. No change needed; the existing algorithm handles reuse naturally by sorting jobs once and assigning sequentially.
B. Sort jobs by duration instead of start time to prioritize shorter jobs for reuse.
C. Use a brute force approach checking all possible assignments since reuse breaks heap assumptions.
D. Maintain a priority queue of job instances and re-insert jobs after completion to simulate reuse, updating start times accordingly.

Solution

  1. Step 1: Understand job reuse impact

    Reusing jobs means after a job finishes, it can be assigned again, so jobs are not fixed once but can appear multiple times.

  2. Step 2: Modify algorithm to handle reuse

    Maintain a priority queue of job instances with their next available start times. After a job finishes, re-insert it with updated start time to simulate reuse.

  3. Step 3: Why other options fail

    No change ignores reuse; brute force is inefficient; sorting by duration ignores start times and scheduling constraints.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Re-inserting jobs after completion models reuse correctly [OK]
Hint: Re-insert jobs with updated start times to simulate reuse [OK]
Common Mistakes:
  • Assuming reuse needs no algorithm change
  • Switching sort order breaks scheduling correctness
  • Using brute force is inefficient and unnecessary
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard