CareerCup

O(n) runtime and O(n) memory:

public boolean hasTwoNumbersThatSumValue(int[] arr, int num){
    if(arr == null){
        throw new NullPointerException();
    }

    HashSet<Integer> alreadyEncountered = new HashSet<Integer>();
    for(int i = 0; i < arr.length; i++){
        int val = arr[i];
        if(alreadyEncountered.contains(num-val)){
            return true;
        }
        alreadyEncountered.add(val);
    }
    return false;
}

Well zortlord, interviewer deliberately put "large" array in the question. It means that you cannot afford to have one more O(N) memory into RAM. here we have two approaches

1) use bitset for candidacy. It will use 1/32 memory than set or hashmap.
2) have a distributed hash table if you have N nodes. and distribute array values to arr[i]%N node. while traversing back again check into respective node for candidacy.

public boolean hasTwoNumbersThatSumValue(int[] arr, int num){
    if(arr == null){
        throw new NullPointerException();
    }

	// Sort begin,  the array, in increasing order
	//Sort end

	int left = 0;
	int right = arr.length;
	while(left < right) {
		int sum = arr[left] + arr[right];
		if(sum == num) {
			return true;
		}
		else if(sum < num) {
			left++;
		}
		else{
			right++;
		}
	}
	
	return false;
}

space O(n) if merge sort
or O(1) if quick sort

time O(nlogn)

public boolean hasTwoNumbersThatSumValue(int[] arr, int num){
    if(arr == null){
        throw new NullPointerException();
    }

	// Sort begin,  the array, in increasing order
	//Sort end

	int left = 0;
	int right = arr.length;
	while(left < right) {
		int sum = arr[left] + arr[right];
		if(sum == num) {
			return true;
		}
		else if(sum < num) {
			left++;
		}
		else{
			right--;
		}
	}
	
	return false;
}

I think you want to do right-- in below else condition

else{
			right++;
		}

This will take time O(n) and space O(n)

map<int,bool>m;
bool TwoNumbersThatSumValue(int a[],int num)
{
    for(int i=0;i<sizeof(a)/sizeof(a[0]),i++)
    {
        if(m[num-a[i]]==true)
        {
            return true;
        }
    }
    return false;
}
int main()
{
    int a[]={1,9,4,5};  //let us take this for example;
    int sum=14;        //Searching for sum==14
    for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
        m[a[i]]=true;
    TwoNumbersThatSumValue(a,sum);
}

This is an O(nlogn) Time complexity solution with O(1) space complexity

1. Sort the array
2. Take two indexes from start and end
3. If values of indexes is equal to sum, this is the answer
else if value is > sum, Move last index down
else as value < sum, move start index up.

This algorithm will change the array.

Ruby impl using Set. Running time: O(n). Space: O(n). In practice, it's more efficient to allocate enough space to a data structure in advance.

require 'set'

def two_numbers_sum_to_value_using_set(array, num) 
  return [] if !array.kind_of?(Array) || array.length<=1
  return array if array.kind_of?(Array) && array.length==2 && array[0]+array[1]==num
  
  set=Set.new(array)
  
  array.any? do |value|
    num-value != value && set.include?(num-value)
  end
end

array=[1,2,3,4,5,9,8,7,6]
puts "Two numbers? #{two_numbers_sum_to_value_using_set(array,13)}"

boolean hasTwoNumbersThatSumValue(int[] arr, int num) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = (i + 1); j < arr.length; j++) {
            if ((arr[i] + arr[j]) == num) {
                return true;
            }
        }
    }
    
    return false;
}