## Goldman Sachs Interview Question for Applications Developers

Country: India

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

What is quicksort is best answered by yourself by reading that chapter of your algorithms textbook. At the very min. you should know about these sorting algorithms:

Insertion sort (the most practicaly n^2 sort)
Merge sort (the stable n*log(n) comparison sort, which also works on linked lists)
Quicksort (the fastest comparison sort on arrays in practice)
Counting sort (fast integer sort when the range of integers is small)

And when you learn mergesort, study the "merge" subroutine well and realize that it is useful outside the sort. Same goes for the "partition" subroutine of quicksort.

Choosing a pivot is best done by picking a random pivot.

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

First assume the "Partitioning" problem:
Assume "A" is unsorted and choose its p-th location as the "pivot". Assume A[p] = a and "a" is the i-th smallest element of A. Then, a partitioning over "p" yields a reordering of A such that "a" is located at the i-th location, and any element located at j < i is smaller than "i" (an consequently, the ones at j > i are larger).

This is done in O(n) where n is the length of A.

Quick sort is nothing but a series of recursive calls to partitioning

``````QuickSort(A, p)
{
i = Partition(A, p);
QuickSort(A[1..i - 1], p1);
QuickSort(A[i + 1....n], p2);
};``````

The important question is how to choose "p". The answer is "randomly and uniformly". The average performance of QuickSort for uniformly chosen "p" is optimal, e.g., O(n.log(n)) time.
Worst-case however, is O(n^2) which occurs with O(1 / n!) chance when "p" is selected uniformly in each recursive call.

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

For these type of questions, it's best to let the original poster read up on the topic.

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

hey guys , check out this link that clears my all doubts for quick sort algorithm and it also have an example with screenshot

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.