Historial de atrás y adelante
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
Cada página necesita conocer tanto la página anterior como la siguiente, y back y forward solo recorren uno de esos enlaces.
Una visita no borra las páginas de adelante una por una. Hacer que la página actual apunte a una página siguiente totalmente nueva las vuelve inalcanzables de un solo movimiento.
Guarda un nodo por página con enlaces prev y next, y un puntero al nodo actual. La visita enlaza un nodo nuevo después del actual y se mueve allí; back y forward avanzan por prev o next hasta k veces y se detienen cuando el enlace está vacío.
- Tiempo objetivo
- O(n + Σk)
- Espacio objetivo
- O(n)
Solución
Cada página es un nodo con enlaces a la página anterior y a la siguiente, y un puntero marca dónde está la pestaña. Una visita cuelga un nodo nuevo después del actual, lo que corta en silencio las páginas de adelante anteriores, y luego se mueve a él. Back y forward siguen los enlaces prev o next un paso a la vez y se detienen en el primer enlace que falta, así que pasarse de largo no causa ningún problema. Una visita es O(1), un movimiento de k pasos es O(k) y el espacio es O(número de visitas).
class Page:
def __init__(self, url, prev=None): self.url, self.prev, self.next = url, prev, None
def run_history(home, ops):
current, seen = Page(home), []
for op, arg in ops:
if op == "visit":
current.next = Page(arg, current) # the old forward pages become unreachable
current = current.next
continue
for _ in range(arg): # back or forward, at most arg steps
step = current.prev if op == "back" else current.next
if step is None:
break
current = step
seen.append(current.url)
return seen
print(run_history("home", [("visit", "a"), ("visit", "b"), ("back", 1), ("visit", "c"), ("forward", 1), ("back", 5)])) # -> ['a', 'c', 'home']
print(run_history("x", [("back", 2), ("forward", 3)])) # -> ['x', 'x']
print(run_history("x", [])) # -> []¿Lo que te frena es la idea y no el código? Listas doblemente enlazadas lo explica.