2
$\begingroup$

Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top $\log(n)$ frequent flyers, where n is the total number of the airlines’ frequent flyers. Their current algorithm runs in $O(n \log(n))$ time to sort the flyers scan the sorted list to pick the top logn flyers. Describe an algorithm that identifies the top $\log(n)$ flyer in $O(n)$ time.

How can I devise an algorithm for this problem? I tried to solve it with priority queue ADT and some well-known sorting, but cannot solve this problem.

$\endgroup$

3 Answers 3

4
$\begingroup$

For every $k$, you can find the $k$th largest element in $O(n)$, using a linear time selection algorithm. You can then find the $k$ largest elements by scanning the array.

$\endgroup$
5
  • $\begingroup$ Is there any method to use priority queue ADT? Also I wonder if I can use radix-sort if the data set is the number of flights. $\endgroup$
    – user119526
    Commented Apr 15, 2020 at 17:54
  • $\begingroup$ I feel like several details are missing from your post. It's very hard for us to answer a question unless you ask it. $\endgroup$ Commented Apr 15, 2020 at 18:05
  • $\begingroup$ This is the original problem. - Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top logn frequent flyers, where n is the total number of the airlines’ frequent flyers. Their current algorithm runs in O(nlogn) time to sort the flyers scan the sorted list to pick the top logn flyers. Describe an algorithm that identifies the top logn flyer in O(n) time. $\endgroup$
    – user119526
    Commented Apr 15, 2020 at 18:16
  • 2
    $\begingroup$ You should update your post with this information. At any rate, I see absolutely nothing wrong with my proposed algorithm. $\endgroup$ Commented Apr 15, 2020 at 18:18
  • 1
    $\begingroup$ And by the way, @Mathematicaist, you can indeed use radix bucketing instead of (or in combination with) the quickselect approach that Yuval suggested. It will probably even have a smaller constant factor. Anything that lets you locate the $k$th largest elemenbt within a partition size of approximately $\frac{n}{2}$ or smaller for $O(n)$ work will do the job. $\endgroup$
    – Pseudonym
    Commented Apr 15, 2020 at 23:09
1
$\begingroup$

Use the deterministic select algorithm (look it up, it is widely discussed in algorithm/data structures courses). It's core is a partition like Quicksort's (i.e., small elements on one side of the pivot, large ones after), but it selects pivots carefully so as to get a linear worst case (not just average). You just need to ask for the $\log n$-th element, and read off the smaller ones before. Linear, but horrible constant. Theoretical interest only.

If you know which element's key is $\log n$-th beforehand somehow, you can just use Quicksort's partition to get the actual list.

$\endgroup$
-1
$\begingroup$

You can use bucket sort for this problem, by having mile buckets/map. And then scan the frequency bucket to pick top logn flyers. This will be O(n).

$\endgroup$
1
  • $\begingroup$ This is only true if the maximum amount of miles is $O(n)$. $\endgroup$
    – Steven
    Commented Apr 15, 2020 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.