Big Shot IT company interview puzzle

Question

This past week I attended a couple of interviews at a few big IT companies. one question that left me bit puzzled. below is an exact description of the problem.(from one of the interview questions website)

Given the data set,

A,B,A,C,A,B,A,D,A,B,A,C,A,B,A,E,A,B,A,C,A,B,A,D,A,B,A,C,A,B,A,F

which can be reduced to

(A; 16); (B; 8); (C; 4); (D; 2); (E; 1); (F; 1):

using the (value, frequency) format.

for a total of m of these tuples, stored in no specific order. Devise an O(m) algorithm that returns the kth order statistic of the data set. m is the number of tuples as opposed to n which is total number of elements in the data set.

Answer 1

You can use Quick-Select to solve this problem.

Naively:

1. Pick an element (called the pivot) from the array
2. Put things less than or equal to the pivot on the left of the array, those greater on the right.
3. If the pivot is in position k, then you're done. If it's greater than k, then repeat the algorithm on the left side of the array. If it's less than k, then repeat the algorithm on the right side of the array.

There's a couple of details:

1. You need to either pick the pivot randomly (if you're happy with expected O(m) as the cost), or use a deterministic median algorithm.
2. You need to be careful to not take O(m^2) time if there's lots of values equal to the pivot. One simple way to do this is to do a second pass to split the array into 3 parts rather than 2: those less than the pivot, those equal to the pivot, and those greater than the pivot.