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

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)