Design Browser History

Data Structure & Algorithm

Problem Statement

You have a browser of one tab where you start on the homepage and you can visit another URL, get back in the history number of steps or move forward in the history number of steps.

Functionalities to Implement:

• visit(url) → Visits URL from the current page. It clears up all the forward history.
• back(steps) → Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps.
• forward(steps) → Move steps forward in history.

Implementation

Create a Linked List type of structure as below:

class ListNode:
    def __init__(self, val = 0, prev= None, nxt = None):
        self.val = val
        self.prev = prev
        self.nxt = nxt

Implement Browser History:

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

Below is input test data:

["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]]

Output result from the algorithm:

[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Time Complexity

O(N)