Intuition
- The most straightforward way to solve this is by having a forward and backward history, along with a current site variable, then clearing the forward history whenever you visit a site. However, this is for each forward and backward move.
- An improvement is to use a Linked List which allows for clearing the forward history easily, but you still have to traverse forward and backward with difficulty.
- To achieve time, you can simply have a length variable which keeps track of where the proper end of the forward history is.
Complexity
Runtime
since we are only ever doing one operation with the pre-initialized array or history with history skip variable i.
Space
since there can be steps elements in the history.
Code
No Pre-initialization
class BrowserHistory:
def __init__(self, homepage: str):
self.history = [homepage]
self.i = 0
self.len = 1
def visit(self, url: str) -> None:
self.i += 1
if self.i >= len(self.history):
self.history.append(url)
else:
self.history[self.i] = url
self.len = self.i + 1
def back(self, steps: int) -> str:
if self.i - steps >= 0:
self.i = self.i - steps
else:
self.i = 0
return self.history[self.i]
def forward(self, steps: int) -> str:
if self.i + steps < self.len:
self.i = self.i + steps
else:
self.i = self.len - 1
return self.history[self.i]
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)Pre-Initialized Array
class BrowserHistory:
def __init__(self, homepage: str):
self.history = ["" for _ in range(5000)]
self.history[0] = homepage
self.i = 0
self.len = 1
def visit(self, url: str) -> None:
self.i += 1
self.history[self.i] = url
self.len = self.i + 1
def back(self, steps: int) -> str:
if self.i - steps >= 0:
self.i = self.i - steps
else:
self.i = 0
return self.history[self.i]
def forward(self, steps: int) -> str:
if self.i + steps < self.len:
self.i = self.i + steps
else:
self.i = self.len - 1
return self.history[self.i]
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)Linked List
class DoubleLL:
def __init__(self, val, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
class BrowserHistory:
def __init__(self, homepage: str):
self.current = DoubleLL(homepage)
self.tail = self.current
def visit(self, url: str) -> None:
self.current.next = DoubleLL(url)
self.current.next.prev = self.current
self.current = self.current.next
self.tail = self.current
def back(self, steps: int) -> str:
while self.current.prev and steps > 0:
self.current = self.current.prev
steps -= 1
return self.current.val
def forward(self, steps: int) -> str:
while self.current.next and steps > 0:
self.current = self.current.next
steps -= 1
return self.current.val
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)Brute Force Array
class BrowserHistory:
def __init__(self, homepage: str):
self.backward_history = []
self.forward_history = []
self.current = homepage
def visit(self, url: str) -> None:
self.forward_history.clear()
self.backward_history.append(self.current)
self.current = url
def back(self, steps: int) -> str:
while self.backward_history and steps > 0:
self.forward_history.append(self.current)
self.current = self.backward_history.pop()
steps -= 1
return self.current
def forward(self, steps: int) -> str:
while self.forward_history and steps > 0:
self.backward_history.append(self.current)
self.current = self.forward_history.pop()
steps -= 1
return self.current
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)Notes
Cards
START Basic Front: Design Browser History Back: Use a length variable to keep track of the proper end of the history. END