We pay for user submitted tutorials and articles that we publish. Anyone can send in a contribution
Learn MoreThe eleventh post of the series of programming job interview challenge is out. 75 readers provided answers to job interview challenge #10 and most of them had the correct solution. The correct answer as Alex, the first one to provide a detailed solution, wrote:
Here’s an O(N) solution:
Have one variable that stores the sum of all the values. Iterate through the list to add all numbers to the variable, which for simplicity I will call “listSum”.
Now, take the theoretical sum of all numbers between 1…n+1: This can be computed in O(1), as the sum of numbers up to N is n(n+1)/2: So for numbers up to n+1, it’d be (n+1)(n+2)/2 (for instance, if the array is of size 9, we’d do 10*(11)/2, or a theoretical sum of 55). Call this sum “allSum”.
The missing number will be the result of computing “allSum – listSum”.
O(N)complexity, with only two tracking variables.
Those are the bloggers who wrote their solutions in their blogs:
The commentators who got it right are:
David Poll, Michael Mrozek, Mark R, OJ, Edward Shen, ken, Thaison Lam, Shailendra, Simon Ask Ulsnes, pavan kumar, Kirill Sorokin, Florian K., Stephen Burton, Poul Foged Nielsen, Micha? Bendowski, Ivan Grasso, Marius Klimantavicius, thebol, steve_barham, Shams Mahmood, Samuel Williams, Sebastian U, Tim C, Hegi, NathanLaan, Guy Gervais, anton, Mori, Stephen Goldbaum, kranthi, ZagNut, Angelo vd Sijpt, krzysztof kreja, AS, Luke, Richard Vasquez, Christof Jans, Pavel, Randoom, Luca Giurina, Josh Bjornson, leppie, Kris Warkentin, cleg, grigri, Austinian, John, Martin, Jesus DeLaTorre, Hugh Brown, Michael, Tim Kington, Chris Jobson, JJ (it should be ((n+1)*(n+2)/2)), st0le, Guido Domenici, Michael Dikman and Frank D.
This Weeks Question:
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!
You can get updates by RSS so you catch up with the next posts in this series and get the correct answer to today’s question. As always you may post the solution in your blog or comment. Comments will be approved next week.
Tags :
Arraychallengejob interviewListquestionSum Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd
James Curran
Said on July 7, 2008 :
Are the numbers in the list unique? Or could we have (2,4,7,3,7) & 14 with the match being 7 & 7?
Shahar Y
Said on July 7, 2008 :
Hi James,
To make things less complicated, you can assume that the numbers in the list unique.
Alex
Said on July 7, 2008 :
The most time-efficient way would be to utilize a hashtable. (Or, simply a set if your language supports it)
Let’s take the example of searching for a sum 14
in the list 2,6,4,9,1,12,7.
Iterate through the list. For each value x in the list, add it to the hashtable, then check if 14-x exists in the hashtable. If not, go to the next item. if it does, return true (you found your pair). That “add to hashtable before checking” thing is necessary in order to prevent a 14-7=7 situation.
If you reach the end of the list without finding a matching pair, return false.
This algorithm is O(n) time, but also O(n) space.
The most space-efficient way is O(n^2) time, O(1) space:
For indexes 0,1,2,3,4,5, check 0&1…0&5,1&2…1&5, etc. A simple (14-list[i] == list[j]) comparison against every pair of elements evaluated will yield the results. Again, return when you find true, and if you make it all the way through the list without a match, return false.
Shams Mahmood
Said on July 8, 2008 :
Here’s my solution, assuming all integers in the input list are positive:
private boolean isMPresentInInput( final int[] input, final int m ) {
final boolean[] present = new boolean[m + 1];
for( int i = 0; i < input.length; i++ ) {
if( input[i] <= m ) {
present[input[i]] = true;
}
}
for( int i = 0; i < m / 2; i++ ) {
if( present[i] && present[m – i] ) {
return true;
}
}
return false;
}
Time: O(n + m)
Space: O(m)
Morgan Cheng
Said on July 8, 2008 :
Here is a time O(n*log(n)) and space O(1) solution:
The first step: sort the N-element list which takes O(n*log(n)) time complexity.
The second step: search two elements whose sum is M. Since the list is already sorted(smaller to the left and larger to the right), we find one number from left to right, while the other number from right to left. The index of left number is indexed by i, and the index of right number is indexed by j. For each step, we calculate delta = M – Array[i] and compare it to Array[j]. If delta equals Array[j], we can return true; if delta Array[j], we increment i and continue. When i >= j, we break and return false.
The C# code is like below:
static bool CheckSum(int[] numArray, int sum)
{
Array.Sort(numArray);
for (int i = 0, j = numArray.Length – 1; i numArray[j])
{
break;
}
else if (delta < numArray[j])
{
–j;
}
else // (delta == numArray[j])
{ return true;
}
} while (i < j);
}
return false;
}
Mark R
Said on July 8, 2008 :
The naive approach, O(n^2): for each number in the list, test each number further down the list; return true if they sum to m. When you reach the end of the list, return false.
A faster approach, O(n log n): sort the list using your favorite O(n log n) sorting algorithm. For each number list[i], subtract from m and return true if a binary search of the sublist list[i..n] finds this value. Return false when you have iterated to i>n, or list[i]*2 > m.
I hope this is the optimal solution, because it’s the best I would have done in the time allotted for an interview.
Kimmen
Said on July 8, 2008 :
The [first] solution I came up with is actually using a look-up table ;P, a hash table storing numbers. For each number, check if m – list[i] is in the look-up table. Return true if it is, else add the list[i] to the hash table.
This will end up with O(n) in both memory and time complexity. But I have no doubts there’s an algorithm with better memory complexity!
Tim
Said on July 8, 2008 :
My answer is here:
http://90kts.com/blog/2008/job-interview-question-11-summing-numbers/
In summary:
For now I am satisfied that a hash key search is the least complex way to deal with this particular challenge, with the only caveat being a ceiling limit on the amount of elements that are in your initial array to begin with e.g. 1 – 10,000 elements. For larger arrays, binary tree algorithms might offer better memory performance but would be more complex to implement in a scripting language like Ruby.
Kirill Sorokin
Said on July 8, 2008 :
I believe the below one is good enough both performance and memory-wise.
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
if (m – array[i] == array[j]) {
return true;
}
}
}
return false;
Maneesh
Said on July 8, 2008 :
A simple way to do so is to take the first element of the list(n[0]), subtract it from the result(m), suppose we get x=m-n[0], now if x is positive, we check whether x exists in the list, else we can move to the next element in the list.If x exists in the list, then return true. Repeat this process for all elements in the list. The worst case would be if the last element is a match or there is no match, in which case the complete list needs traversal . In order to optimize the search, we can sort the list and take only the elements which are lesser than the expected result and work with them. This ways the number of traversals can be lowered, although the sorting would entail its own cost, which can be minimized using a good sorting algorithm. I will be posting an implementation on my blog in a day or so.
Luca Giurina
Said on July 8, 2008 :
int find_copple_max(list_numbers *l, int m)
// return 0 if no copple of numbers > m, else 1
{
int max_first, max_second;
max_first = l->value;
l=l->next;
max_second = l->value;
l=l->next;
while ((l != NULL) || (max_first + max_second value > max_first)
max_first = l->value;
else if (l->value > max_second)
max_second = l->value;
l = l->next;
}
if (max_first + max_second > m)
{
printf(“%d + %d > %d”, max_first, max_second, m);
// Print result
return 1;
}
return 0;
}
Complexity is O(n) max (visit the complete list elements). Memory used: two int;
Heiko Hatzfeld
Said on July 8, 2008 :
You can find a blogpost here:
http://roadrunner74.wordpress.com/2008/07/08/dev-102-interview-challenge-11dev-102-interview-challenge-11/
Password is “foo”
I will unprotect it on monday.
Paul
Said on July 8, 2008 :
It seems to me that the answer I’d look for in a job applicant would be to subtract each number in n from m and check to see if the result was in n:
public bool DoesSumExist(List n, int m)
{
foreach (var number in n)
{
if (n.Contains(m – number)) return true;
}
}
That’s probably not the answer you’re looking for, but it’s applicable to an interview question, since I’d be looking for C# coders to work in a business environment where use of the tools (List) and keeping maintainability are important.
Dejan Dimitrovski
Said on July 8, 2008 :
Assuming we already have a binary search tree implemented, first insert all the nodes in the tree. Then start traversing through the nodes… If the node has a value greater then the sum that we are looking for then move to the next node on the left and ignore all the nodes on the right.
If the value is smaller then the sum we are looking for, start traversing further through the child nodes, check the sum of the current node value and the child node value, if smaller continue traversing, if not ignore the rest on the right.
Hard to express myself correctly in this small text-box but maybe i’ll blog about it later on if i have time
James Curran
Said on July 8, 2008 :
My solution (er..um… solutions)
http://honestillusion.com/blogs/blog_0/archive/2008/07/08/dev102-s-challenge-11-summing-numbers.aspx
Christof Jans
Said on July 8, 2008 :
static bool CanSum(int[] inputList, int m)
{
inputList = inputList.OrderBy(i => i).ToArray();
int minIdx = 0;
int maxIdx = inputList.Length – 1;
while (minIdx m) maxIdx–;
else minIdx++;
}
return false;
}
//complexity O(n)
Dan Sydner
Said on July 8, 2008 :
Assuming that m>n.
Fast version O(n) time, O(m) space:
Call the elements of the list x1…xn for each xi insert a 1 into an array, a, at index i. (Time O(n))
Iterate over the the elements and see if a[m-xi] == 1 and if so return true. (O(n) lookups that take O(1) time)
Slow version O(nlogn) time, O(n) space:
Sort the list (Time O(nlogn)) call. For each element xi in list do a binary search in the sorted list to see if m-xi exists. (O(n) lookups that take O(logn) time)
Xerxes
Said on July 8, 2008 :
Hi – i’ve posted my (probably quite wrong) solution and my (possibly even more wrong) proof on my blog:
http://www.xerxesb.com/2008/a-programming-job-interview-challenge-11-summing-numbers/
appreciate any feedback you could provide.
Alessio Spadaro AS
Said on July 8, 2008 :
Re-post, as today i got a wp-install page as a result, so i’m not sure it worked.
The first solution uses a HashSet to record the elements as it scans the array as follows:
hs = new HashSet
for each elem in array:
if hs.contains(m-elem) return true
hs.add(elem)
return false
contains and add are both constant time operations on an hashset, so we got O(n) for both execution time and memory.
The second approach sorts the array with a N*logN method (e.g. HeapSort) and then use two indexes to scan the sorted array like this:
sort(a)
h = 0
t = n-1
while (hm t-=1
if sum<m h+=1
return false
Doing so will result in a O(1) memory and O(NLogN) execution
Michael Mrozek
Said on July 8, 2008 :
I assume we’re not supposed to provide two algorithms, one for complexity and one for memory; the instructions are somewhat unclear.
Sort the list; there are many simple O(n log n) sorts including the one used by C++ in this code. Put pointers at the first and last nodes and sum them. If the sum is less than m, increase the low pointer; if it’s higher than m, decrease the high pointer; if it equals m, return true. Keep trying until the low and high pointers touch, then return false. This is O(n), so the overall complexity is still O(n log n). Memory usage is O(1) assuming the sort is in-place like this code. I’m suspicious that the problem asks for true/false instead of the actual numbers, but I can’t think of a way to lessen the complexity to take advantage of it.
bool check(int l [], const unsigned int lSize, const int m) {
std::sort(l, l + lSize);
int* start = l;
int* end = l + lSize – 1;
while(start != end) {
const int sum = *start + *end;
if(sum m) {
end–;
} else {
return true;
}
}
return false;
}
Jon
Said on July 8, 2008 :
private static bool Question(List n, int m)
{
bool result = false;
foreach (var i in n)
{
var list = new List(n);
list.Remove(i);
if (list.Contains(m – i))
{
result = true;
break;
}
}
return result;
}
C#: this should handle both a list that has a unique value of 7 (would return false when it sees only one 7), and a list that has 2 values of 7 (would return true because there are two values of 7).
Luca Giurina
Said on July 9, 2008 :
Sorry… little logic patch…
-while ((l != NULL) || (max_first + max_second <= m))
+while ((l != NULL) && (max_first + max_second <= m))
Luca!
Ronnie Hoogland
Said on July 9, 2008 :
IList numbers = new List() { 2, 6, 4, 9, 1, 12, 7 };
int m = 14;
var q = from a in numbers
from b in numbers
where (a + b) == m && a < b
select new { Number1 = a, Number2 = b };
foreach (var numberSet in q)
{
Console.WriteLine(“{0} {1}”, numberSet.Number1, numberSet.Number2);
}
Console.ReadLine();
Guido Domenici
Said on July 9, 2008 :
Here’s a solution that uses O(n) for storage (by using a hashtable) and has a complexity O(n). The idea is that you loop on the array and, on each iteration, if the hashtable contains the number that, added to the current one, yields the target number, then you got your solution:
bool PairExists (int[] nums, int target)
{
Dictionary foundNums = new Dictionary();
for (int i = 0; i < nums.Length; i++)
{
int addendumToFind = target – nums[i];
if (foundNums.ContainsKey(addendumToFind))
{
return true;
}
foundNums.Add(nums[i], true);
}
return false;
}
Michael
Said on July 9, 2008 :
Did not found anything better than BitArray. Instead of BitArray can be used hashtable, but it is overhead.
required memory is m/8
just one loop.
c#
using System;
using System.Collections;
public class MyClass
{
public static void Main()
{
Console.WriteLine(checkSum(new int[] {9, 2}, 5));
Console.WriteLine(checkSum(new int[] {5, 0}, 5));
Console.WriteLine(checkSum(new int[] {2, 2}, 4));
Console.WriteLine(checkSum(new int[] {5, 0, 2, 7 , 1, 9}, 5));
Console.WriteLine(checkSum(new int[] {7, 8, 9, 7 , 8, 9}, 14));
Console.WriteLine(checkSum(new int[] {}, 2));
Console.WriteLine(checkSum(new int[] {1, 2, 3, 4, 5, 7, 8}, 12));
Console.WriteLine(checkSum(new int[] {1, 2, 3, 4, 5, 7, 8}, 4));
Console.WriteLine(checkSum(new int[] {1, 2, 3, 4, 5, 7, 8}, 8));
Console.WriteLine(checkSum(new int[] {9, 2, 5, 4, 3, 2, 1}, 13));
}
public static bool checkSum(int[] numbers, int m)
{
BitArray myBits = new BitArray(m+1);
foreach (int i in numbers)
{
if (i <= m)
{
myBits[m – i] = true;
if (myBits[i])
{
return true;
}
}
}
return false;
}
}
Michael Dikman
Said on July 9, 2008 :
I will sort the n integers first in O(nlogn) complexity.
Then i will move with 2 pointers – one from the start (p1) and one from the end (p2) over these integers, with these rules:
If arr[p1] + arr[p2] m, advance p2
Do this until arr[p1] + arr[p2] = m, then return true
Or until p1 and p2 meet then return false;
(this can be done in recursion)
Space complexity is only 2 pointers.
lucas
Said on July 10, 2008 :
One silly solution.
Store the numbers in a Hashtable. than traversal the list , calc x=m-n[i], if hashtable[x]==true. then return true.
time complexity: o(n)
space complexity:o(n)
ZagNut
Said on July 10, 2008 :
In C#:
// O(n log n)
static bool TwoNumsInList(List numbers, int sum)
{
for (int i = 0; i < numbers.Count; i++)
for (int j = i; j < numbers.Count; j++)
if ((numbers[i] + numbers[j]) == sum)
return true;
return false;
}
Firefly
Said on July 13, 2008 :
This is a very easy problem if the list is unique
bool check(List list, int m)
{
//walk the list
foreach(var item in list)
{
if( l.Contains( m-item) )
return true;
}
return false;
}
Firefly
Said on July 13, 2008 :
since we are looking for i1+i2 = m where i1,i2 is some number in the list. So i2 = m-in
so all we need to do is check to see if list(n) contain i2.
It’s worth pointing out that the efficiency of my solution depend on the efficiency of the list.Contains method which also greatly depend on the type of the list.
Morgan Cheng
Said on July 14, 2008 :
switch (reader.NodeType)
{
case XmlNodeType.Element:
Console.Write(“”, reader.Name);
break;
case XmlNodeType.Text:
Console.Write(reader.Value);
break;
case XmlNodeType.CDATA:
Console.Write(“”, reader.Value);
break;
case XmlNodeType.ProcessingInstruction:
Console.Write(“”, reader.Name, reader.Value);
break;
case XmlNodeType.Comment:
Console.Write(““, reader.Value);
break;
case XmlNodeType.XmlDeclaration:
Console.Write(“”);
break;
case XmlNodeType.Document:
break;
case XmlNodeType.DocumentType:
Console.Write(“<!DOCTYPE {0} [{1}]”, reader.Name, reader.Value);
break;
case XmlNodeType.EntityReference:
Console.Write(reader.Name);
break;
case XmlNodeType.EndElement:
Console.Write(“”, reader.Name);
break;
}
Stephen Goldbaum
Said on July 14, 2008 :
Assuming non-unique and entries are added to themselves.
http://happyworldnoodle.com/blog1/2008/07/14/summing-numbers-challenge/
Stephen Goldbaum
Said on July 14, 2008 :
http://blog.happyworldnoodle.com/2008/07/14/summing-numbers-challenge/
Simplified my solution since the first post.
SS
Said on July 18, 2008 :
Please take care of integer overflow. I have improved method_2 over method_1.
public static int method_1(int [] sequence)
{
// this can overflow
int allSum = ((sequence.length + 1) * (sequence.length + 2)) / 2;
int seqSum = 0;
for (int i = 0; i < sequence.length; ++i)
{
// this can overflow
seqSum += sequence[i];
}
return allSum – seqSum;
}
/**
* @param sequence : Sequence of length N Contains integers 1 to (N + 1)
* with one number missing. The array is unsorted.
*
* @return The missing number
*/
public static int method_2(int [] sequence)
{
int missingNum = sequence.length + 1;
for (int i = 0; i < sequence.length; ++i)
{
missingNum += ((i+1) – sequence[i]);
}
return missingNum;
}
psychic attack
Said on July 16, 2011 :
What the heck are u talking about?! “A PROGRAMMING JOB INTERVIEW CHALLENGE #11 – SUMMING NUMBERS | Dev102.com”? I completely disagree! Where do you get your ideas from?