Techno Blender
Digitally Yours.

Design custom Browser History based on given operations

0 14


back(1) 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 = “geeksforgeeks.org”
visit(“amazon.com”);
back(2);
Output: geeksforgeeks.org
Explanation:  We need to move 2 steps back but since only 1 step is available we would land up at the homepage, i.e., geeksforgeeks.org

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);
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:   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.
  • 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.

visit(“gogle.com”), visit(“facebook.com”), visit(“youtube.com”)

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. 

back(1)

back(1)

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. 

back(1)

back(1)

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. 

forward(1)

forward(1)

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.

visit(

visit(“linkedin.com”)

9th operation: We cannot move 2 steps forward since there is no URL beyond the current page. We will return linkedin.com. 

forward(2)

forward(2)

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.

back(2)

back(2)

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. 

back(7)

back(7)

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

  

class BrowserHistory {

public:

    stack<string> backStack, forwardStack;

  

    

    

    BrowserHistory(string homepage)

    {

        backStack.push(homepage);

    }

  

    

    void visit(string url)

    {

        while (!forwardStack.empty()) {

            forwardStack.pop();

        }

        backStack.push(url);

    }

  

    

    

    string back(int steps)

    {

        while (backStack.size() > 1 && steps--) {

            forwardStack.push(backStack.top());

            backStack.pop();

        }

        return backStack.top();

    }

  

    

    

    string forward(int steps)

    {

        while (!forwardStack.empty() && steps--) {

            backStack.push(forwardStack.top());

            forwardStack.pop();

        }

        return backStack.top();

    }

};

  

int main()

{

  

    

    string homepage;

    homepage = "gfg.org";

  

    

    

    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;

}

Output
facebook.com
google.com
facebook.com
linkedin.com
google.com
gfg.org

Time complexity: O(N)
Auxiliary Space: O(K)

Related Articles:


back(1) 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 = “geeksforgeeks.org”
visit(“amazon.com”);
back(2);
Output: geeksforgeeks.org
Explanation:  We need to move 2 steps back but since only 1 step is available we would land up at the homepage, i.e., geeksforgeeks.org

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);
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:   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.
  • 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.

visit(

visit(“gogle.com”), visit(“facebook.com”), visit(“youtube.com”)

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. 

back(1)

back(1)

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. 

back(1)

back(1)

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. 

forward(1)

forward(1)

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.

visit(

visit(“linkedin.com”)

9th operation: We cannot move 2 steps forward since there is no URL beyond the current page. We will return linkedin.com. 

forward(2)

forward(2)

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.

back(2)

back(2)

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. 

back(7)

back(7)

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

  

class BrowserHistory {

public:

    stack<string> backStack, forwardStack;

  

    

    

    BrowserHistory(string homepage)

    {

        backStack.push(homepage);

    }

  

    

    void visit(string url)

    {

        while (!forwardStack.empty()) {

            forwardStack.pop();

        }

        backStack.push(url);

    }

  

    

    

    string back(int steps)

    {

        while (backStack.size() > 1 && steps--) {

            forwardStack.push(backStack.top());

            backStack.pop();

        }

        return backStack.top();

    }

  

    

    

    string forward(int steps)

    {

        while (!forwardStack.empty() && steps--) {

            backStack.push(forwardStack.top());

            forwardStack.pop();

        }

        return backStack.top();

    }

};

  

int main()

{

  

    

    string homepage;

    homepage = "gfg.org";

  

    

    

    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;

}

Output
facebook.com
google.com
facebook.com
linkedin.com
google.com
gfg.org

Time complexity: O(N)
Auxiliary Space: O(K)

Related Articles:

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.
Leave a comment