# 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!

Become a Member to join the conversation.

belushkinon April 27, 2020My solution before watching video:

I guess complexity would be: log(N) for priority queue and 2

N for for list traversal. So it would be Nlog(N)