## Microsoft Interview Question for Senior Software Development Engineers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 6 vote

I guess the answer might be to state an answer and defend it....here is what I would have tried...

For 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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

It depends on the situation but in general Quicksort is one of best available. A close second in Mergesort.
Src:h\$\$p://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort

Comment hidden because of low score. Click to expand.
1
of 1 vote

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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Depends on the constraints and whether they mean comparison-based sorting algorithm (if so, then quicksort / mergesort depending on the memory importance), otherwise input-sensitive O(n) bucket / radix sort.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Insertion sort is a good choice if you know that the array is almost sorted

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorting algorithms can definitely be better then O(N) that is the whole basis for creating them. Maybe don't be so quick on judging intelligence bro.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.....

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.