__Pairs From a List That Match a Sum__

This code sample came from an interview question I was asked recently, to test my
optimization skills. The problem was: given an arbitrary list of integers, print
out each pair within the list that sum up to a given value. The idea was to come
up with a 0(n) complexity solution (one that requires only a single pass through
the list).

During the interview, I figured out most of the problem, despite having never seen
it before. However, I lost points for not making one of the basic assumptions
this problem requires: assume the list is sorted. I actually considered this
during the interview, but rejected it, since this was not specified by "the
customer" (aka. the interviewer) until he suggested it to me. I felt I could not
make that assumption without it being stated as part of the problem, and thus, at
first, could only come up with a n squared solution (compare every element in the
list against every other element). Once I knew the list was sorted, however, other
optimizations were possible.

After the interview, I wrote it up as a Java class and began experimenting with
the problem. I decided to come at the problem with no other assumptions (for
example, the interviewer allowed the assumption that every integer in the list was
unique... no repeats. I decided to not allow that assumption, which made the
problem more complex, though the basic solution still worked).

Get the full source code for it here:
SumPairList_DPL.zip (8 Kb)

To learn more about the games I've worked on, go to
my Games Page.

To go to my website, go to
OpusGames.com.