Dev 102 Interview Challenge 11

 

This weeks question on „Dev102“ is:

 

Given a list of n integers and another integer called m, determine (true / false) if there exist 2 numbers in that list which sum up to m.
Example: 2,6,4,9,1,12,7 and m=14 -> 2 and 12 sum up to 14, so the answer is true.
Provide the best algorithm in both manners: performance and memory to solve this puzzle. Don’t forget to mention the complexity of your solution!

 

So lets take a look at the different options we have…

 

The naïve approach would be to check every number with every other number. This would lead to N * (N-1) / 2 checks to find all possible combinations. And as you most likely guessed it, this is not the optimal approach.

 

So how can this be improved?

 

My 1^st thought is again by sorting the input and the testing it more logically. I am still trying to wrap my mind around a solution that does not require me to sort the list, but it seems like this time there is no way around it.

 

So how would you test this more logically?

 

Since we now operate on a sorted list, we know that if we exceed the test for 2 given numbers in the list, then we can eliminate all further tests for that “row”. We close in from both sides until we found it.

 

Basically we can construct a result matrix that is also sorted, and by testing only the relevant points in this matrix we can eliminate all unneeded tests. For example the List { 5,8,11,15,23,25,29} would result in a Matrix like this:

 

i	5	8	11	15	23	25	29
1	13	16	20	28	30	34
2		19	23	31	33	37
3			26	34	36	40
4				38	40	44
5					48	52
6						54
j ->	2	3	4	5	6	7

 

 

If we start with j = max and i = 1, we could zero in on the target number quite fast.

 

 

 

 

For example if we look for 35 in the matrix (Which does not exist) we would have to do the following tests: (orange = to low, red = to high, green = eliminated since impossible)

 

5	8	11	15	23	25
13	16	20	28	30	34
	19	23	31	33	37
		26	34	36	40
			38	40	44
				48	52
					54

 

 

The actual source for this problem is:

 

        private bool findPair(int[] data, int target)

        {

            Array.Sort(data);

            int i = 0;

            int j = data.GetUpperBound(0);

 

            while(i<j)

            {

                int current = data[i] + data[j];

                if (current > target)

                    j -= 1;

                else if (current < target)

                    i += 1;

                else

                    return true;

            }

            return false;

        }

 

 

You could also add an additional test at the beginning, that validates that there is a possible solution at all (checking if the 2 biggest numbers in the sorted list are bigger then the target number) But this would depend on the actual data that has to be processed. If that happens a lot, then you could even move this test to the pre-sort stage and simplify it to target < 2 * maxValueInList.

 

The overall complexity for this problem would be the cost of sorting + O(N).

 

~ by Heiko Hatzfeld on July 8, 2008.