Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

There is one big advantage of merge sort over quick sort on modern multi-core architecture. Although both have average response time of (n log n), remember that because you have separate memory for the divisions in merge sort, you can safely run some operations in parallel where as in quick sort, unless you run first partition operation, you cannot run 2nd partition operation and therefore there are issues with making it parallel.

- PK February 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Its possible to make merge sort parallel, not possible (difficult due to partition pass dependency) with quick sort. So (n log n) <= ( n log n)

- PK February 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

there are few advantage of the quick sort over merge sort :
1. it is inplace .
2. it is most widely used algo. for any set of data.
3. in the worst case , whet the partition algorithm combined with the randomization , it becomes very power full.very less probablity of the worst case.
4. for settelite data it really performs well.

- Anonymous February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Merge sort always run at O(n log(n)). Quick sort can be O(n^2) in worst case scenario.
Merge sort cannot be done in-place (It is possible but the implementation is very hard), Quick sort can be done in-place a lot easier.

Which one is better? Quick sort, as long as we use randomize algorithm to randomize the quick sort pivot selection so that we can make the worst case runtime of O(n^2) virtually disappear.

- hiuhchan February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Merge Sort:
Inplace: false
Stable: true
Worst: N*log(N)
Average: N*log(N)
Best: N*log(N)

Quick Sort:
Inplace: true
Stable: false
Worst: N^2 / 2
Average: 2N*log(N)
Best: N*log(N)
Remark: in practice work faster.

- Mike L February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

those who are blaming quick sort for the worst case ,it will give worst case only when the array is sorted or almost sorted.
it is most practically used algo. and if the array is sorted ,why are you going for sorting !!?
IT IS TONY HOARE PRODUCT , MY FAV COMPUTER SCIENTIST , winner of turing award!
quick sort worst case , average case o(nlog n )only , and with randomization , it will give n log n , even in the worst case , for the 99% of the input sets , and bigger advantage over the merge is , it is outplace.
when someone comes to the sattelite data , using this is probably the worst idea !

- nakul_o+ve February 18, 2015 | Flag Reply


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