Question:
Given a file with a set of unique (non-repeating) integers from 1 to 1,0000,000 , how would you sort it?
For example, if the input file contained
420
2001
23
90210
1492
the output should be
23
420
1492
2001
90210
Solution:
This is one of my favorite interview questions since it shows how the interviewee approaches a fairly simple and common sorting problem.
The best answer in my opinion is to use a bit array. When the words "unique integer" appears, a bit array should be one of your solution considerations. The basic algorithm is
1. Initialize a bit array to a size of 1,000,000 with all the values of 0.
2. Read each number from the file.
3. For each number, set the bit array index for that number to 1. For example, for the number 420, you would set bit_array[420] = 1 . For 2001,you would bit_array[2001] = 1;
4. Once all the numbers are processed, loop through the bit array and output all the indexes that have a value of 1. That is your sorted list of numbers.
In Java, there is a built-in BitSet implementation of a bit array.
// 1. Initialize bit array
final BitSet bitSet = new BitSet(1000000);
// 2. Read each number
final int[] intInput = {420, 2001, 23, 90210, 1492};
// 3. Set bit array index with each number from step 2
for (int i : intInput) {
bitSet.set(i);
}
// 4. Loop through bit array and display all set values
for(int i = bitSet.nextSetBit(0); i >=0; i = bitSet.nextSetBit(i+1) ) {
System.out.print(i + "\n");
}
The algorithm is easy to understand and implement. It is also fast and does not require a lot of memory.
This question comes from the first chapter of Jon Bentley's book, Programming Pearls . It is a book every good programmer should read
