Design Browser History

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

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.

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”]

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.

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”]

Doubly Linked List

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
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

Time Complexity

O(Q*M), Where Q is the number of queries and M is the number of average steps.

We are iterating over each query once hence which will take O(Q) time. For back and forward operations, the time required will be O(M). Hence the overall time complexity is O(Q*M).

Space Complexity

O(Q), Where Q is the number of queries.

We are maintaining a doubly linked list which in the worst case will take O(Q) space. Hence the final space complexity is O(Q).

Problem statement

Sample Input 1:

Explaination:

Sample Output 1

Sample Input 2:

Sampe Output 2:

Constraints: