CareerCup

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		TwoSumImpl obj = new TwoSumImpl();
		obj.store(1);
		obj.store(-2);
		obj.store(3);
		obj.store(6);
		
		System.out.println("test val " + 4 + " result " + obj.test(4));
		System.out.println("test val " + -1 + " result " + obj.test(-1));
		System.out.println("test val " + 9 + " result " + obj.test(9));
		System.out.println("test val " + 10 + " result " + obj.test(10));
		System.out.println("test val " + 5 + " result " + obj.test(5));
		System.out.println("test val " + 0 + " result " + obj.test(0));

	}
}

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);
}

class TwoSumImpl implements TwoSum{
	
	ArrayList<Integer> list = new ArrayList<Integer>();
	public void store(int input){
		list.add(input);
	}
	
	public boolean test(int val){
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(Integer input: list){
			map.put(input, 1);
		}
		for(Integer input: list){
			if(map.containsKey(val - input))
				return true;
		}
		return false;
	}
}

Run binary search. For input [1,-2,3,6], sort it first,
test(4) {
for each element i in the array
binary search (4 - i);
}

Hey, what is the run-time of your algorithm?

What complexity were they expecting for this question?

Its in a way similar to this question. Here the sum is the input http://www.careercup.com/question?id=5727163577794560

There is a bug in the above implementation.
This function will return true for input set [1,2,3 ] and testing for value 2.

There is no need to using HashMap for randomCoder1988 solution

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Solution
{
public static void main (String[] args) throws java.lang.Exception
{
TwoSumImpl obj = new TwoSumImpl();
obj.store(1);
obj.store(-2);
obj.store(3);
obj.store(6);

System.out.println("test val " + 4 + " result " + obj.test(4));
System.out.println("test val " + -1 + " result " + obj.test(-1));
System.out.println("test val " + 9 + " result " + obj.test(9));
System.out.println("test val " + 10 + " result " + obj.test(10));
System.out.println("test val " + 5 + " result " + obj.test(5));
System.out.println("test val " + 0 + " result " + obj.test(0));

}
}

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);
}

class TwoSumImpl implements TwoSum{

ArrayList<Integer> list = new ArrayList<Integer>();
public void store(int input){
list.add(input);
}

public boolean test(int val){
for(Integer in : list) {
if(list.contains(val - in.intValue()))
return true;
}

return false;
}
}

1) Go through the list and store every possible sum in a hash table. O(n^2) preprocessing step and O(1) look up each time method is called. O(n) space.
2) Go through list and store every element in hash table. O(n) preprocessing step and O(n) look up each time method is called. O(n) space. --> for each element, is value minus element in hash map?
3) Sort the list as preprocessing step, O(nlogn). Use 2 pointers to go through list from both ends, incrementing left pointer if sum is too low, and decrementing right pointer if sum is too high, O(n). Space O(1).

public class TwoSum {
    /**
     * Stores @param input in an internal data structure.
     */
    Map<Integer, Integer> storeMap = new HashMap<Integer, Integer>();
    public void store(int input) {
        //if the input value exists in the map
        if (storeMap.containsKey(input)) {
            storeMap.put(input, storeMap.get(input) + 1);
        } else {
            storeMap.put(input, 1);
        }
    }

