Write an algorithm to sort an array of integers in O(n) time?

Question

NK · Accepted Answer

As it is array of integers radix sort can be used which has runtime of O(n). On a computer the size of integer variable is fixed, or constant, hence it become O(n). Any comparative sort will take O(n log(n)) but, the radix and buck sort are not comparative. Lets say the integer size is 32bits, then it's run time will be 32 * O(n), which is same as O(n)

Anonymous · Answer

There are a number of algorithms to do this one is called bucket sort. The interview didn't indicate the answer to me, but it seemed like he was looking for heap sort (which is O(nlogn) )..

Christian · Answer

I believe your answer should be that no sort algorithm (on a sequential computer) can sort an array of numbers in less than O(n lg n) time.  So his request couldn't be satisfied.

Akamai

Akamai interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?