I had a series of five interviews, each 45 minutes long. Each interviewer presented a technical problem and asked me to write code on the whiteboard.

The first interviewer tried to ask questions in the context of my recent work, but I ended up having to explain the context of the problem (economics) in order to explain what I had done, so he was disappointed.

The other interviews included questions about:

• How to do a "dispersion sort," that is, to ensure that identical items in the input are maximally spread out in the output.
• How to represent words and frequencies to provide interactive spelling corrections.
• Tracking recent queries so you can produce a random selection from the most recent N queries.

How would you write a sort routine to ensure that identical elements in the input are maximally spread in the output?