Microsoft Interview Question
Senior Software Development EngineersCountry: India
Interview Type: Phone Interview
I agree with smallchallenges upto certain extent, however my answer goes like this.
If we know what kind of input is we are receiving and if that input is in given range, then we can use counting sort/bucket sort depending on input. - Time : O(n)
If we know the (1) what kind of input, (2)numbers are random(but not in range), (3) numbers are not already sorted(ascending/descending) , then choose quick sort
- Time : O(nlogn)
If we don't know anything about input - heap sort/Merge Sort - Time : O(nlogn)
In terms of (worst-case) complexity, the best sorting algorithm is heapsort, since it's O(n log n) time and O(1) space. Heapsort has soe shortcomings, such as the fact it's not stable and the best case time is also O(n log n) and not O(n) like some other sorting algorithms. But in terms of complexity, as specified in this question, it's the best.
There is no one sorting algorithm which is best in all cases
Counting sort is best if given number is within certain range and it also requires space bt it can be done in linear time.
If the given input is represented as linked list then merge sort will be best since it can be done in O(NlogN) time and O(1) space
If we have very few numbers and it is not sorted then quicksort will be best.
If space is a constraint and the input is almost sorted then insertion sort is best.
small-changes - that's your answer ? hahaha. Non comparison sorts can only be used in special cases, not in the general case. Regarding comparison sorts, why is merge sort the best ? It requires O(n) space, so it's worse than most other algorithms in terms of space complexity. The question specifically requires the best algorithm in terms of complexity, which means both time complexity and space complexity. You failed.....
Let's look at the highest voted answer here from "small-challenges" : first he says (although it's presented as a question) a sorting algorithm cannot be better than O(N). Well, obviously any problem where you have to process O(N) input will take at least O(N) time..... Next he talks about no-comparison sorting algorithms without mentioning that these are applicable only in special cases, such as when the input is in a known discrete range. Next he says that if additional memory cannot be used than use any O(n log n) sort, but of course many O(n log n) sorts do use addiyional memory - fail again !! He adds that qsort may be better, but guess what ? quick sort uses at least O(log n) additional meory for the recursion !!!! what a joke, this guy shows his total lack of knowledge. Finally, he refers to the fact that quick sort has a worst case time of O(n), so if that's a problem then use merge sort - but guess what ? merge sort uses O(n) memory..... what a bad bad answer. This answer in an interview would just make you dig your own grave deeper and deeper...... horrible answer "small-challenges" you get 0 out of 10
I guess the answer might be to state an answer and defend it....here is what I would have tried...
- smallchallenges March 12, 2016For a set of "n" elements, can any sorting algorithm do better than O(n)? No...we have to visit each element atleast once. So, imo, the best sorting algorithm is one which is O(n). So, I vote for Counting sort IF cpu were the only consideration (time complexity)....counting sort needs additional memory.
If additional memory cannot be used (space complexity), then any O(nlogn) sort should work....as a previous poster says qsort may better.
But, if a worst case bound is required, then merge sort it is.