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.

- smallchallenges March 12, 2016 | Flag Reply
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

- Tarun March 11, 2016 | Flag Reply
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)

- Raj March 13, 2016 | Flag Reply
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.

- jermenkoo March 11, 2016 | Flag Reply
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.

- gen-y-s March 13, 2016 | Flag Reply
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

- Arnab March 27, 2016 | Flag Reply
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.

- urajokeGenX March 29, 2016 | Flag Reply
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.

- nn January 24, 2017 | Flag Reply
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.....

- gen-x-s March 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- bad_challenges March 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More