1. Two Sum

# Approach 1. Brute Force
# Time Complexity: O(n^2)
# Space Complexity: O(1)
class Solution1:
    def twoSum(self, nums, target):
        for i in range(0, len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []


# Approach 2. Hash
# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution2:
    def twoSum(self, nums, target):
        hashed_nums = dict()
        for i in range(len(nums)):
            # We only keep the last number if it's a repeating number
            # This works because it has exactly one solution
            hashed_nums[nums[i]] = i

        for i in range(len(nums)):
            pair_num = target - nums[i]
            if pair_num in hashed_nums and hashed_nums[pair_num] != i:
                return [i, hashed_nums[pair_num]]
        return []


# Approach 3. Hash (Enhanced Version)
# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution3:
    def twoSum(self, nums, target):
        hashed_nums = dict()
        for i in range(len(nums)):
            pair_num = target - nums[i]
            if pair_num in hashed_nums:
                return [i, hashed_nums[pair_num]]
            hashed_nums[nums[i]] = i
        return []

 

Mock: How to: Work at Google — Example Coding/Engineering Interview – YouTube

Similar to two sum question. But the array here is sorted (ascending)

[1, 2, 3, 9] sum = 8
[1, 2, 4, 4] sum = 8

I’m trying to figure out is you’re looking for a pair of numbers then that add up to a target number.

How are these numbers given? Can I assume that they’re kind like in memory? an array?

How about repeating elements? Can I assume that they would be like, for instance, can I use like the 4 and the 4 (same element) to get that target?

You can’t repeat the same element at the same index twice.
But certainly, the same number may appear twice.

How about these numbers? Are they integers or are they floating point?

You can assume they are always be integers.

Negatives? Positives?

Negatives can happen

So, first, the simplest solution of couse is just comparing every single possible pair. So, I could just have two for loops. One scanning the whole thing, and then the second one starting from let’s say you have the i loopand the j loop starting from i plus 1. So that I don’t repeat the same value. And just testing all of them if the sum is equal to the target sum.

That’s obviously not very efficient but that would be like a way to solve it.

That would work. It certainly would be time-consuming.

That would be quadratic. So, better than quadratic…

If I have a 1, what I’d need to figure out is if there’s a 7 somewhere in the array.
That’s the case, it’s sorted. Then I can just do binary search.

That’s a bit better than quadratic. Binary search is log algorithm in a sorted list.

So, what if you took a look at instead of doing a binary search which is unidirectional, what if you started with a pair of numbers to begin with. And work your way through in work from there.

Okay, let me try to bound this thing. So, the largest possible sum would be the last two values. And the smallest possible sum would be the two smallest.

[1, 2, 3, 9]

The sum is 10 in this case. It’s too large. So, I need to find a smaller sum. So, I could just move this one (9) over here (3). And if that is too small now and I need to move that one (1) over there (2). So, I can do it in a linear solution, just moving at each iteration. I either move the high one lower if my pair is too large. And I move my lower higher if my pair is too small. And I end whenever I either find the pair that adds up to 8 or whenever they cross.

How does it make that faster than a binary search.

In a binary search case, I was doing log for finding. But I had to repeat that for every element. It was an nlogn solution.
In this case, I just need to do that moving scanning the one time. So, it’s a linear solution. So, that’s faster.

What coding language would you prefer to do it?

I preferred C++ if that’s okay.

Now, I realize that I haven’t figured out what I need to return. So, do I want the pair, the hindeces of the pair, or whether I just found it or not?

For the purposes of the example, we will go with whether you’re found it or not. But, let’s say you were going to return the pair, how could that become a problem if there wan’t a pair?

bool HasPairWithSum (const vector<int>& data, int sum) {
    int low = 0;
    int hi = data.size() - 1;
    while (low < hi) {
        int s = data[low] + data[hi];
        if (s == sum) return true;
    } 
}

I see what you’re getting at here. But now, I can no longer guarantee for you that the numbers in this collection are sorted.
ou have to think of a different way just to pair them against each other.

When I look at a number what I need to figure out is if the complement is in the rest. For example, have I seen 5 (8 – 3)in the past?
I can use a data structure that is very good for lookups. I can do something like a hash table which has like a constant time lookup.

Do you need a key in this case?

I guess I don’t need a key. I mean I just need the values, the elements, Actually, I don’t want to store any payload. So, a hash set would be the thing to do. So, I hash set all the compliments and then I look for them.

To deal with the rcase of repeated elements, I only look for things that I have seen before. So, as long as I check before I insert things that should work.

bool HasPairWithSum (const vector<int> data, int sum) {
    unordered_set<int> comp; //complements (I don't want to write compliments all the time. So, I'm just going to call it comp)
    for (int value: data) {
        if (comp.find(value) != comp.end)
            return true;
        comp.add(sum-value);
    }
    return false;
}

That’s it. Let me go through some examples to make sure.

set = {} -> {7} -> {7, 6} -> {7, 6, 5} –> return false
set = {} -> {7} -> {7, 6} -> {7, 6, 4} –> found, return true

Would you do anything differently here if there were 10 million integers in this collection?

So, if the input is large, does it still fit in memory or?

Probably not at this point.

So, if it doesn’t fit in memory, what I can do…. So, is the range of these values limited in some way?

You can assume that. It might be.

So, if my set fits in memory, but my whole input doesn’t fit in memory. Then I can just sort of process it in chunks, right? I chunked it andn I just put it in a set. I accumlated my set. If we can do it in parallel, then it’s kind of the same thing. So, now you have multiple computers, each one particular rocessing each bit of it of the input. Each one producing a set of complements that this bit has seen and we just sort of merge them. The merging would be a bit tricky because we want to make sure that again we don’t sort of look for the tihing that we have put in. So, I guess as long as each individual computer is testing this (Line 3-7) in the right order when we mere them. Now, we can say those two are correctly. For examply, I have a 4 in one computer and 4 inthe other computer. When I merge them, I would need to be careful that I reconcile them. But other than that I think that would be the only consideration.

Recap

1. The first thing he did was to ask for clarification to the problem. So, if you don’t fully understand the question, please feel free to ask for clarification or ask to have it repeated. You can write it down verbatim if needs. Whatever you need to do to get complete understanding of the questions that’s being asked.
2. Another thing that he did is while he was going through his solution, even before he started writing code down, he thought out loud constantly. Constantly thinking out loud is probably the best thing you can do in the interview because it gives the interviewee the opportunity to see your thought process and use that to possible course-correct you more towards the question that they were asking or to feed off of that and ask you more questions that might help you demonstrate your knowledge even further because you may have said something that they can expand upon. But in the very least, it’s going to help you to work that problem out and there’s nothing wrong with working at problem with somebody else it always needs to minds are better than one.
3. Another thing that he did really great is he thought through everything before he started writing something down. So, we thought about how we were going to do it. We actually went through two iterations. The first thing the thing at the top of his mind wasn’t the best solution and it’s not going to be the best solution for anybody. So think through what you want to do and then you might get challenged by the interviewer to think better, faster, or more efficiently, think through that solution and then ultimately when you feel like you’re at a spot where you can code it then you can start coding it down on the screen or paper.
4. He did really well that I encourage everyone to do is to test it in real time. If the interviewer doesn’t give you an example, please make one up. Also, think about edge cases. Edge cases can be important. So, in this case, he thought about a empty collection. He tested his logic with an empty collection. It was really nice to see him thinking about those edge cases and bringing them up in the air view.