1. Given k sorted streams where each stream could possibly be infinite in length, describe an efficient algorithm to merge the k streams into a new stream (also in sorted order).

2. Given a set of KEY->VALUE pairs such that each KEY is unique, describe a method of storing these pairs on disk, and a method for accessing the corresponding VALUE given a KEY. Assume that RAM is fixed at 1gb and the set of pairs requires 40gb. (Hint: Try to minimize page-transfers.)

3. Given N computers networked together, with each computer storing N integers, describe a procedure for finding the median of all of the numbers. Assume that a computer can only hold O(N) integers (i.e. no computer can store all N^2 integers). Also assume that there exists a computer on the network without integers, that we can use to interface with the computers storing the integers.

4. Given the sequence S1 = {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence S2 = {1,2,3,4,….} Write code to convert an element of S1 to the corresponding element of S2. Write code to convert an element of S2 to the corresponding element of S1.

5. Given a binary tree with the following constraints:

a) A node has either both a left and right child OR no children.
b) The right child of a node is either a leaf or NULL.

Write code to invert this tree. (Hint: Draw this out.)

6. Given a square with side length = 1, describe all points inside square that are closer to the center of the square than to the edge of the square.

7. How many 0’s are at the end of N! (Hint: look at the prime factorization of N!)

8. Given an array A[string], an array of strings where each string represents a word in a text document. Also given 3 search terms T1, T2, and T3 and 3 corresponding sorted sequences of integers S1, S2, and S3 where each integer in Si represents an index in A where search term Ti occured (i.e. S1, S2, and S3 contain the locations of the search terms in our array of words).

Now find a minimal subarray of A that contains all of the search terms T1, T2, and T3. Extend this algorithm for an arbitrary number of search terms. (Hint: Think of the brute force algorithm first.)

9. You are shrunk to the height of a nickel and your mass is proportionally reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 seconds. What do you do?

10. How would you find out if a machine’s stack grows up or down in memory?

11. Explain a database in three sentences to your eight-year-old nephew.

12. How many gas stations would you say there are in the United States?