Amazon.com
3.4 of 5 2,812 reviews
www.amazon.com Seattle, WA 5000+ Employees

Amazon.com Software Design Engineer In Test Interview Question

I interviewed in Seattle, WA and was asked:
"given a sorted list of integers, how would you find whether 2 integers exist that add up to a given sum?"
Tags: complexity
Add Tags [?]
Answer Flag Question

Part of a Software Design Engineer In Test Interview Review - one of 4,152 Amazon.com Interview Reviews

Answers & Comments

0
of 0
votes
Here's a fairly simple solution in C# (certainly not the most efficient, but simple).

static bool sumOfTwo(int[] arr, int sum, ref int num1, ref int num2)
{
    int len = arr.Length;
    if (len < 2)
        return false;

    if ((arr[len - 1] + arr[len - 2] < sum) || (arr[0] + arr[1] > sum))
        return false;

    for (int i = 0; i < len; i++)
    {
        if (arr[i] + arr[len - 1] < sum)
            continue;

        for (int j = 0; j < len; j++)
        {
            if (i == j)
                continue;

            if (arr[i] + arr[j] == sum)
            {
                num1 = arr[i];
                num2 = arr[j];
                return true;
            }

            if (arr[i] + arr[j] > sum)
                break;
        }
    }
    return false;
}
- Dan on Sep 25, 2011 Flag Response
2
of 2
votes
Have two pointers one pointing to the beginning of Array and the other pointing to the end of array. Try to traverse the first pointer forward and the second one in reverse direction.
Eg:- Array -->123456789. Search for sum 9

1.P1 points to 1 , P2 points to 9
2.Add value(P1) + value(P2).
Compare with 9.
If the sum is equal, then these are the integers
If the sum is less, move P1 further but not P2
If the sum is more, move P2 further but not P1.
3.Do the step 2 till P1 is >= P2.

Advantages
1.This method takes good advantage of the fact that array is sorted
2.You can find out multiple pairs in one iteration
- Manju on Oct 6, 2011 Flag Response

To comment on this question, Sign In with Facebook or Sign Up


Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Amazon.com interview questions and advice. All interview reviews posted anonymously by Amazon.com employees and interview candidates.