Design Browser History

Data Structure & Algorithm

Problem Statement

Implementation

class ListNode:
def __init__(self, val = 0, prev= None, nxt = None):
self.val = val
self.prev = prev
self.nxt = nxt
class BrowserHistory(object):def __init__(self, homepage):
"""
:type homepage: str
"""
self.node = ListNode(homepage)
self.last = self.node
def visit(self, url):
"""
:type url: str
:rtype: None
"""
self.last.nxt = ListNode(url)
self.last.nxt.prev = self.last
self.last = self.last.nxt
def back(self, steps):
"""
:type steps: int
:rtype: str
"""
while steps and self.last.prev:
steps -= 1
self.last = self.last.prev

return self.last.val
def forward(self, steps):
"""
:type steps: int
:rtype: str
"""
while steps and self.last.nxt:
steps -= 1
self.last = self.last.nxt

return self.last.val

Testing

["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"] 
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Time Complexity

O(N)

A Machine Learning & technology explorer with the drive to learn, apply, and expand his mind.