Перемещение максимального варианта

Question

Вчера мне задали следующий вопрос во время технического интервью.

Представьте, что вы работаете в информационном агентстве. В каждый отдельный момент времени tРассказы Некоторые истории более интересны, чем другие. Эта "жара" выражается как натуральное число hс большими числами, представляющими горячие новости.

Учитывая поток S из n истории, ваша работа состоит в том, чтобы найти самую горячую историю из самых последних k истории для каждого t >= k,

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

Теперь вопрос становится сложнее. Конечно, старые истории обычно менее горячие по сравнению с новыми историями. Пусть возраст a самой последней истории будет ноль, и пусть возраст любой другой истории будет на один больше, чем возраст ее последующей истории. "Улучшенная жаркость" истории тогда определяется как max(0, min(h, k - a)),

Вот пример:

n = 13, k = 4

S indices:   0   1   2   3   4   5   6   7   8   9  10
S values:    1   3   1   7   1   3   9   3   1   3   1

mov max hot indices:     3   3   3   6   6   6   6   9
mov max hot values:      7   7   7   9   9   9   9   3

mov max imp-hot indices: 3   3   5   6   7   7   9   9
mov max imp-hot values:  4   3   3   4   3   3   3   3

Я был в полном замешательстве с этим вопросом. Я думал о добавлении индекса к каждому элементу, прежде чем вычислять максимум, но это дает вам ответ, когда актуальность истории уменьшается на единицу на каждом шаге, независимо от того, достигла ли она актуальности или нет.

Можете ли вы найти алгоритм для этой задачи с субквадратичным (в идеале: линейным) временем выполнения?

Answer 1

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

Исходная проблема: держите в окне деку, содержащую истории, которые (1) новее или горячее, чем любая другая история (2). В любой момент самая горячая история в очереди - впереди. Новые истории выдвигаются на заднюю часть deque, после того, как выскочил каждый рассказ со спины, пока не будет найден более горячий рассказ. Истории всплывают с фронта, когда они стареют из окна.

Например:

S indices:   0   1   2   3   4   5   6   7   8   9  10
S values:    1   3   1   7   1   3   9   3   1   3   1

deque: (front) [] (back)
push (0, 1)
deque: [(0, 1)]
pop (0, 1) because it's not hotter than (1, 3)
push (1, 3)
deque: [(1, 3)]
push (2, 1)
deque: [(1, 3), (2, 1)]
pop (2, 1) and then (1, 3) because they're not hotter than (3, 7)
push (3, 7)
deque: [(3, 7)]
push (4, 1)
deque: [(3, 7), (4, 1)]
pop (4, 1) because it's not hotter than (5, 3)
push (5, 3)
deque: [(3, 7), (5, 3)]
pop (5, 3) and then (3, 7) because they're not hotter than (6, 9)
push (6, 9)
deque: [(6, 9)]
push (7, 3)
deque: [(6, 9), (7, 3)]
push (8, 1)
deque: [(6, 9), (7, 3), (8, 1)]
pop (8, 1) and (7, 3) because they're not hotter than (9, 3)
push (9, 3)
deque: [(6, 9), (9, 3)]
push (10, 1)
pop (6, 9) because it exited the window
deque: [(9, 3), (10, 1)]

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

В Python:

import collections

Elem = collections.namedtuple('Elem', ('hot', 't'))


def winmaximphot(hots, k):
    q = collections.deque()
    oldtop = 0
    for t, hot in enumerate(hots):
        while q and q[-1].hot <= hot:
            del q[-1]
        q.append(Elem(hot, t))
        while q and q[0].hot >= k - (t - q[0].t) > 0:
            oldtop = k - (t - q[0].t)
            del q[0]
        if t + 1 >= k:
            yield max(oldtop, q[0].hot) if q else oldtop
        oldtop = max(0, oldtop - 1)


print(list(winmaximphot([1, 3, 1, 7, 1, 3, 9, 3, 1, 3, 1], 4)))

Answer 2

Идея состоит в следующем: для каждой сенсации она превзойдет все предыдущие новости после k-h шаги. Это значит для k==30 и новости жаркости h==28после двух шагов эта новость будет более горячей, чем все предыдущие. Давайте сохраним все моменты времени, когда следующие новости будут самыми горячими. На этапе i мы получаем момент времени, когда текущие новости побьют все предыдущие, равные i+k-h, Так у нас будет такая последовательность объектов {news_date | news_beats_all_previous_ones_date}в порядке возрастания news_beats_all_previous_ones_date:

{i1 | i1+k-h}{i3 | i3+k-h}{i4 | i4+k-h}{i7 | i7+k-h}{i8 | i8+k-h}

На текущем шаге получаем i9+k-h, мы добавляем его в конец этого списка, удаляя все значения, которые больше (поскольку последовательность увеличивается, это легко). Однажды первый элемент news_beats_all_previous_ones_date становится равным текущей дате (i), эта новость становится ответом на запрос скользящего окна, и мы удаляем этот элемент из последовательности. Итак, вам нужна структура данных с возможностью добавления в конец и удаления из начала и с конца. Это Дек. Временная сложность решения O(n),