1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/.hgignore	Fri May 01 16:28:22 2015 -0500
     1.3 @@ -0,0 +1,2 @@
     1.4 +.*~
     1.5 +a\.out$
     1.6 \ No newline at end of file

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/two_sum/two_sum.cpp	Fri May 01 16:28:22 2015 -0500
     2.3 @@ -0,0 +1,45 @@
     2.4 +// Problem: given an input array of numbers, and a target value, find two numbers
     2.5 +// in the input which sum to the target value.  Do so with worst case performance
     2.6 +// of O(N).
     2.7 +
     2.8 +// Solution: add the input numbers to a hash as they are read, with the number
     2.9 +// as the hash key, and it's index position in the input as the hash value.
    2.10 +
    2.11 +// At each step we can do an O(1) lookup in the hash to see if target - num has
    2.12 +// already been added to the hash.  If it has, we terminate processing and print
    2.13 +// the two numbers (along with their indices).  Otherwise we add num to the hash
    2.14 +// and loop back to read the next input number.
    2.15 +
    2.16 +// Overall performance is O(N) in the worst case, since in that case we must
    2.17 +// process each input item exactly once.  (For each item, we perform one lookup
    2.18 +// into the hash, which adds only a small constant to the running time per
    2.19 +// iteration of the loop.)
    2.20 +
    2.21 +// Usage: Pass the target value as a command line option, and the number array as
    2.22 +// values on stdin, one item per line.
    2.23 +
    2.24 +#include <map>
    2.25 +#include <string>
    2.26 +#include <cstdlib>
    2.27 +#include <iostream>
    2.28 +
    2.29 +int main( int argc, char **argv ) {
    2.30 +    char *endptr = NULL;
    2.31 +    long target = strtol( argv[1], &endptr, 10);
    2.32 +
    2.33 +    long lookfor, num, index = 0;
    2.34 +    std::map<long, long> hash;
    2.35 +    std::map<long, long>::const_iterator iter;
    2.36 +    std::string s;
    2.37 +
    2.38 +    while ( std::cin >> s ) {
    2.39 +        num = strtol( s.c_str(), &endptr, 10);
    2.40 +        lookfor = target - num;
    2.41 +        if ( ( iter = hash.find(lookfor) ) != hash.end() ) {
    2.42 +            std::cout << num << " " << lookfor << " (indices " << index << ", " << (*iter).second << ")" << std::endl;
    2.43 +            exit(EXIT_SUCCESS);
    2.44 +            }
    2.45 +        hash[num] = index++;
    2.46 +        }
    2.47 +    exit(EXIT_FAILURE);
    2.48 +    }