Given a sequential file that contains at most four billion
32-bit integers in random order, find a 32-bit integer that isn't in the
file (and there must be at least one missing - why?). How would you solve
this problem with ample quantities of main memory? How would you solve
it if you could use several external "scratch" files but only a few hundred
bytes of main memory?
Rotate a one-dimensional vector of n elements
left by i positions. For instance, with n=8
and i=3, the vector abcdefgh is rotated to defghabc.
code uses an n-element intermediate vector to do the job
in n steps. Can you rotate the vector in time proportional
to n using only a few dozen extra bytes of storage?
Given a dictionary of English words, find all sets of anagrams.
For instance, "pots", "stop" and "tops" are all anagrams of one another
because each can be formed by permuting the letters of the others.