Частота слова с упорядочением по сложности O (n)

Во время собеседования на должность разработчика Java меня спросили следующее:

Напишите функцию, которая принимает два параметра:

1. Строка, представляющая текстовый документ и
2. целое число, представляющее количество возвращаемых предметов.

Реализуйте функцию так, чтобы она возвращала список Строк, упорядоченных по частоте слова, первое из которых встречается чаще всего. Ваше решение должно выполняться за время $O(n)$ где $n$ - количество символов в документе.

Вот что я ответил (в псевдокоде), это не $O(n)$ а скорее $O(n \log n)$ время из-за сортировки. Я не могу понять, как это сделать $O(n)$ раз.

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

Кто-то знает, или кто-то может дать мне несколько советов?

Я предлагаю вариант подсчета распределения:

1. Прочитайте текст и вставьте все слова, встречающиеся в три , сохраняя в каждом узле счетчик того, как часто встречается слово, представленное этим узлом. Дополнительно следите за наибольшим количеством слов, скажем maxWordCound. - $O(n)$
2. Инициализируйте массив размера maxWordCount. Тип записи - это списки строк. - , так как количество не может быть выше.$O(n)$
3. Пройдите через три и для каждого узла добавьте соответствующую строку к записи массива, указанной счетчиком. - , так как общая длина строк ограничена n .$O(n)$$n$
4. Пройдите по массиву в порядке убывания и выведите желаемое количество строк. - , поскольку это ограничение как размера, так и количества данных в массиве.$O(n)$

Возможно, вы можете заменить три других структур данных на первом этапе.

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

Куча - это распространенный способ агрегирования верхних значений k, хотя могут использоваться и другие методы (см. Https://en.wikipedia.org/wiki/Partial_sorting ).

Предполагая, что k является вторым параметром выше, и что это константа в постановке задачи (она выглядит так):

1. Создайте три слова с количеством вхождений на каждом узле.
2. Инициализируйте кучу размера k.
3. Пройдите три и мин-зонд / вставьте каждую пару (лист, число-количество) в кучу top-k.
4. Выведите верхние k листьев и счетчиков (на самом деле это немного болезненно, потому что вам нужны родительские указатели, чтобы сопоставить каждый лист обратно со словом).

Поскольку размер кучи является постоянным, операции кучи - это O (1), поэтому шаг 3 - это O (n).

Куча также может поддерживаться динамически при построении дерева.

Ваш алгоритм даже не запускается за время ; вставка Θ ( n ) вещей в хеш-таблицу уже стоит время Ω ( n 2 ) (наихудший случай).$O(n \log n)$$\Theta(n)$$\Omega(n^2)$

То, что следует, неправильно ; Я оставляю это здесь пока в иллюстративных целях.

Следующий алгоритм выполняется в наихудшее время (при условии алфавита Σ постоянного размера), n количество символов в тексте.$O(n)$$\Sigma$$n$

1. Построить дерево суффиксов текста, например, с помощью алгоритма Укконена .

   Если конструкция еще не делает этого, добавьте число достижимых листьев для каждого (внутреннего) узла.

2. Пройдите по дереву от корня и отрежьте все ветви в первом (белом) пространстве.

3. Пройдите по дереву и отсортируйте список дочерних элементов каждого узла по количеству листьев.

4. Выход дерева (листья слева направо) теперь представляет собой список всех слов, отсортированных по частоте.

Что касается времени выполнения:

1. Алгоритм Укконена (в его расширенной форме) выполняется за время ; поддержание подсчета листьев не увеличивает thetas ; -Стоимость алгоритма.$O(n)$$\Theta$
2. Мы должны пройти один узел на символ каждого слова, встречающегося в тексте. Поскольку существует не более различных пар слово-символ, мы посещаем не более n узлов.$n$$n$
3. Мы посещаем не более узлов (ср. 2) и проводим время O ( | Σ | ⋅ log | Σ | ) = O ( 1 ) на узел.$n$$O(|\Sigma| \cdot \log |\Sigma|) = O(1)$
4. Мы можем получить доход (который, конечно, имеет размер ) простым обходом времени O ( n ) (ср. 2).$O(n)$$O(n)$

Более точные границы могут быть получены путем параметризации времени выполнения с количеством разных слов; если их мало, дерево мало после 2.

Используйте хеш-таблицу (например, HashMap), чтобы собрать все слова и их частоты. Затем используйте сортировку подсчета, чтобы отсортировать слова в порядке убывания частоты. Поскольку все частоты являются целыми числами в диапазоне , сортировка при подсчете занимает время O ( n ) . Общее ожидаемое время работы O ( n ) , что более чем вероятно более чем достаточно для всех практических целей (если интервьюер не упомянул что-то, что было оставлено вне вашего вопроса). Не забудьте упомянуть, что это ожидаемое время выполнения, а не время выполнения в худшем случае .$1..n$$O(n)$$O(n)$

Это может не быть ответом, который учитель будет искать в классе алгоритмов, потому что это ожидаемое время выполнения а не время выполнения O ( n ) в худшем случае. Если вы хотите набрать дополнительные баллы на вопросе об интервью, вы можете небрежно упомянуть, что, конечно, это ожидаемое время выполнения, но это также можно сделать за O ( n ) наихудшее время выполнения, заменив хэш-таблица с более сложной структурой данных - и вы были бы рады подробно рассказать о том, как вы будете выбирать между алгоритмами в такой ситуации.$O(n)$$O(n)$$O(n)$

$O(n)$$O(n)$

Решение на основе хэш-таблицы

$\Omega(n^2)$$n$

$n$$\Omega(n)$

$O(1)$$O(n)$$O(n^2)$$n$

Предполагается, что алгоритм хеширования является линейным по времени относительно количества символов.

Решение на основе сортировки Radix

В качестве альтернативы, если исходить из английского, поскольку длина слов хорошо известна, я бы вместо этого создал сетку и применил бы сортировку по основанию, которая $O(kN)$$k$$N$$n$$k$$O(n)$

$2n$$n$$O(n)$

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