Interview Questions: Two Sum

In interviews for programming positions, it is common for the interviewer to present a small programming problem and see what kind of solution the candidate comes up with. These problems help to reveal how the candidate thinks about solving problems, and also provide a chance to show basic coding competency. These problems can also be fun to work in their own right as exercises in the craft of software design.

The two sum problem is simple version of the more general (and NP complete!) subset sum problem. Two sum can be stated as follows:

Given an input array of numbers, and a target value, find all pairs of numbers in the input which sum to the target value.

There are various solutions possible, of course.  Naively, one might consider iterating over all elements of the array, and for each element, iterating over the other elements to see if the pair add up to the sum. This leads to a solution that runs in O(N2) running time, though, which is clearly not desirable for large inputs.

A first pass at improving the performance would be to consider sorting the data.  We can then use binary search to quickly see if a number’s compliment is also in the set.

Solution: Sort the input data.  For each value in the array, use binary search to see if (target – value) is also in the array, and if so print the pair of numbers.  We need not consider values greater that target/2 since the the data is sorted, and (target – value) would have already been checked.

Time performance is O(N log N) for the lookup, and varies for the sort, though typically it is also O(N log N) giving O(N log N) overall performance. Space complexity if O(1), though, since no extra space is needed for the operations.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

long binary_search( std::vector<long> vec, long lookfor, long min, long max ) {
    while ( max >= min ) {
        long mid = min + (max – min) / 2;
        if ( vec[mid] == lookfor )
            return mid;
        else if ( vec[mid] > lookfor )
            max = mid – 1;
        else
            min = mid + 1;
        }
    return -1;
    }

void two_sum( std::vector<long> vec, long target ) {
    std::sort( vec.begin(), vec.end() );

    long lookfor;
    long i = 0;
    while ( vec[i] <= target/2 ) {
        lookfor = target – vec[i];
        long pos = binary_search( vec, lookfor, 0, vec.size()-1 );
        if ( pos != -1 && pos != i ) {
            std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << pos << ")" << std::endl;
            }
        i++;
        }
    }

int main( int argc, char **argv ) {
    char *endptr = NULL;
    long target = strtol( argv[1], &endptr, 10);

    std::vector<long> vec;
    long num;
    std::string s;

    while ( std::cin >> s ) {
        num = strtol( s.c_str(), &endptr, 10);
        vec.push_back(num);
        }

    two_sum( vec, target );

    exit(EXIT_SUCCESS);
    }
 

 

This is good, but if we are willing to use more memory, we can improve the speed of processing in a classic time-memory trade off.

Solution: Add the input numbers to a hash with the number as the hash key, and it’s index position in the input as the hash value. For each value in the array, check to see if (target – value) is also in the hash and if so print the pair of numbers.  We need not consider values greater than target/2 since this would generate a duplicate pair when we eventually come across (target – value) itself in the array.

We are using an extra O(N) amount of memory for the hash table, but doing so gives us O(1) lookup time to see if (target – value) is also in the array, so once the hash is built in O(N) time we need only another O(N) amount of time to find all pairs, yielding an overall O(N) running time.

#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <vector>

void two_sum( std::vector<long> vec, long target ) {
    std::map<long, long> hash;

    for ( long i=0; i < vec.size(); i++ ) {
        hash[vec[i]] = i;
        }

    long lookfor;
    long i = 0;
    std::map<long, long>::iterator it;
    while ( i < vec.size() ) {
        if ( vec[i] <= target/2 ) {
            lookfor = target – vec[i];
            if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).second != i ) ) {
                std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << (*it).second << ")" << std::endl;
                }
            }
        i++;
        }
    }

int main( int argc, char **argv ) {
    // Same as above.
    }
 

 

If you’d rather not read C++, here is a Perl version of the hash based algorithm that stops after finding the first matching pair of numbers.

#!/bin/env perl

use strict;
use warnings;
use Data::Dumper;

# Usage: Pass the target value as a command line option, and the number array as
# values on stdin, one item per line.

my $target = $ARGV[0];
my $lookfor;
my $num;
my $i = 0;
my %h;
while () {
    $num = $_;
    chomp($num);
    $lookfor = $target$num;
    if ( exists $h{$lookfor} ) {
        print "$num $lookfor (indices $i, ".$h{$lookfor}.")\n";
        exit(0);
    }
    $h{$num} = $i;
    $i++;
}
exit(1);

 

References