Nimbula

  nimbula.com
Work in HR? Unlock Free Profile

Nimbula Senior Software Engineer Interview Question

I interviewed in Mountain View, CA and was asked:
"You are given a sorted array of integer. Describe an algorithm that finds two numbers in that array whose sum equals a given number. What's the complexity of your algorithm ? Can you do better ?"
Add Tags [?]
Answer

Part of a Senior Software Engineer Interview Review - one of 5 Nimbula Interview Reviews

Answers & Comments

0
of 0
votes

1. You can do a brute force search using two nested inner loops. This will have the complexity of O(n^2) and is probably not what they expect from you.

2. Add the first and last number (use two indexes). If this is smaller than the given number there is no solution. If it is bigger then decrease the index of the last number until the sum is bigger than or equal to the given number. If the sum becomes smaller than the given number start increasing the left index until the sum is smaller or equal to the given number.

The complexity of this solution is O(n). Program attached.

3. I think there is also a O(log n) solution based on solution number 2 where you do the searches in the left and right side of the array in a binary search fashion.

int main()
{
    int a[] = {2, 5 , 7, 10, 15, 23, 26, 30, 36, 39, 42, 47, 55};
    int sum = 49;
    int i, j, k;
    size_t sizeofa = sizeof(a)/sizeof(a[0]);
    bool found = false;

    i = 0;
    j = sizeofa - 1;

    while (!found) {
        if (i >= j)
            break;

        if ((a[i] + a[j]) > sum) {
            j--;
            continue;
        }

        if ((a[i] + a[j]) < sum) {
            i++;
            continue;
        }

        printf("i = %d j = %d\n", i, j);
        i++;
        j--;
        //found = true;
    }
}

- Interview Candidate on Mar 17, 2011

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.