Leetcode: Design Browser History

 

This question is asked a lot at Bloomberg and DoorDash. Here it is:

You have a browser of one tab where you start on the homepage in which you can visit another url, get back in the history a number of steps and move forward the history a number of steps, and your objective is to implement the BrowserHistory class. Here's the constructor and methods:

The BrowserHistory(string homepage) initializes the object with the homepage of the browser. 

void visit(string url) visits the url from the current page and clears up all the forward history.

string back(int steps) move steps back in history. string forward(int steps) move steps forward in history. If you can only forward x steps in history you will forward only x steps. Here are the examples:

Example:

Input:

["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]

[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]

Output:

[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:

BrowserHistory browserHistory = new BrowserHistory("leetcode.com");

browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"

browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"

browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"

browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"

browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"

browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"

browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"

browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.

browserHistory.back(2);                   // You are in "linkedin.com", move back two steps to "facebook.com" then to "google.com". return "google.com"

browserHistory.back(7);                   // You are in "google.com", you can move back only one step to "leetcode.com". return "leetcode.com"

 

Constraints:

1 <= homepage.length <= 20

1 <= url.length <= 20

1 <= steps <= 100

homepage and url consist of  '.' or lower case English letters.

At most 5000 calls will be made to visit, back, and forward.

So, this problem will be obviously solved through a double stack. We need to be able to store the urls in the stack, and the 2 special cases is you must have one element in the history stack which is the page that is visited/at. Here's the C++ implementation:

class BrowserHistory {

    public:

        stack<string> history;

        stack<string> future;

        //adds to history and resets the forward stack

        BrowserHistory(string homepage) {

            history.push(homepage);

            future = stack<string>();

        }

        //adds to history and resets the forward stack.

        void visit(string url) {

            history.push(url);

            future = stack<string>();

        }

    

        //get the pages on the future stack to keep track of current visited page

        string back(int steps) {

            while(steps > 0 && history.size() > 1) {

                future.push(history.top());

                history.pop();

                steps--;

            }

             return history.top();

        }

         //get the future stacks back the number of stacks and return the top of the stack. 

         string forward(int steps) {

            while(steps > 0 && future.size() > 1) {

                history.push(future.top());

                future.pop();

                steps--;

            }

             return history.top();

        }

      

/**

*the instatiation is like obj->visit(url); string param_2 = obj->back(steps) string param_3 = obj->forward(steps);

*/

}