CareerCup

Same as two sum interface :

package com.careercup.linkedin;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by nileshagrawal on 11/18/16.
 */
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;
    }
}

Can you provide some samples?

This is a very straight-forward question concerning Hash tables. The only tricky part that I can see is that you have to know if a number has appeared twice (so that you can computer the sum of "number + number").

In Java, I would use a HashMap to keep track of the inputs (key=the number, value=how many times that number has been seen).

I would then have a HashSet for the sums. That way, isNumberPresent() is a trivial implementation -- it just has to look to see if the number is present in the HashSet.

When implementing store(), you first have to check to see if the number is already in your map. If it isn't, you put a 1 in the map for that number. If it is, then you increment the existing count.

Then, check to see how many times this number has been encountered. If it's "count > 2", nothing has to be done. If it's "count == 2", then you just have to compute the sum of "number + number". If it's "count == 1", then you have to execute a for loop and compute the sum of this number with every other number in the HashMap (except for the number itself).

Assumptions:
There can be number duplicates. The numbers fit in memory
The isPresent signature is isPresent(sum, i) - If i is present in sum.

The idea is to store all the distinct numbers in a set. Store the sum as well in the set.
Since this is a online algorithm, we can loop through all the existing numbers and add to the new number and put it in the set.

when is present is called, then check the sum exists in SumSet, check i is present in storage and sum - i is present in the storage.

import java.util.HashSet;
import java.util.Set;

public class OnlineNumberPairs {
	
	public static void main(String[] args) {
		INumber number = new NumberImpl();
		number.insert(-1);
		number.insert(1);
		number.insert(0);
		number.insert(2);
		number.insert(3);
		number.insert(4);
		number.insert(1);
		System.out.println(number.isPresentInPairSum(2, 1));
		System.out.println(number.isPresentInPairSum(2, 2));
		System.out.println(number.isPresentInPairSum(5, 2));
		System.out.println(number.isPresentInPairSum(5, 4));
	}
	
	private static interface INumber {
		
		public void insert(int i);
		
		public boolean isPresentInPairSum(int sum, int i);
	}
	
	private static class NumberImpl implements INumber {
		
		private Set<Integer> storage;
		
		private Set<Integer> sumSet;
		
		public NumberImpl() {
			storage = new HashSet<Integer>();
			sumSet = new HashSet<Integer>();
		}

		@Override
		public void insert(int i) {
			storage.add(i);
			for(Integer in: storage) {
				sumSet.add( i + in );
			}
		}
		
		public boolean isPresentInPairSum(int sum, int i) {
			return sumSet.contains(sum) && storage.contains(i) && storage.contains( sum - i);
		}
		
	}
}

Store incoming numbers in balanced binary search tree.
IsNumberPresent, go through each node, find difference and search for difference in BST.

Space complexity O(N) and time complexity O(N * logN)

Question makes you think that you need to store computed sum, problem with that approach is, its N^2 solution to store a number, no matter which data structure you chose to store.