Amazon interview prob

Существует большой файл слов, который динамически меняется. Мы постоянно добавляем в него несколько слов. Как бы вы отслеживали 10 самых популярных слов в каждый момент?

Я нашел этот вопрос в блоге, но я не мог понять ответ. Ответ: хэш-таблица + min-heap

Я понимаю, почему хеш-таблица, но не часть min-heap, может мне кто-то помочь?

Ответы

Ответ 1

Если это top 10 trending words, тогда вы должны использовать max-heap вместе с hash-table.

Когда в файл добавляется новое слово, выполните следующие действия:

  • Create новый элемент x с x.key=word и x.count=1.
  • Add x к hash-table. O(1).
  • Add x к max-heap. O(lgn).

Если в файл добавлено существующее слово, выполните следующие действия:

  • Find x в hash-table. O(1).
  • Update x.count до x.count++.

При необходимости получить top 10 trending words, а затем:

  • Extract 10 раз из max-heap. 10*O(lgn)=O(10*lgn)=O(lgn).

Как вы можете видеть, все необходимые операции выполняются максимально O(lgn).

Ответ 2

Если вы хотите сохранить только топ-10, использование макс-кучи слишком велико. Сохранение 10 записей в отсортированном массиве будет проще и быстрее.

Для сортировки просто используйте сортировку вставки, начиная со дна массива. Вам нужно будет проверить случай, когда кандидат уже входит в первую десятку, обновляя свою позицию, если это необходимо.