Another Algorithm Job-Interview

Question

So here is the question:

Suppose you have 100 thousand integers which ranges from 1 to 1 million. Please sort out the integers. The time complexity should be O(n).

Anybody who shares his or her ideas is well appreciated.

Answer 1

Sounds like a straightforward counting sort.

1. Reserve memory for an array a of size 1 million
2. Initialize all array values to 0
3. Loop through the integers. For each integer i increment a[i] by one.
4. Output sorted sequence by walking through the array and printing each number i for a[i] times.

Space is constant. Runtime is O(n).

Answer 2

The hint should be that they range from 1 to 1 million.

See pigeonhole sort

Answer 3

Since the problem has fixed size and includes a finite set of instances, any sorting algorithm will terminate in O(1). You should tell the tester to go back to algorithm analysis school. One possible way to generalize this problem to an infinite set is: you have an array of size n with numbers ranging in [0, 10n]. Can you sort it in O(n)? That makes sense to me. Or you could parametrize the problem with the size of the array and the range of the integers and come up with some O(f(n,k)) bound. The problem is when you get a question like this in an interview, what do you do? Do you try to guess what the interviewer would like to hear or do you say something like "let me rephrase your question"? Or you just scoot towards the exit with a big smile?