[Coding Dojo] How to nail the most asked coding interview question

[tolstenko]

This is the most asked coding interview question. You have 20 minutes to solve it in 3 different ways.

• Naive: Time complexity O(N^2) and Memory complexity O(1);
• Fastest: Time complexity O(N) and Memory complexity O(N);
• Fastest without memory allocation: Time complexity O(N*Log(N)) and Memory complexity O(1);

[tolstenko]

#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

// Naive!!
// Time complexity O(N^2), Memory complexity O(1)
vector<int> twoSumNumber(vector<int> numbers, int target){
    for(int i=0; i<numbers.size();i++){
        for(int j=i+1; j<numbers.size();j++){
            auto a=numbers[i];
            auto b=numbers[j];
            if(a+b==target) {
                if(a<b)
                    return {a,b};
                else
                    return {b,a};
            }
        }
    }
    return {};
}

// Fastest!!
// Time complexity O(N), Memory complexity O(N)
vector<int> twoSumNumberFast(vector<int> numbers, int target){
    unordered_set<int> cache; // cache consumes up to O(N) space
    for(auto num : numbers) {  // O(N) Searches
        if(cache.contains(target-num)) { // search is O(1) averaged
            if(target-num < num)
                return {target-num, num};
            else
                return {num, target-num};
        }
        else
            cache.emplace(num);
    }
    return {};
}

// fastest without mem allocation!
// Time complexity(N*lg(N)), Space Complexity(1)
vector<int> twoSumNumberWithoutAllocation(vector<int> numbers, int target){
    sort(numbers.begin(), numbers.end());
    int left = 0;
    int right = numbers.size() -1;
    while (left<right){ // enquanto os dois indices nao se chocam
        int sum = numbers[left] + numbers[right];
        if(sum==target)
            return {numbers[left], numbers[right]};
        if(sum<target)
            left++;
        else
            right--;
    }
    return {};
}