Design Browser History

Problem Statement

In this scenario, you are working with a simple web browser that supports basic navigation functionalities in a single tab. The capabilities you need to implement include visiting a new URL from the current one, moving backward in the visitation history by a certain number of steps, and moving forward through the same history by a specified number of steps. The class BrowserHistory should be designed with methods to handle these functionalities:

• BrowserHistory(string homepage): This initializes the browser with the given homepage URL.
• void visit(string url): This method should allow the browser to visit a new URL. The forward history from the current page gets cleared as a new URL is visited.
• string back(int steps): This retrieves the URL after moving back a given number of steps in the history. Should the desired steps exceed available history, it returns the furthest possible.
• string forward(int steps): This retrieves the URL after advancing forward by the specified steps. If the desired forward movement exceeds the tracked forward history, it returns as far forward as possible.

The objective is to manage the browser's history effectively, ensuring that movements forward and backward adjust the current position and potential future movements accordingly.

Examples

Example 1

Input:

["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["vultr.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","vultr.com"]

Explanation:

BrowserHistory browserHistory = new BrowserHistory("vultr.com");
browserHistory.visit("google.com"); // You are in "vultr.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 "vultr.com". return "vultr.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.

Approach and Intuition

To understand the approach required to simulate the browser history, let's analyze the example provided:

• Initialization:

  • The browser is initialized at "vultr.com".

• Visiting URLs:

  • Visits are registered sequentially from "google.com" to "youtube.com", each time clearing forward navigation possible from the current page.

• Moving Back:

  • It's then asked to move back first by 1 step from "youtube.com" to "facebook.com", and then another step back lands it at "google.com".

• Moving Forward:

  • Moving forward by 1 step from "google.com" brings it back to "facebook.com".

• More Visiting:

  • Visiting "linkedin.com" from "facebook.com" clears any forward history entirely.

• Attempts to Move Forward:

  • Any attempt to move forward beyond this point results in staying on "linkedin.com" because there are no forward entries.

• Moving Back Further:

  • Moving back by 2 steps from "linkedin.com" takes the browser to "google.com" through "facebook.com".
  • An attempt to move back by 7 steps from "google.com" brings it only back to the homepage "vultr.com", which is the furthest back it can go.

From the example, the critical operational details emerge:

• Navigating the website: Each visit should dynamically adjust the history stack.
• Bounds of navigation: Both the back and forward operations are bound by the current position in the history and the extremities of the history list (either the beginning or the most recent page).

The design of BrowserHistory can effectively be achieved using a list to keep track of visited URLs and an index pointer to the current URL. The operations adapt the current position pointing to handle the navigation requests within the constraints of available history.

Solutions

class NavigationHistory {
    vector<string> history;
    int currentIdx, lastIdx;
public:
    NavigationHistory(string startPage) {
        history.push_back(startPage);
        currentIdx = 0;
        lastIdx = 0;
    }
        
    void visit(string url) {
        currentIdx += 1;
        if (history.size() > currentIdx) {
            history[currentIdx] = url;
        } else {
            history.push_back(url);
        }
        lastIdx = currentIdx;
    }
        
    string back(int steps) {
        currentIdx = max(0, currentIdx - steps);
        return history[currentIdx];
    }
        
    string forward(int steps) {
        currentIdx = min(lastIdx, currentIdx + steps);
        return history[currentIdx];
    }
};