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 (Suboptimal Solution)
In this lesson, you’ll see an attempt at improving the brute force solution. You’ll see how this solution is still suboptimal, but it’s important to understand before moving on to the optimal solution. The suboptimal solution will be available at the end of the course.
00:00
In that first video, you saw a brute force solution where you just put all the values of the linked list into a list, sorted it, and created a final linked list—this should be # final linked list—from those values.
00:10 The resulting runtime was k * n * log(k * n). Let’s see if we can do better.
00:17 This solution actually didn’t take advantage that each linked list is sorted. This solution would have worked for any linked list, but let’s see if we can take advantage of the fact that they’re sorted.
00:28
So, if you were the computer, how would you actually build this linked list? Basically, how do you know 1 is supposed to be the first number? Well, you know, all of them are sorted, and you know 1 is the smallest of all these numbers, so you know 1 goes here. Then, in your mind, you’re going to be like, “Okay, I’ve already included this one so I’ll just, like, remove it in my mind and then, now, look at which number should I include here?” Well, it’s going to be the smallest, so it’s basically like this is the 2, and then this is the 2. And then now it’s, “Oh, this is the smallest, so let’s put that in there. This is the smallest, so let’s put that in there.” It’s okay that you’re always looking at the front, because these linked lists are sorted, so you can always guarantee that the front value will be smaller than the rest of the values. Okay, so conceptually, that doesn’t seem too hard, but in the code, that might be a little difficult.
01:16
I’m just going to delete all this code. It’ll all be in the ZIP file at the very end, but basically, let’s try to implement that algorithm. # look at the front value of all the linked lists find the minimum, put it in the result linked list "remove"—I’m going to put it in quotes because obviously, we don’t want to, like, mutate the input, but it’s—like, in our minds—removing that value that we’ve added.
01:41
# "remove" that value that we've added. keep going until there are no more values to add.
01:49
Let’s put this Link() back and then get started. Okay, so let’s try to look at the front value of all the linked lists. Something like link.val for link in linked_list. Okay, find the minimum. min_val is going to be the min() of front_vals.
02:05
# put it in the result linked list. So, we need a result = Link(0), then a pointer equal to result, same concept as part one where basically, the result is going to be this head node, and then pointer is going to move along the result and add nodes.
02:22
Now that we have the min_val, let’s loop through the links again. for link in linked_list: if link.val == min_val, now add it to result.
02:35
So, pointer.next = Link(link.val),
02:39
then pointer = pointer.next. And now, # "remove" that value that we've added. So, how are we going to “remove” this Link from our thought process? Well, we can do something like this: get the index like this, enumerate through the linked list, and then do
02:58
linked_lists[i]= link.next. So, this is going to mutate the index of the linked list, change it to now be Link(2).
03:11
This is actually not good practice to mutate the input, because in Python you pass by reference, so if something else is referencing this linked_lists list and then you’re mutating it, then that’s not very good.
03:23
So really, we need to do something like copy_linked_list (copy of linked list) will be linked_lists, like this, and then—add s—use this whenever we’re doing anything.
03:36 So, what this is going to do is copy a reference to each of these linked lists. It won’t copy each linked list, but basically, it’ll create a copy of the list and it will point to each linked list. And then, when we mutate, here, it’s going to just mutate this copy we’ve made, and the initial input will still stay preserved.
03:56
You could ask the interviewer, though, if it’s okay to mutate the input, but most of the time I feel like it’s better to create a copy. Okay. So, let’s do something like print(result, copy_linked_lists), and see what just this code did.
04:10
Okay. We got Link(0), Link(1). So, it added the Link(1) to result correctly. It got <hard_interview.Link object>. Oh. That’s because, in our Link class, there’s a __str__() method, but this should really be a __repr__() method. That’s a little bit better. Okay.
04:23
Now, let’s look at what the copy_linked_list is. So, copy_linked_list has Link(2), so it actually “removed” this Link(1) from the copy, then Link(2, Link4)), then Link(3, Link(3)), so it didn’t touch either of these.
04:35
So, that’s good. So, we have to actually do this over and over again until there are no more values to add. So, while any(copy_linked_lists)—that’s going to check, “Are any of the values in copy_linked_lists not None?” Then, we know that there are still values. Put all of this, like this.
04:55
Save. return result.next.
05:01
Maybe that’ll just work. 'NoneType' object has no attribute 'val' […] link.val for link. This is line 38. Okay. Well, why does that happen? Well, it’s because some of the values in copy_linked_lists could be None, but this is just checking that any of them are not None, so we need to do a check if link, here, to make sure that we only get the front values of the ones that aren’t None. Okay, now, link.val == min_val. Same issue, here.
05:27
When you’re looping for the linked lists of the copy_linked_lists, it could be that they are None already. So, we need to do something like if link and link.val == min_val. And it actually passed.
05:39
Let’s look at what the algorithm actually did. It looked at the front values of all the linked lists, found the minimum, which is 1, then looped through the front values again to find which linked list is equal to the minimum, remove that, did that process again—2, 2, 3. This is the minimum, remove that.
05:58
So now, really, there’s a None, here. I don’t care about the None, I care about 2 and 3—remove this. 4 and 3—remove this. 4 and 3—remove this.
06:11
4, None. Now, this while any() is now going to return False because all of them are None, and then return the result. Okay, I bet you’re thinking maybe there are some optimizations.
06:23
We’ll look at that in the next video. But first, let’s look at the runtime of this solution. We actually defined k to be the length of the linked_lists, and then n to be the max length of any linked list.
06:36 And then k * n to be the upper bound of number of values in all linked lists.
06:44
So, let’s look at the runtime using those variables. Well, copying the linked list is only going to take O(k), because that’s the length of linked_lists.
06:54
This is constant. This is constant. while any(copy_linked_lists)—so, the actual while condition is going to take O(k), because it has to loop through all the values in copy_linked_lists and check if they are a True value or a False value. Here, this is going to take O(k), because that’s going to loop through all the values in copy_linked_lists. Finding the minimum is going to be O(k).
07:17 This loop right now is going to run O(k) times, as well.
07:22
This is constant, constant, constant, constant. So, this whole while loop takes O(k), because it’s basically O(k) + O(k) + O(k) + O(k), and that’s still O(k).
07:35
But now the question is # how many times does the while loop run? We know that the while loop, each time, will take O(k) time.
07:43 How many times does it run? Well, looking at that algorithm again, you’d have to look at this value, remove it, then check all these values, remove the minimum, then check this value, remove it, then check these values, remove it, et cetera. By the end, it’s going to have done k * n iterations, because that’s an upper bound of all values in all linked lists. So, what is our final runtime?
08:07
Final runtime is O(k * n * k), because this is the number of times that we executed the while loop, and this is how much time each while loop took. Okay, so remember from part one, the brute force solution—# brute force—
08:24 final runtime was k * n * log(k * n), and now this current solution is k * n * k. So, this solution is actually slower than the brute force solution, unless of course, n is really, really, really large, and this log becomes greater than this k. But most of the time, this solution is actually worse.
08:47 But this idea of sort of finding these values and mutating it, or removing it, or something like that will be really useful in the next video, where we optimize this solution to be better than the brute force solution.
mdwikira on Sept. 14, 2021
My solution for the suboptimal version.
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))))))
'''
result = None
last = None
ll = linked_lists[:]
while ll[0:]:
smallest = min(ll, key=lambda x: x.val)
ll.remove(smallest)
if smallest.next:
ll.append(smallest.next)
smallest.next = None
if result == None:
last = smallest
result = last
continue
last.next = smallest
last = last.next
return result
Become a Member to join the conversation.
ambreen2006 on Nov. 19, 2020
Thank you for this wonderful tutorial. I’m finding it very useful.
I think in the sub-optimal solution provided in the video + code, there is no need to separately iterate for the min value and the index to which the min val belongs to. So I can write something like this:
But please do correct me if I overlook something.