Saltar al contenido

Historial de atrás y adelante

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

La misión

Problema

Simula el historial de una sola pestaña del navegador que empieza en una página de inicio. Una visita abre una página nueva después de la actual y descarta todas las páginas a las que antes podías ir hacia adelante. Un back de k retrocede hasta k páginas hacia el inicio, y un forward de k avanza hasta k páginas hacia la más nueva, deteniéndose antes si ya no queda adónde ir. Dada la página de inicio y una lista de operaciones, devuelve la página en la que estás después de cada back o forward, en orden.

Ejemplos

Input:  home = "home"
        ops  = [("visit", "a"), ("visit", "b"), ("back", 1),
                ("visit", "c"), ("forward", 1), ("back", 5)]
Output: ['a', 'c', 'home']
Por qué: visitar c desde a descarta b, así que forward no tiene adónde ir
Input:  home = "x", ops = [("back", 2), ("forward", 3)]
Output: ['x', 'x']
Por qué: caso límite: una pestaña nueva no puede moverse en ninguna dirección

Pistas

0 / 3

Tiempo objetivo
O(n + Σk)
Espacio objetivo
O(n)

¿Lo que te frena es la idea y no el código? Listas doblemente enlazadas lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio