Big Shot IT-интервью с головоломкой

Question

На прошлой неделе я посетил пару интервью в нескольких крупных ИТ-компаниях. один вопрос, который оставил меня немного озадаченным. ниже приводится точное описание проблемы. (от одного сайта интервью вопросов)

Учитывая набор данных,

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 

, которая может быть сведена к

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

используя (значение , частота).

всего м этих кортежей, хранящихся в определенном порядке. Разработать алгоритм O (m), который возвращает статистику k-го порядка набора данных. m - количество кортежей, а n - общее количество элементов в наборе данных.

Answer 1

Для решения этой проблемы вы можете использовать Quick-Select.

Наивно:

1. Выберите элемент (так называемый стержнем) из массива
2. навел меньше чем или равной ось слева от массива, тем больше справа.
3. Если стержень находится в положении k, то все готово. Если он больше k, повторите алгоритм в левой части массива. Если он меньше k, повторите алгоритм в правой части массива.

Там есть пара деталей:

1. Вы должны либо выбрать точку опоры случайным образом (если вы счастливы с ожидаемым O (м) в качестве стоимости), или использовать детерминированный медиана алгоритм.
2. Вы должны быть осторожны, чтобы не брать время O (m^2), если имеется множество значений, равных оси. Один простой способ сделать это - сделать второй проход, чтобы разбить массив на 3 части, а не на 2: те, которые меньше, чем ось, равная оси вращения, и те, которые больше, чем точка поворота.