From the course: Advanced Algorithmic Thinking with Python

The two-sum interview problem - Python Tutorial

From the course: Advanced Algorithmic Thinking with Python

Start my 1-month free trial Buy for my team

The two-sum interview problem

“

- [Instructor] We are going to kick off with a classic challenge that is often set in coding interviews. It's called the two-sum problem. So given an unsorted list of integers, we have to find a pair which add up to a given value. And we have to identify the indices of the values which sum to this target. The indices must be distinct, i.e. you can't use the same value in the same position twice. So for example, if the input was a list containing 1, 2 and 3, and the target value was 4, then we want the indices of the values, which sum to 4. So they're going to be 0 and 2 in this case. And for this example, we have the list, 8, 7, 2, 5, 3, 1, and the target of 10. And there's actually multiple possible solutions here. So we can have the indice 0 and 2 or 2 and 0. They're both valid. Or 1 and 4 or 4 and 1. If you check out Branch 01 01 of the repository for this course, you'll find a file called two-sum stub dot py. And what this is is a function stub for you to complete, which is going to provide a solution to the two-sum problem. Now, for now, we're only interested in a simple or brute force solution, so don't worry too much about efficiency. However, you do need to get these assertions to pass. Now, if you haven't worked with assertions, I'm just going to explain the concept for you. So at the moment, our function returns a default value of none, because by default, Python returns none from a function if nothing else is specified. So the return value from these function calls, so for example, on line seven, when we call two-sum problem with parameters, a list, 1, 2, 3, and target 4, then it's going to return number. We are asserting that it should return something which is contained in this list. So it should either return 0 comma 2 or 2 comma 0. Now, the reason that I've covered both of these contingencies is that we haven't stipulated the order in which you're going to go through your list. So it might be that your solution returns the first index and then the second one, or it might return them in the other order. But the point is, you need to complete this function so that it takes these arguments and returns the correct values. I'll just show you it running now with the assertions not working, so you can see how that works. So the minute, it's saying we've got an assertion error, because we've called our function with this particular data or these parameters. And it's getting the return value of none. It's not getting what was expected. So it's giving me an error. When you're working with assertions, which is a very simple form of test-driven development, then you know your code is correct when nothing happens. That means there'll be no assertion error, and you may not have provided any output, so literally nothing happens is good. Okay. So have a go at this. At this stage, it's really not that important if you successfully complete the challenge. It's much more important that you have a go. And in doing so, you're going to better understand the kind of process that you need to engage in when approaching a problem like this. Okay. Good luck with it.

Contents