    /**
     * 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
     */
    public boolean test(int val) {
        for (Integer currVal : storeMap.keySet()) {
            Integer otherNumber = val - currVal;
            //if the map contains the other number
            if (storeMap.containsKey(otherNumber)) {
                if (otherNumber.equals(currVal)) {
                    //If the number is the same as current, then check if another number exists
                    Integer count = storeMap.get(currVal);
                    //another same number exists
                    if (count > 1) {
                        return true;
                    }
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TwoSum twoSum = new TwoSum();
        twoSum.store(1);
        twoSum.store(-2);
        twoSum.store(3);
        twoSum.store(6);
        twoSum.store(6);

        System.out.println("Test " + twoSum.test(4));
        System.out.println("Test " + twoSum.test(-1));
        System.out.println("Test " + twoSum.test(9));
        System.out.println("Test " + twoSum.test(12));
        System.out.println("Test " + twoSum.test(10));
        System.out.println("Test " + twoSum.test(5));
        System.out.println("Test " + twoSum.test(0));
    }
}

public class TwoSum {
    /**
     * Stores @param input in an internal data structure.
     */
    Map<Integer, Integer> storeMap = new HashMap<Integer, Integer>();
    public void store(int input) {
        //if the input value exists in the map
        if (storeMap.containsKey(input)) {
            storeMap.put(input, storeMap.get(input) + 1);
        } else {
            storeMap.put(input, 1);
        }
    }

    /**
     * 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
     */
    public boolean test(int val) {
        for (Integer currVal : storeMap.keySet()) {
            Integer otherNumber = val - currVal;
            //if the map contains the other number
            if (storeMap.containsKey(otherNumber)) {
                if (otherNumber.equals(currVal)) {
                    //If the number is the same as current, then check if another number exists
                    Integer count = storeMap.get(currVal);
                    //another same number exists
                    if (count > 1) {
                        return true;
                    }
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TwoSum twoSum = new TwoSum();
        twoSum.store(1);
        twoSum.store(-2);
        twoSum.store(3);
        twoSum.store(6);
        twoSum.store(6);

        System.out.println("Test " + twoSum.test(4));
        System.out.println("Test " + twoSum.test(-1));
        System.out.println("Test " + twoSum.test(9));
        System.out.println("Test " + twoSum.test(12));
        System.out.println("Test " + twoSum.test(10));
        System.out.println("Test " + twoSum.test(5));
        System.out.println("Test " + twoSum.test(0));
    }
}

protocol TwoSumProtocol {
    func store(val: Int)
    func test(val: Int) -> Bool
}

// optimized for Insert

class TwoSum: TwoSumProtocol {
    
    var values = Set<Int>()
    
    func store(val: Int) {
        values.insert(val)
    }
    
    func test(val: Int) -> Bool {
        for value in values {
            let difference = val - value
            if values.contains(difference) {
                return true
            }
        }
        return false
    }
}


//Optimized for GET

class TwoSum: TwoSumProtocol {
    
    var values = Set<Int>()
    var sums = Set<Int>()
    
    func store(val: Int) {
        for value in values {
            sums.insert(value + val)
        }
        values.insert(val)
    }
    
    func test(val: Int) -> Bool {
        return sums.contains(val)
    }
}

protocol TwoSumProtocol {
    func store(val: Int)
    func test(val: Int) -> Bool
}

// optimized for Insert

class TwoSum: TwoSumProtocol {
    
    var values = Set<Int>()
    
    func store(val: Int) {
        values.insert(val)
    }
    
    func test(val: Int) -> Bool {
        for value in values {
            let difference = val - value
            if values.contains(difference) {
                return true
            }
        }
        return false
    }
}


//Optimized for GET

class TwoSum: TwoSumProtocol {
    
    var values = Set<Int>()
    var sums = Set<Int>()
    
    func store(val: Int) {
        for value in values {
            sums.insert(value + val)
        }
        values.insert(val)
    }
    
    func test(val: Int) -> Bool {
        return sums.contains(val)
    }

}

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

public class TwoSumA implements TwoSum {
	private int[] arr; 
	private int length;
	private Set s; 
	
	public TwoSumA(){
		this.arr = new int[50]; 
		this.length = 0; 
		this.s = new HashSet<Integer>() ;  
	}
	public void store(int input ){
		arr[length] = input; 
		length ++; 
		for(int i = 0 ;i <= length -1; i ++){
			s.add(new Integer(input + arr[i])) ; 
		}
		
	}
	
	
	public boolean test(int val){
//		for( int i = 0 ; i <= length - 1; i ++){
//			for( int j = 0; j <= length - 1; j ++){
//				if( arr[i] + arr[j] == val)
//					return true; 
//			}
//		}
//		return false; 
		
		if( s.contains(new Integer(val))) return true; 
		else return false; 
	}
}

Here is C++ version of solution.
If I can use the hashtable with load factor close to 1. This algorithm will run in O(N) where N is the number of elements in the hashtable.
In this solution, I used map, which gives O(log N) search time.
Therefore, the running time is O( N log N).

#include <map>
#include <iostream>
using namespace std;

class TwoSum {
public:
	void store(int input)
	{
		if (hashtable.find(input) == hashtable.end())
		{
			hashtable[input] = input;
		}
	}

	bool test(int val)
	{
		map<int, int>::iterator iter;
		for (iter = hashtable.begin(); iter != hashtable.end(); iter++)
		{
			int cur = iter->second;
			int left = val - cur;
			if (hashtable.find(left) != hashtable.end())
				return true;
		}
		return false;
	}
private:
	map<int, int> hashtable;
};