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

Question

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

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

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

До сих пор так хорошо: это проблема с максимальным перемещением (также известная как проблема с максимальным раздвижным окном), и есть linear-time algorithm, который ее решает.

Теперь вопрос усложняется. Конечно, старые истории, как правило, менее жаркие по сравнению с более новыми историями. Пусть возраст 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) в окне. В любой момент времени самая горячая история в очереди стоит впереди. Новые истории выталкиваются на заднюю часть дека, после того, как они всплывали каждую историю со спины, пока не появилась более горячая история. Истории выталкиваются спереди, когда они выходят из окна.

Например:

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), эта новость становится ответом на запрос скользящего окна, и мы удаляем этот элемент из последовательности. Итак, вам нужна структура данных с возможностью добавления в конец и удаление с начала и с конца. Это Deque. Временная сложность решения - O(n).