Java Interview Problems

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.

Example 1:

add(3); add(5); add(8);
find(8) -> true
find(4) -> false

Solution

class TwoSum {
    List<Integer> list;
    boolean isSorted=true;
    public TwoSum() {
        list = new ArrayList<>();
    }     
    public void add(int number) {
        list.add(number);
        isSorted=false;
    }   
    public boolean find(int value) {
        if(!isSorted){
            Collections.sort(list);
        }
        int leftPtr = 0;
        int rightPtr = list.size()-1;
        while(leftPtr < rightPtr){
            int sum = list.get(leftPtr)+list.get(rightPtr);
            if(sum == value){
                return true;
            }else if(sum < value){
                leftPtr++;
            }else{
                rightPtr--;
            }
        }
        return false;
    }
}