CareerCup

code

interface TwoSumInterface{
    public void store(int value);
    public boolean test(int value);
}

public class TwoSumInterfaceImpl implements TwoSumInterface {
    private Set<Integer> localStore = new HashSet<Integer>();
    
    @Override
    public void store(int value) {
        localStore.add(value);
    }

    @Override
    public boolean test(int newValue) {
        for(int currentNumber:localStore){
            if(localStore.contains(newValue - currentNumber)) {
                return true;
            }
        }
        return false;
    }
}

Store Time Complexity: O(1), Space Complexity : O(n)
Test Time Complexity O(n), Space Complexity : O(n).

You can solve this problem with O(n) for test() and O(log(n)) for store().
- For store(): use insert() function of set to always have a sorted set
- For test(): use left and right variable to narrow down the range of finding the 2 target numbers.

#include <iostream>
#include <vector>
#include <set>

using namespace std;

class NumberManager {
public:
    void store(int number){
        numbers.insert(number);
    }
    bool check(int number){
        set<int>::iterator left = numbers.begin();
        set<int>::iterator right = --numbers.end();
        
        
        while (left != right){
            if (number == *left + *right){
                return true;
            } else if (number > *left + *right){
                left++;
            } else {
                right--;
            }
        }
        return false;
    }
    void printNumbers(){
        for (set<int>::iterator left = numbers.begin(); left != numbers.end(); left++){
            cout << *left << " ";
        }
        cout << endl;
    }
private:
    set<int> numbers;
    
};



int main(){
    NumberManager test;
    test.store(1);
    test.store(3);
    test.store(2);
    test.printNumbers();
    cout << test.check(3) << endl;
    
    return 0;
}

Your code does not pass the test for 4. 4 should return true but returns false.

Approach 1: use a hashtable, O(1) to insert and O(n) to check
Approach 2: any form of sorted container, AVL, B-Tree, ... for O(lg(n)) insert and with vucuong020195 method to test

From the big-o 1) looks better, I'm not sure if that's really the case in real world - how ever, depends very much on the tree implementation, could be quite bad if with lots of pointers etc...

You could have used a HashSet to insert values in the data store.
In the test, you should have iterated over all the values of the HashSet and check if
(target - hashSet[i]) is present in the HashSet.
If yes, then return true or else return false.

The answer really depends on the frequency of operations and space:

* If test() is expected to be called more number of times than store(), then it is better to insert all combination of sums into unordered_set during store() itself. Each store operation would be O(n) to add all the numbers already stored with the input to store(). Then test() would be an O(1) operation.
* If store() is called more than test() (num stores > num tests), then insert the input to store() in unordered_set. Store() would be O(1), test would be O(n).
* If we have no additional space for unordered_set, make store() O(logN) by sorted insert and test() would be O(N).

- use a TreeSet - which ensures guaranteed ordering. inserts take O(log(n))
- for test - O(n) - dump it to an object list and use two pointers from first and last to get the sum. If no extra space need to be used then use containsKey method for each value of n. i.e. O(nlog(n))

import java.util.TreeSet;

public class TwoSumImpl {

    private TreeSet<Integer> cache = new TreeSet<Integer>();

    public void store(int input) {
        // store the elements in the TreeSet
        cache.add(input);
    }

    public boolean test(int val) {
        Object[] numbers = cache.toArray();
        int i = 0;
        int k = numbers.length - 1;
        while (i < k) {
            if (((Integer) numbers[i] + (Integer) numbers[k]) == val) {
                return true;
            } else if (((Integer) numbers[i] + (Integer) numbers[k]) < val) {
                i += 1;
            } else {
                k -= 1;
            }
        }
        return false;
    }

    public static void main(String... args) {
        TwoSumImpl twoSum = new TwoSumImpl();

        twoSum.store(1);
        twoSum.store(2);
        twoSum.store(3);
        boolean status = twoSum.test(4);
        if (status == true) {
            System.out.println("Verified the implementation");
        } else {
            System.out.println("Could not find the number");
        }
    }
}

I would use HahMap for O(n) complexity. So that for storing data it is O(1) and for testing it is O(n), as we can check the complement of the number.
{{ test - value(key-test) }}
for the length of hash keys

Filtering based on the difference. Slightly similar to a java solution suggested somewhere above.

// can be local or public
  val localStore = new ArrayBuffer[Int]
  def store(number: Int) = localStore.append(number)
  def test(newNumber: Int): Boolean = localStore.exists( number => localStore.contains(newNumber - number))

class TwoSum 
{
    std::unordered_map<int, bool> _store;
 
    public void Store(int input)
    {
    	_store[input] = true;
    } 

    public bool Test(int val)
    {
    	for(auto it = _store.begin(); it < _store.end(); it++)
    	{
    		int dif = val - it.first;
    		if (_store.find(dif) != _store.end())
    		{
    			return true;
    		}
    	}
    	
    	return false;
    }
}

class TwoSum {
	public:
		void Store(int n)
		{
			++map_[n];
		}
		bool Test(int sum)
		{
			for (auto el : map_) {
				int remainder = sum - el.first;
				auto it = map_.find(remainder);
				if (it != map_.end()) {
					if (remainder != el.first ||
						it->second > 1)
					{
						return true;
					}
				}
			}
			return false;
		}

	private:
		unordered_map<int, int> map_;
};