Nimbula Interview Question: You are given a sorted array ... | Glassdoor

Interview Question

Senior Software Engineer Interview Mountain View, CA

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 ?

Interview Answer

1 Answer


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)

        if ((a[i] + a[j]) > sum) {

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

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

Interview Candidate on Mar 17, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.