Pular para o conteúdo

Histórico de voltar e avançar

Fácil#doubly-linked-list#design~20 min

A missão

Problema

Simule o histórico de uma única aba do navegador que começa em uma página inicial. Uma visita abre uma nova página depois da atual e descarta todas as páginas para as quais antes seria possível avançar. Uma operação back de k volta até k páginas em direção ao início, e uma forward de k avança até k páginas em direção à mais nova, parando antes quando não há mais para onde ir. Dada a página inicial e uma lista de operações, retorne a página em que você está depois de cada back ou forward, em ordem.

Exemplos

Input:  home = "home"
        ops  = [("visit", "a"), ("visit", "b"), ("back", 1),
                ("visit", "c"), ("forward", 1), ("back", 5)]
Output: ['a', 'c', 'home']
Por quê: visitar c a partir de a descarta b, então o forward não tem para onde ir
Input:  home = "x", ops = [("back", 2), ("forward", 3)]
Output: ['x', 'x']
Por quê: edge case: uma aba nova não consegue ir nem para trás nem para a frente

Dicas

0 / 3

Tempo-alvo
O(n + Σk)
Espaço-alvo
O(n)

Travou na ideia, e não no código? Listas duplamente encadeadas explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado