Interview Question for Software Development Engineer I at Amazon.com:

Again, the general idea is to make one pass through the array and insert the numbers into a hash table. Then, on the second pass, compute the difference between n and the current value and search for it in the hash table. If it exists, those two form a pair. Repeated pairs were allowed (determined from clarifying question). O(n) time (2n specifically), O(n) space.