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.

- bigphatkdawg September 18, 2013 | Flag Reply
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.

- Ehsan September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- bigphatkdawg September 18, 2013 | Flag
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

link - geeksprogrammings.blogspot.com/2014/02/algorithm-quick-sort-program.html

- Ranjeet singh bajwa January 17, 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