This content originally appeared on Level Up Coding - Medium and was authored by Thenjiwe kubheka
Google Interview Question: Two Sum
A very popular interview question that tests your knowledge in producing efficient code. Ideally, there are two approaches to solving this popular question.
We are given a list of numbers together with the target number and are expected to figure out which two numbers add to the target. The combination of numbers could or could not exist.
The question could be structured as follows;
“ Suppose we have an array of integers. We have to return the indices of two integers, such that if we add them up, we will reach a specific target that is also given. Here we will take one assumption, that is always there will be one unique solution in the array, so no two sets of indices for the same target will be there.
For example, suppose the array is like A = [2, 8, 12, 15], and the target sum is 20. Then it will return indices 1 and 2, as A[1] + A[2] = 20.”
Method 1: Brute Force
This is ideally the easiest we exhaust all our options, to check if the combination exists.
We will use two pointers; one pointing at the first item of our list and the other one iterating through our list.
So one pointer will be pointing at 2, this is the first item in our list and the second traversing through the list. We will check the combination of 2 and 2, which does not add up to 20, hence False we move on.
The next combination is 2 and 8, which produce 10 and is not True, we move on to 2 and 12, which give us 14, False.
We move on to the next item we test 2 and 15, which give us 17, we looking for 20 we return False, we have exhausted all combinations for two, we move on to 8.
First, we check the combination of 8 and 2, we get 10 and move on to the combination of 8 and 8, which gives us 16, the combination of 8 and 12 which give us 20. We have found our match and will return True.
This was quite draining imagine if we had to loop multiple times on a huge dataset and the items were at the end of the list? Hence this method returns a time complexity of Big O(n²) which is very slow.
On the bright side, we did not utilize memory, and we have a space complexity of O(1).
Nonetheless, let’s code up our solution:
def twoSum(nums,target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums [j] == target:
return[i,j]
If someone threw this solution at me, I wouldn’t be amused or impressed in fact I would be very disappointed. Efficiency is very important, especially in Big Tech. I would rather go for a much more optimized solution.
Method 2
For the second method, we just need one pointer as we will be seeking the help of a set data structure.
The same rules apply as we are searching for a combination of two numbers that add up to the target, which is 20 in our case.
Our set will save all combinator items we have ‘seen’, this will keep track of our checks.
We will start with 2 as it is our first item, we know we need 18 to get to the sum of 20. We will then save 18 in the set. Move on to the next item which is 8, we need 12 to get a sum of 20 and thus we will save 12 in our set.
The next item is 12, but we already have 12 in our set and our condition has been met, we will return True.
Let's code up our solution:
def twoSum(nums,target):
combinators = {}
for i in range(len(nums)):
if target - nums[i] in combinators:
return True
else:
combinators[nums[i]] = i
test_list = [2,8,12,15]
print(twoSum(test_list,20))
As we only loop once through the list, our time complexity is BigO(n) but remember we used a set and this will change our space complexity to Big O(n).
Additional Resources
Google Interview Question : Two Sum was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Thenjiwe kubheka
Thenjiwe kubheka | Sciencx (2021-08-29T23:20:13+00:00) Google Interview Question : Two Sum. Retrieved from https://www.scien.cx/2021/08/29/google-interview-question-two-sum/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.