Monday, August 24, 2015

Leetcode: Two Sum III - Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Understand the problem:
The problem asks for designing a class TwoSum which supports two operations, add and find. There are two data structures / design decisions to think about. 
 1. Use two pointers. Requires the list to be sorted. 
       -- add: insert an element to a sorted array requires O(logn) + O(n) time. 
       -- find: use two pointers. Takes O(n) time. 

2. Use a hash map. 
       -- Add takes O(1) time. 
       -- Find takes O(n) time. 

Note that we have to use  the map instead of the set because we need to counter the number of duplicates for a number. e.g. add(0), add(0) and find(0). 

Code (Java):
public class TwoSum {
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
 public void add(int number) {
     if (map.containsKey(number)) {
         int val = map.get(number) + 1;
         map.put(number, val);
     } else {
         map.put(number, 1);
     }
 }

 public boolean find(int value) {
     if (map.isEmpty()) {
         return false;
     }
     Iterator it = map.entrySet().iterator();

     // Itearte over the set
     while (it.hasNext()) {
         Map.Entry pair = (Map.Entry) it.next();
         int firstKey =  (int) pair.getKey();
         int firstValue = (int) pair.getValue();
         
         int secondKey = value - firstKey;
         
         // 0 + 0 = 0
         if (firstKey == secondKey && firstValue >= 2) {
             return true;
         }  else if (firstKey != secondKey && map.containsKey(secondKey)) {
             return true;
         }
     }
     return false;
 }
}

Follow-up: 
What if you add a few, but search very heavily? You need to make sure search only takes O(1) time. Add(num), add num with all the previous added numbers 
search(target), only takes O(1) time. 

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