In it’s 11th installment in a series of posts of interesting/quirky questions you may (or may not) be asked in a job interview, this series has definitely challenged everything I knew (or thought I knew) about computer science fundamentals and mathematical reasoning.
My response is to the 11th question about summing numbers is below:
PROBLEM:
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!
Answer
I suppose I will start by giving my answer first because it seems logical to me, and i’m generally better at providing solutions rather than the mathematical proof behind them 
Basically put, the most efficient way I can think of to determine if any of the numbers sum up to m is to work from left-right, subtract the current number from m, and then scan the rest of the list for the resulting number.
ie:
In a list consisting of the numbers 2,6,4,9,1,12,7 and m=14, my process will look like:
idx = 0
val = a[idx] (2)
searchFor = m - val (12)
Found 12 in the 5th position
Because you’re working from left to right, you don’t need to scan the array from the start every time, so on the first scan you’ll search through n – 1 elements, on the second scan you’l search through n – 2 elements and so on until you’re up to the last element in the array. According to the rules, there needs to exist 2 numbers which add up to m, so the last element CANNOT = m
I believe the most efficient way of scanning the list of values. Happy to be proven wrong I guess one optimisation would be to sort the elements of the array upfront, and then you can use a super-efficient sorted list scan algorithm, if you have a large array of elements. Also one of the commenters questioned whether duplication of numbers was/was not allowed – i see this point as irrelevant under this solution because 7 + 7 = 14, so why wouldn’t it be allowed?!
Reasoning
Here (for me) is where things start falling apart. I might have this totally wrong but i’ll give it a shot anyway….
Given m=14,
With List = 2, 6, 4, 9, 1, 12, 7 (ie: 7 elements in array)
The maximum complexity of the alg would be given by the maximum number of scans it would have to do to find the winning combination of numbers. In this example, it would be expressed as:
(1 * 7-1) + (1 * 7-2) + (1 * 7-3) + (1 * 7-4) + (1 * 7-5) + (1 * 7-6)
Again, we don’t worry about case 7-7 because there needs to exist 2 numbers which add up to m (and either way it’s a zero ;P)
Which roughly translates into:
6 + 5 + 4 + 3 + 2 + 1
Now substituting for n, we see it comes to
(n – 1) + (n – 2) + (n – 3) + … (n – (n – 2)) + (n – (n – 1))
which boils down to n(n+1)/2
So the maximum complexity of this solution would be O(n(n+1)/2)
This feels like such a hacky maths proof – my HS maths teacher would be livid…
Xerxes IT & Software Algorithms
