Programming Praxis

We looked at this problem, from the Google Code Jam Qualification Round Africa 2010, in a previous exercise:

Store Credit: You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first). For instance, with C=100 and L={5,75,25} the solution is 2,3; with C=200 and L={150,24,79,50,88,345,3} the solution is 1,4; and with C=8 and L={2,1,9,4,4,56,90,3} the solution is 4,5.

The solution we gave there used two nested loops to look at all combinations and return the first that solved the problems. That takes O(n²) time and O(1) space. But there are other solutions. You could insert each item into some flavor of balanced binary search tree in a first pass, then check the “conjugate” of each item in a second pass; that takes O(n log n) space for the tree plus O(n log n) for each of the two passes. Using a hash table instead of a balanced binary search tree reduces the time and space requirement to O(n), assuming that each hash table lookup is O(1), which is not necessarily true. A fourth option is to sort value/position pairs by increasing value, then use binary search to find matches; that takes O(n log n) for the sort plus O(n log n) for the binary searches, but requires only O(1) space beyond the space used for the input.

Your task is to write the four programs described above; bonus points for finding a solution with some other space/time complexity (is there an exponential algorithm that solves the problem?). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2