8

This is an interview question I saw online and I am not sure I have correct idea for it.

The problem is here:

Design an algorithm to find the two largest elements in a sequence of n numbers. Number of comparisons need to be n + O(log n)

I think I might choose quick sort and stop when the two largest elements are find? But not 100% sure about it. Anyone has idea about it please share

Colin Brock
  • 21,267
  • 9
  • 46
  • 61
Allan Jiang
  • 11,063
  • 27
  • 104
  • 165
  • 2
    What is meant by n + O(log n)? Presumably n is the number of elements in the list, but O(log n) is not a number, but a class of algorithms... I think? – recursive May 14 '12 at 21:13
  • 1
    @recursive: It means you're allowed one iteration and one search – James May 14 '12 at 21:15
  • @James: O(log n) is the cost of a binary search, but I assumed this list is not sorted. If it's sorted, the problem becomes O(1). A search of an unsorted list is O(n). – recursive May 14 '12 at 21:17
  • Quck sort and stop? Might as well just go through the list and find them at least it would be clear what it's doing then. Not clear whether the values can be the same either, which would change things a bit. – Tony Hopkinson May 14 '12 at 21:20
  • The question would make more sense if it were \theta(n+log n) – Jacob May 14 '12 at 21:29
  • A partial heapsort comes very close. It satisfies O(n+log(n)), but I can't work out whether it satisfies n+O(log(n)) or not. – Brilliand May 14 '12 at 21:43
  • What do you mean by "satisfies n+O(log(n))". I don't understand that part. BTW O(n + log(n)) == O(n). – recursive May 14 '12 at 21:48
  • 1
    n+O(log(n)) means O(log(n)) time, plus a maximum of n comparisons (not 2n, not 1.5n, just n). – Brilliand May 14 '12 at 21:50
  • 1
    duplicate: http://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-of-comparisom/3628777#3628777 – sdcvvc May 15 '12 at 03:39

2 Answers2

15

Recursively split the array, find the largest element in each half, then find the largest element that the largest element was ever compared against. That first part requires n compares, the last part requires O(log n). Here is an example:

1 2 5 4 9 7 8 7 5 4 1 0 1 4 2 3
2   5   9   8   5   1   4   3
5       9       5       4
9               5
9

At each step I'm merging adjacent numbers and taking the larger of the two. It takes n compares to get down to the largest number, 9. Then, if we look at every number that 9 was compared against (5, 5, 8, 7), we see that the largest one was 8, which must be the second largest in the array. Since there are O(log n) levels in this, it will take O(log n) compares to do this.

id2341677
  • 319
  • 6
  • 13
Running Wild
  • 2,951
  • 18
  • 15
  • 2
    I see few problems, first is "the last part" doesn't require O(log n) it requires O(n), although there are log n levels, the total number of comparisons is n/2 + n/4 + n/8 + n/16 + ... = n Another problem is where do you get the list of numbers the number 9 was compared to? – Cano64 Apr 10 '15 at 20:12
  • @ Cano64 there are logn levels and at each level you will compare only make 1 comparision – akashchandrakar Feb 26 '16 at 15:13
  • 2 5 9 8 5 1 4 3 at this lvl we do more than one comparison – user2975699 Mar 31 '16 at 20:10
1

For only 2 largest element, a normal selection may be good enough. it's basically O(2*n).

For a more general "select k elements from an array size n" question, quick Sort is a good thinking, but you don't have to really sort the whole array.

try this

  1. you pick a pivot, split the array to N[m] and N[n-m].
  2. if k < m, forget the N[n-m] part, do step 1 in N[m].
  3. if k > m, forget the N[m] part, do step in in N[n-m]. this time, you try to find the first k-m element in the N[n-m].
  4. if k = m, you got it.

It's basically like locate k in an array N. you need log(N) iteration, and move (N/2)^i elements in average. so it's a N + log(N) algorithm (which meets your requirement), and has very good practical performance (faster than plain quick sort, since it avoid any sorting, so the output is not ordered).

StanleyZ
  • 598
  • 6
  • 22