CareerCup

The idea is to use a hashtable or a set for this problem. When the store is called, we store all the numbers into the set. This gives us constant O(1) access time. When we are testing whether the target exists in the set, we simply compute its complement and check whether it exists in the set which amounts to O(n) time complexity. I present my solution in Python below:

Solution:

class StoreNums:
  def __init__(self):
    self.numSet = set()

  # TC:- O(1) since we are using a hashable set
  def store(self, num):
    if num in self.numSet:
      return False
    else:
      self.numSet.add(num)
      return True

  # TC:- O(n) where n = number of nums stored
  def test(self, target):
    for num in self.numSet:
      complement = target - num
      if complement in self.numSet:
        return True
    return False

Test code:

# Test code
s = StoreNums()
print(s.store(1)) # True
print(s.store(3)) # True
print(s.store(5)) # True
print(s.store(3)) # False
print(s.store(6)) # True
print(s.test(4)) # True
print(s.test(5)) # False
print(s.test(6)) # True

Using a red black tree means you can perform lookups in guaranteed O(log n ) time, and java has a very nice TreeSet data structure which is a RBT with floor(Key key) and contains(Key key) methods already defined on it. Ive included my code below, works as expected with Test inputs and has running time O(log n) for test

import java.util.TreeSet;

public class Solution {
  static private TreeSet<Integer> dataStore = new TreeSet<>();
  
  public void store(int num){
    dataStore.add(num);
  }

  public boolean test(int targetSum) {
	// since it says sum of two numbers we dont even need a loop.
    int l = dataStore.floor(targetSum); // l returns 3
    int diff = targetSum - l; // we subtract and look to see if there is a hit. 
    return dataStore.contains(diff);
  }
}