Join us and get access to thousands of tutorials and a community of expert Pythonistas.
This lesson is for members only. Join us and get access to thousands of tutorials and a community of expert Pythonistas.
Hard Interview Question (Brute Force)
In this lesson, you’ll use what you learned in the previous sections to solve a hard real world interview question. Hard means something you might find in a more difficult technical phone screen or an onsite interview.
Here’s the question:
class Link:
def __init__(self, val, next=None):
self.val = val
self.next = next
def __str__(self):
if not self.next:
return f"Link({self.val})"
return f"Link({self.val}, {self.next})"
def merge_k_linked_lists(linked_lists):
'''
Merge k sorted linked lists into one
sorted linked list.
>>> print(merge_k_linked_lists([
... Link(1, Link(2)),
... Link(3, Link(4))
... ]))
Link(1, Link(2, Link(3, Link(4))))
>>> print(merge_k_linked_lists([
... Link(1, Link(2)),
... Link(2, Link(4)),
... Link(3, Link(3)),
... ]))
Link(1, Link(2, Link(2, Link(3, Link(3, Link(4))))))
'''
In this first lesson, you’ll go through a brute force solution. The entire solution will be available at the end of the course. Try the problem yourself and then watch the video for the solution.
If you want to learn more about linked lists, check out Linked Lists in Python: An Introduction.
00:00
In this video, you will go through a hard interview question. This would be something you might see on an onsite interview or maybe a phone interview. Let’s get started with the question. merge_k_linked_lists().
00:12
This question is going to ask you to "Merge k sorted"—sorted is important—"linked lists into one sorted linked list." If you don’t know what a linked list is, a linked list is a data structure, which has a value and a next pointer.
00:29
Basically, it’s a recursively-defined data structure, because every next element is also an instance of a link, or it’s None. For example, if you created a Link like this, with the first value being 1, and the next pointer would be another linked list with value 2.
00:47
This linked list would be Link(1), and then another linked list, which also has 2 at the front, and then the next pointer points to Link(3), 3 at the front, and then Link(4).
00:58 I will link some more documentation down below on linked lists. They’re a very important data structure that you need to know for interviews. So, what is this question asking, then? Well, the input is a list of linked lists.
01:10
They’re sorted and we need to combine them into one long sorted linked list. For example, merge_k_linked_lists() takes in a list of two linked lists—1, 2 and 3, 4. The final output will be a sorted linked list—1, 2, 3, 4. Here, the input is 1, 2, then 2, 4, then 3, 3—each individual linked list is sorted, and our final output is 1, 2, 2, 3, 3, 4.
01:35
You can assume that every item in this linked list is not None. I highly recommend to try to solve this on your own. It is a hard interview question, so it’s okay if you aren’t able to come up with the solution, but definitely try for maybe 30 or 45 minutes.
01:49 Don’t try to directly just watch the solution. That will really take away from the learning experience. I am actually going to break the solution down into three videos: the first one being a sort of initial solution, the second one being a suboptimal solution, and the third one being one of the more optimal solutions. So, please take some time to solve this.
02:08 I’m going to go over the solution in five, four, three, two, one. So, in an interview, it’s always good to just try to get a solution going. It doesn’t have to be the best solution from the get-go, but it’s better to have a working solution than no solution by the end of the interview. A lot of problems have what you call a brute force solution.
02:27 This is just like hardcoding all the values, just like doing the most naive, throwing them all together, and then making a linked list. In the case of this question, what we can do is just loop through every single linked list like this, add all the values to another list, sort that list, and then make our final linked list. It’s brute force because you’re not really doing anything clever, or no real algorithm—you’re just dumping all the values into something and then just getting all those values and putting them somewhere.
02:54
So, let’s write it down because it’s always good to write down the thought process. # put all the values of all the linked list into a list.
03:02
# sort the list and create a final list from those values.
03:09
So, we’ll have values as an empty list. for linked_list in linked_lists—
03:18
I guess let’s just call it link as an abbreviation, just so it’s shorter. In an interview, you might not want to write a bunch of stuff.
03:27
You can do something like while link—so basically, while there are still values in the link, add to the values the link.val
03:36
and then increment the link to be the next Link. Let’s just print(values) to make sure that it worked. Open up a terminal.
03:47
Okay. So, the values is [1, 2, 2, 4, 3, 3]. So, it did get through all the values. It’s not sorted because we didn’t sort it. But that seemed to work. So let’s do sorted_vals = sorted(values),
04:03
and now this is going to be the sorted, and now, let’s construct the final linked list. This is going to be result = Link(0). With many linked list questions, when you create a result linked list it’s very common to create a head node—which is sort of the front—and then you’ll do something like result.next = Link(1), and then like result.next.next = Link(2), or whatever, and then return result.next.
04:27
So, it’s almost like you’re appending to the end of this Link and then returning result.next. And then, because if you did something like result = result.next, you’ll lose the pointer to the front of the linked list.
04:38
You’ll need another variable pointer equal to result. So now, looping through all the values and constructing that linked list, do something like for val in sorted_vals—sorry, looping through the sorted values, not this values—pointer.next equals a Link of val, then pointer = pointer.next. Then, return result.next.
05:00
Cool, everything passed. Basically, this logic is saying, “Okay, mutate whatever the pointer is pointing at .next pointer to be the value, and then change the pointer to point to the next node.
05:13
So, let’s just print out result and pointer each iteration to see what happened there. So, what happened is result is Link(0), right, because it started at Link(0). pointer is Link(0). Then, pointer.next, which is this link’s .next, became a Link with 1, and then changed pointer to be
05:33
the .next. And then, pointer is now pointing to this Link. It did pointer.next = Link(2), added it, then changed pointer equal to pointer.next.
05:44
Now, pointer.next points to this Link, And then that .next added this Link, and then moved the pointer to here.
05:53
The same goes there. The pointer was pointing to this Link and then .next created the 3, and then moved the pointer to the pointer.next. Same there. If you’re still confused, I would definitely try to put a breakpoint here or maybe draw some diagrams to see that the pointers are moving like that. So, let’s look at the runtime.
06:10
Let’s define k to be the length of linked_list, so basically, that’s going to be the number of linked lists. In this case, it would be 1, 2, 3, and 1, 2.
06:19 Then, define n to be the max length of any linked list. For example, in this case, it would be 2, because the max length is 2. This will just give us a good estimation of how many numbers are in all the linked lists in the list. For example, k * n is upper bound of all numbers, because all the linked lists might not
06:41 have this max length, but we know that this is an upper bound, which we sort of care about for runtime. And so k * n is an upper bound of all numbers, or rather, of the number of values in all linked lists.
06:56
So, let’s look through here. This for loop is going to loop through k things because there are k linked lists in this linked_lists. while link—so, this is looping through each individual linked list, which is as we defined to be O(n)—upper bound O(n).
07:15
So this for loop actually takes k * n. Now, let’s move down here. So, sorting always takes N * log(N), where capital N is whatever the length of this values is. So, in our case, the length of this values is going to be k * n, because that’s an upper bound for the number of values. So, this one line takes k * n * log(k * n).
07:37 Now, to construct the final linked list, we’ll be looping through this many sorted values. While the number of sorted values doesn’t change, it’s just the sort that takes that long.
07:47
So, this for loop is going to take k * n. Both of these lines are constant, so this loops through k * n number of values.
07:55
So the final runtime—I guess I’ll put it all the way at the bottom, # final runtime—would be whatever takes the longest, which is this. In the next video, you’ll see another solution that maybe is better.
James Uejio RP Team on April 27, 2020
@belushkin thank you for sharing! Yes that is the case where N is the number of elements (in my example I use k and n as different variables).
James Uejio RP Team on April 27, 2020
Note for everyone, if you want to learn more about linked lists, here is a Wikipedia article
Özgür Gündoğan on Sept. 13, 2020
My solution taking the advantage of that Link class does not contain any special information. If link class contains any special information, this is not useful.
def merge_k_linked_lists(linked_lists):
all_values=[]
for linked_list in linked_lists:
all_values.append(linked_list.val)
all_values.append(linked_list.next.val)
all_values=sorted(all_values,reverse=True)
prev_link=None
for val in all_values:
if not prev_link:
prev_link=Link(val)
else:
new_link=Link(val,next=prev_link)
prev_link=new_link
return prev_link
James Uejio RP Team on Sept. 17, 2020
Nice solution Ozgur!
linus-g on June 5, 2021
Here is my solution. It finds the linked list that has the current link with the smallest value, and then adds that link on to the end of the new list and removes it from its original list. This should make efficient use of the fact that all the linked lists are themselves sorted.
def merge_k_linked_lists(linked_lists):
first_link_in_new_list = None
while len(linked_lists) > 0:
# Find the smallest link by value in of all the links currently in linked_lists
smallest_link = min(linked_lists, key=lambda x: x.val)
smallest_link_index = linked_lists.index(smallest_link)
if first_link_in_new_list is None:
# If this is the first iteration, set up new linked list
first_link_in_new_list = smallest_link
last_link_in_new_list = smallest_link
else:
last_link_in_new_list.next = smallest_link
last_link_in_new_list = last_link_in_new_list.next
# Update the linked list that had the smallest value,
# remove if there are no more values
if linked_lists[smallest_link_index].next is None:
del linked_lists[smallest_link_index]
else:
linked_lists[smallest_link_index] = linked_lists[smallest_link_index].next
return first_link_in_new_list
Elise Ratcliffe on March 31, 2022
I’m trying to understand your solution, but there’s a part I’m really struggling with. I’ve commented the code to explain what I’m not understanding. I’ve had a look at the resources provided, but I’m still not getting what’s happening with pointer = result. Can anyone explain, or link to a good explanation of the theory?
sorted_val = sorted(values)
'''
I know the next section is supposed to start creating
a linked list by iterating through the sorted values
but am unclear how.
'''
# I know this is initialisng the final linked list
result = Link(0)
# what is happening here? I think this is the key point I'm struggling with
# we're only updating pointer in the for loop, but that's changing result
# How?
pointer = result
for val in sorted_val:
print(f'result is {result}, pointer is {pointer}')
pointer.next = Link(val)
pointer = pointer.next
# I understand the .next removes the first "0" that we added when creating the linked list
return result.next
I was going to ask this question on stackoverflow but there have been quite a few similar questions - unfortunately, none of them are very clear to me.
Bartosz Zaczyński RP Team on April 1, 2022
@Elise Ratcliffe The solution presented in the video boils down to the following three high-level steps:
- Go through each individual linked list and unpack the stored values onto a flat list
- Sort the list of unpacked values
- Build a new linked list from the sorted values
It seems to me that you’re struggling to understand the last point, so I’ll try to break it down for you. Let’s use one of the examples from the video to try and visualize what’s going on:
- Linked lists (input):
- ① → ②
- ② → ④
- ③ → ③
- Unpacked values: 1, 2, 2, 4, 3, 3
- Sorted values: 1, 2, 2, 3, 3, 4
- Merged linked list (the expected output): ① → ② → ② → ③ → ③ → ④
So, now the question is, how do you wrap the sorted list of numbers into a corresponding linked list? Both are sequences, but every element of the linked list (called a node) must also point to the next element until there are no more elements. You can start by creating the first node (head) of your list:
head = Node(0)
(I’m using slightly different variable and class names here to make my point across easier. Also, note that using .next as an attribute name shadows the built-in next() function. In cases like this, it’s customary to append a single underscore character to the variable name to avoid name conflicts, for example, .next_.)
head is going to be the first element of your resulting linked list. It can have any value at all, such as zero, because you’re going to discard that element later anyway. Your linked list looks like this at the moment: ⓪
Next, you go through the sorted values, then create the associated node element for each of the values, and hook the current node up to the previous node. To keep track of the previous node, you’ll need another helper variable. Let’s call it previous because we’ll use that variable to refer to the last node:
head = Node(0)
previous = head
for value in sorted(values):
current = Node(value)
previous.next_ = current
Initially, the previous node is set to the head of your resulting linked list. This will ensure that the head will now point to the current node with the desired value, for example: ⓪ → ①.
You must also remember to update the current value of the previous node so that the subsequent loop runs will move to the next node in your linked list:
head = Node(0)
previous = head
for value in sorted(values):
current = Node(value)
previous.next_ = current
previous = current
Otherwise, you’d always keep overwriting the .next_ attribute of the head, ending up with something like ⓪ → ④ as a result. You can rewrite the code snippet above without using the current helper variable, which is similar to the solution in the video:
head = Node(0)
previous = head
for value in sorted(values):
previous.next_ = Node(value)
previous = previous.next_
When the loop finishes, you’ll have created the following linked list: ⓪ → ① → ② → ② → ③ → ③ → ④. Finally, you can use head.next_ to discard the extra node that you created in the beginning:
head = Node(0)
previous = head
for value in sorted(values):
previous.next_ = Node(value)
previous = previous.next_
return head.next_
So, your linked list will not contain the initial head but only the nodes with the desired values: ① → ② → ② → ③ → ③ → ④.
Here’s the complete solution with an example:
from dataclasses import dataclass
@dataclass
class Node:
value: int
next_: "Node" = None
def merge(linked_lists):
head = Node(0)
previous = head
for value in sorted(unpack_values(linked_lists)):
previous.next_ = Node(value)
previous = previous.next_
return head.next_
def unpack_values(linked_lists):
for head in linked_lists:
while head:
yield head.value
head = head.next_
if __name__ == '__main__':
print(merge([
Node(1, Node(2)),
Node(2, Node(4)),
Node(3, Node(3)),
]))
James Carr on May 13, 2022
My solution before watching video 😬 ..
def merge_k_linked_lists(linked_lists):
nodes = []
for linked_list in linked_lists:
node = linked_list
while(node):
nodes.append(node)
node = node.next
# Sort the nodes based on their value and re-link in order.
nodes.sort(key=lambda node: node.val)
for i in range(len(nodes)):
nodes[i].next = nodes[i+1] if i < len(nodes)-1 else None
return nodes[0]
abdrfaoui on Oct. 24, 2022
My solution:
def merge_k_linked_lists(linked_lists):
'''
Merge k sorted linked lists into one
sorted linked list.
>>> print(merge_k_linked_lists([
... Link(1, Link(2)),
... Link(3, Link(4))
... ]))
Link(1, Link(2, Link(3, Link(4))))
>>> print(merge_k_linked_lists([
... Link(1, Link(2)),
... Link(2, Link(4)),
... Link(3, Link(3)),
... ]))
Link(1, Link(2, Link(2, Link(3, Link(3, Link(4))))))
'''
values = []
for link in linked_lists: #O(n)
values.append(link.val)
values.append(link.next.val)
values.sort(reverse=True) #O(nlog(n))
linked = None
for val in values: #O(n)
linked = Link(val, linked)
return linked
Become a Member to join the conversation.
belushkin on April 27, 2020
My solution before watching video:
I guess complexity would be: log(N) for priority queue and 2N for for list traversal. So it would be Nlog(N)