Interview Question for Software Engineer In Test at Google:

import java.util.NoSuchElementException;
import java.lang.IllegalStateException;

class PairWithSum {

    //O(n^2)
    static int[] findPairWithSum(int[] n, int sum){
        int index = indexLessThanSum(n, sum);

        for(int i = index; i>0; i--){
            for(int j = i-1; j>=0; j--){
                if(n[i] + n[j] == sum) return new int[] {n[i],n[j]};
                if((n[i] + n[j]) < sum) break;
            }
        }

        throw new NoSuchElementException("No such pair exists that sums up to the number "+ sum);
    }

    //O(log n)
    static int indexLessThanSum(int[] n, int sum){
        if(sum < n[0])
            throw new NoSuchElementException("The smallest element in the given list of numbers is bigger than the given sum ");

        int i = n.length-1;
        while(i>0 && n[i]>sum){
            int s = i / 2;
            if(n[s]<sum){//now search for a bigger number
                int e = s;
                int d = 1;

                while(d > 0 && e<i){

                    if(n[e]<sum){
                        s = e;
                        d = (i - e) / 2;
                        e = e + d;
                        }
                    else{
                        i = e;
                        d = (e - s) / 2;
                        e = e - (d==0?1:d);
                        }
                }

                return e;

            }
            i = s;
        }

    return i;
    }

    public static void main(String args[]){
        int sum = Integer.valueOf(args[0]);
        int[] n = findPairWithSum(new int[]{1,2,4,5,6,7,8}, sum);
        System.out.format("%1$d + %2$d = %3$d %4$n", n[0], n[1], sum);
    }

}

OUTPUT:
> java PairWithSum 13
8 + 5 = 13

> java PairWithSum 6
5 + 1 = 6

> java PairWithSum 20
Exception in thread "main" java.util.NoSuchElementException: No such pair exists that sums up to the number 20

>java PairWithSum 0
Exception in thread "main" java.util.NoSuchElementException: The smallest element in the given list of numbers is bigger than the given sum