Another Algorithm Job-Interview Question

Question

Hi all: So here is the question:

Suppose you have got 100 thousands integers which ranges from 1 to 1 million,please sort out the integers and its time complexity should be O(n)

Anybody who shares his or her ideas is well appreciated.

Thanks in advance!

Answer 1

Use count sort. Just count all of them ( O(n) ), and then create fill the result array ( O(n), again).

Answer 2

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 3

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

See pigeonhole sort

Answer 4

You have to use any known sorting algorithms with complexity O(n)

http://stackoverflow.com/questions/2352313/is-there-an-on-integer-sorting-algorithm

Answer 5

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?