Design custom Browser History based on given operations
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. The task is to design a data structure and implement the functionality of visiting a URL starting from the homepage and moving back and forward in the history. The following functionalities should be covered:
- visit(page)
- forward(step)
- back(step)
Note: The starting page of the tab will always be the homepage.
Examples:
Input:
homepage = “w3wiki.net”
visit(“amazon.com”);
back(2);
Output: w3wiki.net
Explanation: We need to move 2 steps back but since only 1 step is available we would land up at the homepage, i.e., w3wiki.netInput:
homepage = “gfg.org”
visit(“google.com”);
visit(“facebook.com”);
visit(“youtube.com”);
back(1);
back(1);
forward(1);
visit(“linkedin.com”);
forward(2);
back(2);
back(7);
Output:
facebook.com
google.com
facebook.com
linkedin.com
google.com
gfg.org
Explanation:
visit(“google.com”) : We are at google.com
visit(“facebook.com”): Now, we are at facebook.com
visit(“youtube.com”): We are at youtube.com
back(1): We would land up at facebook.com, if we move one step back.
back(1): Moving one step back, takes us to google.com
forward(1): Moving a step forward we would be at facebook.com
visit(“linkedin.com”): We are at linkedin.com
forward(2): We are still at linkedin. since visiting clear the forward history . When we are the current URL, there is no URL to move forward to.
back(2): Moving two steps back, takes us to google.com
back(7): We need to move 7 steps back, but only 1 url is available. Therefore we would return gfg.org.
Approach 1: The problem can be solved efficiently using stack based on the following idea:
We can implement a browser history design by employing two stacks. We need a stack to keep track of the previously visited URLs and another stack to store the current URL on the browser tab.
Follow the steps mentioned below to implement the idea:
- Create two stacks, backStack, and forwardStack.
- A backStack stores the current URL, while a forwardStack keeps track of previously visited URLs.
- The constructor BrowserHistory(string homepage) initializes the object with the homepage of the browser. Push the homepage into backStack.
- We have a visit() function to visit a URL from the current page:
- While visiting a URL, the forward history gets cleared up. Since there will be nothing beyond the last visited URL. So, pop all the elements from the forwardStack and then push the URL we need to visit in the backSTack.
- We have a back() function to move backward in history and return to the current page. The steps represent the number of steps we need to move.
- To move steps back, run a while loop till there is at least one element left in the backStack or we have moved step number of times.
- Push the top of the backStack into the forwardStack and then pop it from the backStack. Return the topmost element from the backStack.
- If we can only return x steps in the history and steps > x, we will return only x steps.
- To move steps back, run a while loop till there is at least one element left in the backStack or we have moved step number of times.
- There is a forward() function to move steps forward in history and return the current page.
- To move steps forward, run a while loop for steps numbers of times and till the stack is not empty push the top element of forwardStack into backStack and then pop it from the forwardStack.
- Return the top value of backStack.
Follow the below illustration for a better understanding:
Illustration:
input:
homepage = “gfg.org”
visit(“google.com”);
visit(“facebook.com”);
visit(“youtube.com”);
back(1);
back(1);
forward(1);
visit(“linkedin.com”);
forward(2);
back(2);
back(7);Operations:
1st operation: Initialising gfg.org as the homepage and pushing it into the backStack.
2nd, 3rd and 4th operation: Visiting google.com, facebook.com, and youtube.com. So, push all of these into the backStack.
5th operation: Move one step back in the browser history. Take youtube.com from the backStack and push it into the forwardStack to keep track of it. After moving one step back, we would land on facebook.com. So, the current page is facebook.com.
6th operation: Again we will move one step back by popping the topmost element of the backStack and pushing the same into the forwardStack. After moving one step back, we will be on google.com.
7th operation: Move one step forward. We moved to facebook.com after visiting google.com. Therefore, from the forwardStack, we will pick its top and push it into the backStack. facebook.com now serves as the current page.
8th operation: Now, for visiting another URL, we will push linkedin.com into the backStack. Since this is the most recent URL and there is nothing beyond this, we would clear the forwardStack.
9th operation: We cannot move 2 steps forward since there is no URL beyond the current page. We will return linkedin.com.
10th operation: To move 2 steps back, pop linkedin.com and facebook.com and push them into the forwardStack. Now the current page turns out to be google.com.
11th operation: We need to move 7 steps back, but we only have one URL after the homepage. We cannot move back in history beyond the homepage. Therefore, the homepage is the current page. We will return gfg.org.
Below is the implementation of the above approach:
C++
// C++ Implementation of the approach #include <bits/stdc++.h> using namespace std; class BrowserHistory { public : stack<string> backStack, forwardStack; // Constructor to initialize object with // homepage BrowserHistory(string homepage) { backStack.push(homepage); } // Visit current url void visit(string url) { while (!forwardStack.empty()) { forwardStack.pop(); } backStack.push(url); } // 'steps' move backward in history and // return current page string back( int steps) { while (backStack.size() > 1 && steps--) { forwardStack.push(backStack.top()); backStack.pop(); } return backStack.top(); } // 'steps' move forward and return // current page string forward( int steps) { while (!forwardStack.empty() && steps--) { backStack.push(forwardStack.top()); forwardStack.pop(); } return backStack.top(); } }; // Driver Code int main() { // Input case : string homepage; homepage = "gfg.org" ; // Initialise the object of Browser // History BrowserHistory obj(homepage); string url = "google.com" ; obj.visit(url); url = "facebook.com" ; obj.visit(url); url = "youtube.com" ; obj.visit(url); cout << obj.back(1) << endl; cout << obj.back(1) << endl; cout << obj.forward(1) << endl; obj.visit( "linkedin.com" ); cout << obj.forward(2) << endl; cout << obj.back(2) << endl; cout << obj.back(7) << endl; return 0; } // } Driver Code Ends |
Java
// Java Implementation of the approach import java.io.*; import java.util.*; class GFG { static class BrowserHistory { Stack<String> backStack = new Stack<>(); Stack<String> forwardStack = new Stack<>(); // Constructor to initialize object with // homepage BrowserHistory(String homepage) { backStack.push(homepage); } // Visit current url void visit(String url) { while (!forwardStack.isEmpty()) { forwardStack.pop(); } backStack.push(url); } // 'steps' move backward in history and // return current page String back( int steps) { while (backStack.size() > 1 && steps-- > 0 ) { forwardStack.push(backStack.peek()); backStack.pop(); } return backStack.peek(); } // 'steps' move forward and return // current page String forward( int steps) { while (!forwardStack.isEmpty() && steps-- > 0 ) { backStack.push(forwardStack.peek()); forwardStack.pop(); } return backStack.peek(); } } public static void main(String[] args) { // Input case : String homepage = "gfg.org" ; // Initialise the object of Browser History BrowserHistory obj = new BrowserHistory(homepage); String url = "google.com" ; obj.visit(url); url = "facebook.com" ; obj.visit(url); url = "youtube.com" ; obj.visit(url); System.out.println(obj.back( 1 )); System.out.println(obj.back( 1 )); System.out.println(obj.forward( 1 )); obj.visit( "linkedin.com" ); System.out.println(obj.forward( 2 )); System.out.println(obj.back( 2 )); System.out.println(obj.back( 7 )); } } // This code is contributed by lokeshmvs21. |
Python3
# Python implementation of the approach class BrowserHistory: # Constructor to initialize object with homepage def __init__( self , homepage: str ): self .backStack = [homepage] self .forwardStack = [] # Visit current url def visit( self , url: str ): self .forwardStack.clear() self .backStack.append(url) # 'steps' move backward in history and return current page def back( self , steps: int ): while len ( self .backStack) > 1 and steps > 0 : self .forwardStack.append( self .backStack.pop()) steps - = 1 return self .backStack[ - 1 ] # 'steps' move forward and return current page def forward( self , steps: int ): while len ( self .forwardStack) > 0 and steps > 0 : self .backStack.append( self .forwardStack.pop()) steps - = 1 return self .backStack[ - 1 ] # Input case homepage = "gfg.org" obj = BrowserHistory(homepage) url = "google.com" obj.visit(url) url = "facebook.com" obj.visit(url) url = "youtube.com" obj.visit(url) print (obj.back( 1 )) print (obj.back( 1 )) print (obj.forward( 1 )) obj.visit( "linkedin.com" ) print (obj.forward( 2 )) print (obj.back( 2 )) print (obj.back( 7 )) |
C#
// C# Implementation of the approach using System; using System.Collections.Generic; public class GFG { class BrowserHistory { Stack< string > backStack = new Stack< string >(); Stack< string > forwardStack = new Stack< string >(); // Constructor to initialize object with homepage public BrowserHistory( string homepage) { backStack.Push(homepage); } // Visit current url public void Visit( string url) { while (forwardStack.Count > 0) { forwardStack.Pop(); } backStack.Push(url); } // 'steps' move backward in history and return // current page public string Back( int steps) { while (backStack.Count > 1 && steps-- > 0) { forwardStack.Push(backStack.Peek()); backStack.Pop(); } return backStack.Peek(); } // 'steps' move forward and return current page public string Forward( int steps) { while (forwardStack.Count > 0 && steps-- > 0) { backStack.Push(forwardStack.Peek()); forwardStack.Pop(); } return backStack.Peek(); } } static public void Main() { // Input case: string homepage = "gfg.org" ; // Initialize the object of BrowserHistory BrowserHistory obj = new BrowserHistory(homepage); string url = "google.com" ; obj.Visit(url); url = "facebook.com" ; obj.Visit(url); url = "youtube.com" ; obj.Visit(url); Console.WriteLine(obj.Back(1)); Console.WriteLine(obj.Back(1)); Console.WriteLine(obj.Forward(1)); obj.Visit( "linkedin.com" ); Console.WriteLine(obj.Forward(2)); Console.WriteLine(obj.Back(2)); Console.WriteLine(obj.Back(7)); } } // This code is contributed by lokesh. |
Javascript
// JavaScript Implementation of the approach class BrowserHistory { constructor(homepage) { this .backStack = []; this .forwardStack = []; // Initialize object with homepage this .backStack.push(homepage); } // Visit current URL visit(url) { this .forwardStack = []; this .backStack.push(url); } // 'steps' move backward in history and return // current page back(steps) { while ( this .backStack.length > 1 && steps-- > 0) { this .forwardStack.push( this .backStack[ this .backStack.length - 1]); this .backStack.pop(); } return this .backStack[ this .backStack.length - 1]; } // 'steps' move forward and return //current page forward(steps) { while ( this .forwardStack.length > 0 && steps-- > 0) { this .backStack.push( this .forwardStack[ this .forwardStack.length - 1]); this .forwardStack.pop(); } return this .backStack[ this .backStack.length - 1]; } } // Driver Code // Input case let homepage = "gfg.org" ; // Initialize the object of BrowserHistory let obj = new BrowserHistory(homepage); let url = "google.com" ; obj.visit(url); url = "facebook.com" ; obj.visit(url); url = "youtube.com" ; obj.visit(url); console.log(obj.back(1)); console.log(obj.back(1)); console.log(obj.forward(1)); obj.visit( "linkedin.com" ); console.log(obj.forward(2)); console.log(obj.back(2)); console.log(obj.back(7)); // This code is contributed by rutikbhosale. |
facebook.com google.com facebook.com linkedin.com google.com gfg.org
Time complexity: O(N)
Auxiliary Space: O(K)
Approach 2: Using a Doubly Linkeded List
- First Create a class Node have attributes as a link, Previous (Denoting the previous Node), Next (Denoting Next Node)
- Node Made class BrowserHistory have attribute as Node Current where Current denotes the website in which you are currently
- The constructor BrowserHistory(string homepage) initializes the object with the homepage of the browser set Current Node as current.link=homepage
- We have a visit(String url) function to visit a URL from the current page: when visit(String url) is called it will a made new node have a link as URL and Previous as Current and Next as null then we will change the pointer of Current.next to the new node that we made then just do one thing make new Node as Current Node
- For Function forward(int step) we will travel in a forward direction in the list and if attend the end of the string before completing all steps then we return the last link and if all steps are complete then we will return Node.link that travelling
- For Function back(int step) we will do similar to forward just that we travel in the opposite direction
Below is the implementation of the above approach:
C++
#include <iostream> #include <string> using namespace std; // Node of Doubly Linked List class Node { public : string link; Node* Previous; Node* Next; Node(string link) { this ->link = link; this ->Previous = nullptr; this ->Next = nullptr; } }; class BrowserHistory { public : // This Node Reprsent in which url are currently Node* Current; BrowserHistory(string homepage) { // visiting Homepage and seting Current Node to this // Homepage Current = new Node(homepage); } void visit(string url) { // Creating a node for this Visit Node* url_Node = new Node(url); // This Visited After the current so its previous as // current url_Node->Previous = Current; // now seting current.next as url_Node as after // Current we visited the url_Node Current->Next = url_Node; // Now Finnaly Updating Current as url is visited Current = url_Node; } string back( int step) { Node* temp = Current; // travel step time back if possile while (temp->Previous != nullptr && step > 0) { temp = temp->Previous; step--; } // After step back then updating Current Current = temp; return Current->link; } string forward( int step) { Node* temp = Current; // travel step time forward if possile while (temp->Next != nullptr && step > 0) { temp = temp->Next; step--; } // After step forward then updating Current Current = temp; return Current->link; } }; int main() { string homepage = "gfg.org" ; // Initialise the object of Browser History BrowserHistory obj(homepage); string url = "google.com" ; obj.visit(url); url = "facebook.com" ; obj.visit(url); url = "youtube.com" ; obj.visit(url); cout << obj.back(1) << endl; cout << obj.back(1) << endl; cout << obj.forward(1) << endl; obj.visit( "linkedin.com" ); cout << obj.forward(2) << endl; cout << obj.back(2) << endl; cout << obj.back(7) << endl; return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; // Node of Doubly Linked List class Node { // Link is url of that node String link; // From which Node/url you visited this link Node Previous; // After this you visit which link weill store in next Node Next; // constructor Node(String link) { this .link = link; this .Previous = null ; this .Next = null ; } } // BrowserHistory Class class BrowserHistory { // This Node Reprsent in which url are currently Node Current; public BrowserHistory(String homepage) { // visiting Homepage and seting Current Node to this // Homepage Current = new Node(homepage); } public void visit(String url) { // Creating a node for this Visit Node url_Node = new Node(url); // This Visited After the current so its previous as // current url_Node.Previous = Current; // now seting current.next as url_Node as after // Current we visited the url_Node Current.Next = url_Node; // Now Finnaly Updating Current as url is visited Current = url_Node; } public String back( int step) { Node temp = Current; // travel step time back if possile while (temp.Previous != null && step > 0 ) { temp = temp.Previous; step--; } // After step back then updating Current Current = temp; return Current.link; } public String forward( int step) { Node temp = Current; // travel step time forward if possile while (temp.Next != null && step > 0 ) { temp = temp.Next; step--; } // After step forward then updating Current Current = temp; return Current.link; } } class GFG { public static void main(String[] args) { // Input case : String homepage = "gfg.org" ; // Initialise the object of Browser History BrowserHistory obj = new BrowserHistory(homepage); String url = "google.com" ; obj.visit(url); url = "facebook.com" ; obj.visit(url); url = "youtube.com" ; obj.visit(url); System.out.println(obj.back( 1 )); System.out.println(obj.back( 1 )); System.out.println(obj.forward( 1 )); obj.visit( "linkedin.com" ); System.out.println(obj.forward( 2 )); System.out.println(obj.back( 2 )); System.out.println(obj.back( 7 )); // This Code and Approach Given By Vikas Bishnoi // User id:- vikas20noi } } |
Python3
# Node of Doubly Linked List class Node: # Link is url of that node def __init__( self , link): # From which Node/url you visited this link self .Previous = None # After this you visit which link weill store in next self . Next = None self .link = link # BrowserHistory Class class BrowserHistory: # This Node Reprsent in which url are currently def __init__( self , homepage): # visiting Homepage and seting Current Node to this # Homepage self .Current = Node(homepage) def visit( self , url): # Creating a node for this Visit url_Node = Node(url) # This Visited After the current so its previous as # current url_Node.Previous = self .Current # now seting current.next as url_Node as after # Current we visited the url_Node self .Current. Next = url_Node # Now Finnaly Updating Current as url is visited self .Current = url_Node def back( self , step): temp = self .Current # travel step time back if possile while temp.Previous and step > 0 : temp = temp.Previous step - = 1 # After step back then updating Current self .Current = temp return self .Current.link def forward( self , step): temp = self .Current # travel step time forward if possile while temp. Next and step > 0 : temp = temp. Next step - = 1 # After step forward then updating Current self .Current = temp return self .Current.link # Input case : homepage = "gfg.org" # Initialise the object of Browser History obj = BrowserHistory(homepage) url = "google.com" obj.visit(url) url = "facebook.com" obj.visit(url) url = "youtube.com" obj.visit(url) print (obj.back( 1 )) print (obj.back( 1 )) print (obj.forward( 1 )) obj.visit( "linkedin.com" ) print (obj.forward( 2 )) print (obj.back( 2 )) print (obj.back( 7 )) |
C#
using System; // Node of Doubly Linked List class Node { public string link; public Node Previous; public Node Next; public Node( string link) { this .link = link; this .Previous = null ; this .Next = null ; } } class BrowserHistory { // This Node Reprsent in which url are currently public Node Current; public BrowserHistory( string homepage) { // visiting Homepage and seting Current Node to this // Homepage Current = new Node(homepage); } public void visit( string url) { // Creating a node for this Visit Node url_Node = new Node(url); // This Visited After the current so its previous as // current url_Node.Previous = Current; // now seting current.next as url_Node as after // Current we visited the url_Node Current.Next = url_Node; // Now Finnaly Updating Current as url is visited Current = url_Node; } public string back( int step) { Node temp = Current; // travel step time back if possile while (temp.Previous != null && step > 0) { temp = temp.Previous; step--; } // After step back then updating Current Current = temp; return Current.link; } public string forward( int step) { Node temp = Current; // travel step time forward if possile while (temp.Next != null && step > 0) { temp = temp.Next; step--; } // After step forward then updating Current Current = temp; return Current.link; } } class Program { static void Main( string [] args) { string homepage = "gfg.org" ; // Initialise the object of Browser History BrowserHistory obj = new BrowserHistory(homepage); string url = "google.com" ; obj.visit(url); url = "facebook.com" ; obj.visit(url); url = "youtube.com" ; obj.visit(url); Console.WriteLine(obj.back(1)); Console.WriteLine(obj.back(1)); Console.WriteLine(obj.forward(1)); obj.visit( "linkedin.com" ); Console.WriteLine(obj.forward(2)); Console.WriteLine(obj.back(2)); Console.WriteLine(obj.back(7)); } } // This code is contributed by sarojmcy2e |
Javascript
class Node { constructor(link) { this .Previous = null ; // Represents the previous link/node in the history. this .Next = null ; // Represents the next link/node in the history. this .link = link; // Stores the URL of this node. } } class BrowserHistory { constructor(homepage) { this .Current = new Node(homepage); // Initialize with the homepage as the current node. } visit(url) { const urlNode = new Node(url); // Create a new node for the visited URL. urlNode.Previous = this .Current; // Set the previous node to the current node. this .Current.Next = urlNode; // Set the next node for the current node. this .Current = urlNode; // Update the current node to the newly visited URL. } back(step) { let temp = this .Current; // Travel 'step' times back if possible. while (temp.Previous && step > 0) { temp = temp.Previous; step--; } // After traveling back, update the current node. this .Current = temp; return this .Current.link; } forward(step) { let temp = this .Current; // Travel 'step' times forward if possible. while (temp.Next && step > 0) { temp = temp.Next; step--; } // After traveling forward, update the current node. this .Current = temp; return this .Current.link; } } // Input case const homepage = "gfg.org" ; const obj = new BrowserHistory(homepage); let url = "google.com" ; obj.visit(url); url = "facebook.com" ; obj.visit(url); url = "youtube.com" ; obj.visit(url); console.log(obj.back(1)); // Move back one step. console.log(obj.back(1)); // Move back one more step. console.log(obj.forward(1)); // Move forward one step. obj.visit( "linkedin.com" ); // Visit a new URL. console.log(obj.forward(2)); // Move forward two steps. console.log(obj.back(2)); // Move back two steps. console.log(obj.back(7)); // Move back seven steps. |
facebook.com google.com facebook.com linkedin.com google.com gfg.org
Time complexity: O(N)
Auxiliary Space: O(K)
Related Articles:
Contact Us