Design Browser History

Suppose, We have a browser of one tab where we start on the homepage and we can visit another url, get back in the history number of steps or move forward in the history number of steps.
Implement the BrowserHistory class with following requirments:

BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
void visit(string url) Visits url from the current page. It clears up all the forward history.
string back(int steps) Move steps back in history. Assume, x is number of valid backward movements we can do from our current position. If steps > x, Return the url after moving x steps backward in history.

Here we have only 2 valid backward moves where given steps=5. So we will move X=2 steps backward and return Leetcode. Remember this operation will take O(n) Time for Linked List where n is the number of nodes in Linked List.

string forward(int steps) Move steps forward in history. Assume, x is number of valid forward steps we can move forward from our current position. If steps > x, Return the url after moving x steps forward in history.

Same as backward, we have 2 valid forward moved whereas given steps=5. So we will move x=2 steps forward and return Youtube. This operation will cost O(n) Time for Linked List where n is the number of nodes in Linked List

Intuition

By looking at the picture you already got the idea about the data structure. Yes we are going to use Doubly Linked List. However this is not the optimal solution but at least we've got an opportunity to solve a real world problem using Linked List. But before solving this problem you must solve Design a Doubly Linked List to get better understanding about Doubly Linked List.

Homepage

Let's launch the BrowserHistory instance with Homepage BrowserHistory(string homepage).

# Doubly Linke List Node structure
class Node:
	def __init__(self, val: str, prev=None, next=None):
		self.val = val
		self.prev = prev
		self.next = next

class BrowserHistory:
	def __init__(self, homepage):
		self.curr = Node(homepage)

So what we are doing is creating a Node with the value of homepage=leetcode.com
Assets/Leetcode/LinkedList/design_browser_history/linked_list/3.png

Go Backward

OK Let's assume we have visited few pages after the Homepage and our Linked List is looking like bellow.
Assets/Leetcode/LinkedList/design_browser_history/linked_list/4.png
According to the picture, we can move only 2 steps backward. But the function back(steps: int) takes steps as parameter, so we need to make sure that we have not moved bellow the First Node (i.e. Homepage). Suppose the back function is invoked like this back(steps=5) but we can move backward until prev node is not null. This is more like finding Nth Node from Linked List that we have done before. Let's visualize the process.
Assets/Leetcode/LinkedList/design_browser_history/linked_list/5.png

class BrowserHistory:
	# skipping previous codes
	def back(steps: int) -> str:
		while self.curr.prev and steps > 0:
			self.curr = self.curr.prev
			steps -= 1
		return self.curr.val

This operation takes O(n) times where n is the Number of Nodes in the Linked List. Because Linked List doesn't have Index like Array, so we need to scan through the Linked List one by one Node which has O(n) time complexity.

Move Forward

Now we are at the First Node (i.e. Homepage), we can move only 2 nodes forward. Same as the back function the forward(steps: int) function takes steps as input parameter, so we need to make sure that we have not moved beyond the Last Node. Suppose the forward function is invoked like this forward(steps=5) but we can move forward until next node is not null.
Assets/Leetcode/LinkedList/design_browser_history/linked_list/6.png

class BrowserHistory
	def forward(steps: int) -> str:
		while self.curr.next and steps > 0:
			self.curr = self.curr.next
			steps -= 1
		return self.curr.val

Visit

Now let's implement visit(url: str) function. Basically visits url from the current page and clears up all the forward history. The current Linked List state as bellow
Assets/Leetcode/LinkedList/design_browser_history/linked_list/7.png
Now Let's visit a new page visit(url="wikipidia") and at this point we already know that curr is not null because the object has instantiated with homepage. Let's visualize the output of this code self.curr.next = Node(val=url, prev=self.curr)
Assets/Leetcode/LinkedList/design_browser_history/linked_list/8.png
What have created a new node with visited url and connected the current node with the new node. Now we need to mark the new node as current node self.curr = self.curr.next

You may think why Youtube is back linking with Google? Yes it is but it doesn't matter because we can never reach that Node (Youtube) without having a next pointer connected from Google to Youtube.
Ok, Let's write the code

class BrowserHistory:
	def visit(self, url: str) -> None:
		self.curr.next = Node(val=url, prev=self.curr)
		self.curr = self.curr.next

This operation takes O(1) time as we are appending a new now with current position.

Complete Code Snippet

class Node:
	def __init__(self, val: str, prev=Node, next=Node):
		self.val = val
		self.prev = prev
		self.next = next

class BrowserHistory:
	def __init__(self, homepage: str):
		self.curr = Node(val=homepage)
	
	def visit(self, url: str) -> None:
		self.curr.next = Node(val=url, prev=self.curr)
		self.curr = self.curr.next

	def back(self, steps: int) -> str:
		while self.curr.prev and steps > 0:
			self.curr = self.curr.prev
			steps -= 1
		return self.curr.val

	def forward(self, steps: int) -> str:
		while self.curr.next and steps > 0:
			self.curr = self.curr.next
			steps -= 1
		return self.curr.val

Again, this is not the optimal solution. Check out the Optimized solution here, Design Browser History (Optimized)

Complexity Analysis

Visit: O(1) constant time, because we are just appending a node next to the current node
Back: O(n) where n is the number of nodes in the Linked List
Forward: O(n) where n is the number of nodes in the Linked List

Thanks for Stopping by! Happy Leet coding

Connect with me on