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.