Interview Algorithm: find two largest elements in array of size n

Question

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

Answer 1

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.

Answer 2

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).