Есть функция релевантности: насколько документ интересен конкретному
пользователю. Она задана интерфейсом Ranker. Нужен сервис, который умеет
сохранять документы и выдавать limit самых релевантных для заданного
пользователя.
type Item = int // идентификатор/документ
type Viewer = int // пользователь
type Ranker interface {
Rank(item Item, viewer Viewer) int // чем больше, тем релевантнее
}
// New создаёт сервис с заданной функцией релевантности.
func New(r Ranker) *Service
// Add сохраняет документ.
func (s *Service) Add(item Item)
// Top возвращает до limit документов с наибольшим Rank(item, viewer),
// отсортированных по убыванию скора. limit <= 0 → пустой результат.
func (s *Service) Top(viewer Viewer, limit int) []Item
Поведение
Top сортирует результат по убыванию скора. При равных скорах порядок между
такими документами не специфицирован — любой валидный годится.- Если сохранено меньше
limit документов, возвращаются все.
Rank для разных viewer даёт разные скоры: один и тот же набор документов
ранжируется по-разному.- Один и тот же документ можно добавить несколько раз — он учитывается столько
раз, сколько добавлен.
Ограничения
Rank считается дорогой, но детерминированной (для фиксированных аргументов
возвращает одно и то же).- Ожидается, что выбор топ-
K из n документов работает за O(n·log K), а не
за O(n·log n): при K ≪ n это заметно.
Устно: где тут уместна куча и почему именно min-heap размера K? Что
изменится, если документы добавляются и удаляются постоянно, а топ нужен часто?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.