Hard Interview Question (Optimal Solution & PriorityQueue)

Here is the Python documentation on PriorityQueue and a Wikipedia article.

Not sure if i’m doing the Big O notation right but i believe this solution may run O(n) times.

from functool import reduce

def merge_k_linked_lists(linked_lists):
    next_links = [link.next for link in linked_lists if link.next]  # O(n)
    total_links = next_links + linked_lists # O(1)
    total_links_sorted = sorted(total_links, key=lambda link: link.val, reverse=True)  # Olog(k)
    result = reduce(lambda val, next_val: Link(next_val.val, next=val), total_links_sorted) # O(n)
    return result

This solution essentially builds the links backwards from the largest link to the smallest.

You’re relying on the linked lists only being 2 items deep, which wasn’t stated in the problem (although it’s true of both the test cases).

In the optimal solution without the priority queue there is an improvement made by removing the redundant iteration to find the index to which the min value belongs to. I’m thinking though that it does a tad bit more than just this change, because it has this line:

val_to_links[min_val].pop()

The pop() without the argument should be removing the last item from the list associated with the min value in the dictionary. However, if there are multiple linked list with the same min value, the program in the previous video advances the linked list found first but this one advances the linked list that was found last in the creation/update of ‘val_to_links’ dictionary. That’s fine here but if the Link object had more attributes associated to it, the order in which the sorted list is returned would be different for these two programs.

PriorityQueue solution can also do without the additional book keeping of indices.

Because duplicates are allowed, the entry into the PQ needs to be wrapped (or the next element of the tuple needs to be comparable).

class PQ_Entry:
    def __init__(self, value, data):
        self.value = value
        self.data = data

    def __lt__(self, other):
        return self.value < other.value

Now, we can just use the PQ without needing the dictionary.

def merge_k_linked_lists(linked_lists):

    pq = PriorityQueue()
    for link in linked_lists:
        if link:
            pq.put(PQ_Entry(link.val, link))

    result = Link(0)
    ptr = result

    while not pq.empty():
        pq_entry = pq.get()
        min_val, min_link = pq_entry.value, pq_entry.data
        ptr.next = Link(min_val)
        ptr = ptr.next
        if min_link.next:
            pq.put(PQ_Entry(min_link.next.val, min_link.next))

    return result.next

A quick note about PriorityQueue, in the video at TC:07:23 you say “1 has the highest priority, so pq.get() is going to return 1, then 2, then 3. For some reason, negative numbers have a higher priority, so pq.put(-1), 1 and -5. pq.get() will be -5, -1, and 1.”

I’m sure you’ve realised by now, but in case anyone else is wondering, the reason that negative numbers have a higher priority is simply because they are lower values than positive numbers.

I could probably get a degree in stating the blinking obvious. ;)

If we’re allowed to use the standard library, the simplest solution seems to use heapq.merge. The only thing we need to do then is to convert linked lists to iterators and iterators to linked lists, which is easy and pleasant.

I solved the problem initially with recursion but I’m not sure what the big O complexity might be for that. Mainly because I dont know what the complexity of my merge(merged_list, list) is.... its effectivly merge sort so o(n log n)?

def merge_k_linked_lists(linked_lists):
    merged_list = linked_lists.pop(0)

    # o(k)
    for list in linked_lists:
        # o(nlogn)??? 
        merged_list = merge(merged_list, list)
    return merged_list


def merge(lst_1, lst_2):
    if lst_1 is None:
        return lst_2
    if lst_2 is None:
        return lst_1

    if lst_1.val < lst_2.val:
        return Link(lst_1.val, merge(lst_1.next, lst_2))
    return Link(lst_2.val, merge(lst_1, lst_2.next))

I think it’s O( k * n ) not O( k * n log(n)) . By merging the list it will take O(n) rather than O( n * log( n)) .