# Hard Interview Question (Optimal Solution & PriorityQueue)

In this lesson, you’ll see the final optimal solution to solving the `merge_k_lists` hard interview question. The solution takes advantage of the `PriorityQueue` abstract data type, which is similar to a queue but associates each element with a priority. Getting an element, it retrieves the element with the highest priority. Both `.put()` and `.get()` take logarithmic time.

Here’s an example:

Python
``````>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put(2)
>>> pq.put(1)
>>> pq.put(3)
>>> pq.get()
1
>>> pq.get()
2
>>> pq.get()
3
>>> pq.empty()
True
>>> pq.put((1, "hello"))
>>> pq.put((2, "world"))
>>> pq.get()
(1, "hello")
>>> pq.get()
(2, "world")
``````
Copied!

You can check out the Python documentation on PriorityQueue and the Wikipedia article.

You’ll see all solutions at the end of the course.

James Uejio RP Team

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

Daniel A

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

return result
``````

Daniel A

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

Simon Yates

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

ambreen2006

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.

ambreen2006

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

ptr = result

while not pq.empty():
pq_entry = pq.get()
ptr = ptr.next

return result.next
``````

Geoff Rliey

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

pavolsevera

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.

stephencarey1905

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

# o(k)
# 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: