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.
Hard Interview Question (Suboptimal Solution)
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: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.
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.
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.
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
# 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.
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
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: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.
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.
Okay. We got
Link(1). So, it added the
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.
Now, let’s look at what the
copy_linked_list is. So,
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.
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
None?” Then, we know that there are still values. Put all of this, like this.
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.
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.
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—
3. This is the minimum, remove that.
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.
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: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?
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.
Become a Member to join the conversation.