Join us and get access to hundreds of tutorials and a community of expert Pythonistas.

Unlock This Lesson

This lesson is for members only. Join us and get access to hundreds of tutorials and a community of expert Pythonistas.

Unlock This Lesson

Hint: You can adjust the default video playback speed in your account settings.
Hint: You can set the default subtitles language in your account settings.
Sorry! Looks like there’s an issue with video playback 🙁 This might be due to a temporary outage or because of a configuration issue with your browser. Please see our video player troubleshooting guide to resolve the issue.

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 valuespointer.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 linkso, 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.

belushkin on April 27, 2020

My solution before watching video:

import heapq


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):
    """
    >>> 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))))))
    """
    links = []
    for link in linked_lists:
        while link:
            heapq.heappush(links, link.val)
            link = link.next

    res = Link(heapq.heappop(links))
    v = res
    while links:
        v.next = Link(heapq.heappop(links))
        v = v.next

    return res

I guess complexity would be: log(N) for priority queue and 2N for for list traversal. So it would be Nlog(N)

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.