Nimbula

nimbula.com
nimbula.com

## 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 ?

0

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