Thursday, November 19, 2015

LinkedIn: Two Sum

Question:
public interface TwoSum {
   /**
    * Stores @param input in an internal data structure.
    */
   void store(int input);
   /**
    * Returns true if there is any pair of numbers in the internal data structure which
    * have sum @param val, and false otherwise.
    * For example, if the numbers 1, -2, 3, and 6 had been stored,
    * the method should return true for 4, -1, and 9, but false for 10, 5, and 0
    */
   boolean test(int val);

}

Code (Java):
public class searchTwoSum implements TwoSum {
    Map<Integer, Integer> map = new HashMap<>();
    
    void store(int input) {
        if (!map.containsKey(input)) {
            map.put(input, 1);
        } else {
            int freq = map.get(input);
            map.put(input, freq + 1);
        }
    }
    
    boolean test(int val) {
        for (int num1 : map.keySet()) {
            int num2 = val - num1;
            // 0 + 0 = 0
            
            if (num1 == num2 && map.get(num1) >= 2) {
                return true;
            }
            
            if (num1 != num2 && map.containsKey(num2)) {
                return true;
            }
        }
        
        return false;
    }
}

Complexity analysis:
store: O(1)
test: O(n).


Follow up: what if we need to speedup the test process?
The solution is when we store an element, we could also store the sum of the current number with all previous numbers. Then in the test, we only need to check if the sum exists.

Code (Java):
public class FasterSearchSum implements TwoSum {
    Set<Integer> set = new HashSet<>();
    List<Integer> nums = new ArrayList<>();
    
    public void store(int input) {
        if (!nums.isEmpty()) {
            for (int num : nums) {
                set.add(input + num);
            }
        }
        
        nums.add(input);
    }
    
    public boolean test(int val) {
        return set.contains(val);
    }
}


No comments:

Post a Comment