techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

find 3rd largest element in an array keeping order n

In a given array, how to find 3rd largest value with complexity O(n)?

for example: 10,2,4,7,12,11,9

Ans 10

rgds,
BP
BP Send private email
Tuesday, June 19, 2007
 
 
Make one pass through tracking the three largest values so far.

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Tuesday, June 19, 2007
 
 
Or:

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)
Michael G Send private email
Tuesday, June 19, 2007
 
 
Heap = Overkill.

Gene's solution is perfect.
Tapori
Tuesday, June 19, 2007
 
 
Unless the next problem is "find the 13th element."
Michael G Send private email
Tuesday, June 19, 2007
 
 
I guess it depends on the language.  If you had to do a heap yourself, it'd be a royal pain in the neck.  I was thinking about C++, using STL, and it'd be 4 lines:

priority_queue<int> q(input_container);
q.pop();
q.pop();
return q.top();
Michael G Send private email
Tuesday, June 19, 2007
 
 
No really, heap is not just overkill (coding it might be easier) it is inefficient compared to just making one pass through it.

Instead of integers, suppose the objects in the array were big blogs of strings such that comparing them is inefficient...
Tapori
Wednesday, June 20, 2007
 
 
Instead of maintaining a heap of size equal to array size, how about maintaining a heap(min) of size equal to k,here in this case k is 3.

Make one pass through the array and populate the heap accordingly such that k largest values seen so far are in the heap.

At the end, the root of the heap is the kth largest element.

I guess this will reduce the number of comparisions compared to maintiang k individual variables.
haresh
Wednesday, June 20, 2007
 
 
Thanks for the reply.

Typically interviewers expect Gene's solution. Take three variables tracking the largest 3 numbers so far. This will ensure O(n) though more comparisions required.

Rest all are good when implemented.

Thanks once again,
BP
BP Send private email
Wednesday, June 20, 2007
 
 
There are better algorithms.

Heap is not really optimal.

Best is to follow the "tournament" principle which is used to find the second largest (generalized to kth largest)

Check this out: http://www.seeingwithc.org/topic3html.html
Tapori
Wednesday, June 20, 2007
 
 
Keeping an array to keep largest K elements will work well till k is small. As k grows you might have complexity probems .It might become much higher then o(n).
Google for QuickSelect Algorithm on net . Its a variation of quick sort and is used specifically for this purpose as far as I know.
Ankit Send private email
Thursday, June 21, 2007
 
 
Is complexity of building a heap really O(n) ?
Maciek
Friday, June 22, 2007
 
 
According to the Bible (CLR Intro to Algos any i-th order statistic) can be found in O(N) worst time using some rather complex select and in expected
O(N) time using simpler randomized select which is relatively trivial to code.

i-th order statistic is i-th smallest element but the algo can be adapted for the largest element.
Bytheway
Saturday, June 23, 2007
 
 
Thank you Michael G: I was wondering about the solution to CLR problem 10.1-1: prove that the second smallest of n elements can be found with n + lg n - 2 comparisons in the worst case.

Your use of priority queue gives me a hint.
Bytheway
Saturday, June 23, 2007
 
 
"Is complexity of building a heap really O(n) ? Maciek"

When heap has N nodes inserting a new node is O(logN)

So the time to build it is log0+log1+log2+... logN and I have not the lsigntest idea if that may end up being O(N). Any illumination appreciated.
Bytheway
Saturday, June 23, 2007
 
 
OOps, again according to the Bible since each heap insertion takes O(logN), building the heap of N elements is O(NlogN) but the bound is not 'asymptotically tight'.

Tighter bound analysis on page 145 chapter 7.3 in my edition shows that heap can indeed be built from unordered array in O(N) time. Michael is right.
Bytheway
Saturday, June 23, 2007
 
 
Bleah,
tournament principle is way too much to code in general
k-th case and the result is O(N) + O(logN) - const in any case. Not muche better than heap based alternative.

Somebody got really confused at http://www.seeingwithc.org/topic3html.html as well.

They have for a second tournament:

7 3 8
 3 8
  9

which is braindead.

Should be:

7 3 8
 7 8
  8
Bytheway
Sunday, June 24, 2007
 
 
Bytheway, having lazy programmers is not an excuse for having a crappy product.

Anyway, for k=3, the tournament is pretty good compared to the heap, does not matter is some website got it wrong.

We all know finding 3rd largest is O(N). The constant factor is what matters.
Tapori
Sunday, June 24, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz