Last Updated: 26 Sep, 2021
Design Browser History
Moderate
Asked in company
Your task is to maintain a data structure that supports the following functions of a web browser.
1- Browser(homepage): Set homepage of the browser
2- Visit(url): Visit the url from the current page. It clears up all the forward history.
3- Back(steps): Move ‘steps’ backward in the browser history
4- Forward(steps): Move ‘steps’ forward in the browser history
Note:
If you can’t move steps forward or backward, just return the last website that can be reached.
The Queries are in the given format-:
The first line of each query contains the string representing the homepage of the web browser.
(1, url): Visit the url from the current page.
(2, steps): Move ‘steps’ backward in the browser history.
(3, steps): Move ‘steps’ forward in the browser history.
For example:
You are queries as [[“homepage.com”], [1 , “facebook.com”], [1, “codingninjas.com”],[2, 1], [3, 1]]
1 query is the query that sets the homepage as “homepage.com”.
2 query is the query to visit “facebook.com”
3 query is the query to visit “codingninjas.com”
4 query is the query that moves back one step to “facebook.com”
5 query is the query that moves forward one step to “codingninjas.com”
Hence the answer is [“facebook.com”, “codingninjas.com”]
Input Format:
The first line of input contains a single integer ‘Q’, representing the number of queries.
The next line contains the homepage.
The next ‘Q-1’ lines contain space-separated strings and integers denoting the queries.
Output Format:
The output is a space-separated strings representing the output of the queries.
Note:
You do not need to print anything. It has already been taken care of. Just implement the function.
Approaches
In this approach, we will maintain a doubly linked list and keep track of the current node the linked list, each time we visit a website we will remove every node in front of current node and the new url as the current node in the linked list
We will create a Node(url) class where url is the URL of the given node, there are prev and next as previous and next node pointers respectively.
Algorithm:
- In the constructor(homepage)
- Initialise head as new instance of Node(homepage)
- Initialise curr equal to head
- In the visit(url) function
- Initialize node as new instance of Node(url)
- Set curr.next equal to node
- Set node.prev equal to curr
- Set curr equal to node
- In the back(steps) function
- While curr.prev is not null and steps is greater than 0
- Set curr equal to curr.prev
- Decrease steps by 1
- Return curr.url
- While curr.prev is not null and steps is greater than 0
- In the forward(steps) functions
- While curr.next is not null and steps is greater than 0
- Set curr equal to curr.next
- Decrease steps by 1
- Return curr.url
- While curr.next is not null and steps is greater than 0
In this approach, we maintain two stacks, one to store the history and another one every time we go back. We store the previous websites to it. We will reset the second stack each time we visit a website and only fill the stack if we do a back operation.
Algorithm:
- In the constructor(homepage)
- Initialize history as an empty stack
- Insert homepage in history
- Set future as an empty stack
- In the visit(url) function
- Insert url in history
- Set future as an empty stack
- In the back(steps) function
- While steps are greater than 0 and the size of history is greater than 1
- Insert the top element of history in future and pop the top element in history
- Decrease steps by 1
- While steps are greater than 0 and the size of history is greater than 1
- In the forward(steps) functions
- While steps are greater than 0 and the size of future is greater than 0
- Insert the top element of future in history and pop the top element in future
- Decrease steps by 1
- While steps are greater than 0 and the size of future is greater than 0
In this approach, we will maintain the single array of all the sites visited, every time we visit a new site, we remove all the sites in front of it. If we go back more than history has, then we simply return the last element of the list
Algorithm:
- In the constructor(homepage)
- Initialise history as an empty array
- Insert homepage in history
- Set pos as 0
- Set end as 0
- In the visit(url) function
- Increase pos by 1
- If size of history is equal to pos
- Insert url in history
- Otherwise,
- Set history[pos] as url
- Update end as pos
- In the back(steps) function
- Set pos as the maximum of 0 and pos - steps
- Return history[pos]
- In the forward(steps) functions
- Set pos as the minimum size of end and pos + steps
- Return history[pos]
Similar problems