Design Browser History
You have a browser of a certain version with a history of visited websites. You want to design a data structure to store the history and implement the following functions: visit(url), back(steps), forward(steps). The visit function adds the current url to the history and clears all the forward history. The back function moves the current position back by the given number of steps and returns the current url. The forward function moves the current position forward by the given number of steps and returns the current url.
Constraints:
- 1 <= url.length <= 20
- 1 <= steps <= 100
- At most 10000 calls will be made to the functions
Examples:
Input: BrowserHistory browserHistory = new BrowserHistory("leetcode.com"); browserHistory.visit("google.com"); browserHistory.visit("facebook.com"); browserHistory.visit("youtube.com"); System.out.println(browserHistory.back(1)); System.out.println(browserHistory.back(1)); System.out.println(browserHistory.forward(1)); System.out.println(browserHistory.visit("linkedin.com"));
Output: ["facebook.com", "google.com", "facebook.com", "linkedin.com"]
Explanation: The browser history is initially at leetcode.com. After visiting google.com, facebook.com, and youtube.com, the history is [leetcode.com, google.com, facebook.com, youtube.com]. After back(1), the current url is facebook.com. After back(1), the current url is google.com. After forward(1), the current url is facebook.com. After visiting linkedin.com, the history is [leetcode.com, google.com, facebook.com, linkedin.com] and the current url is linkedin.com.
Solutions
Using two stacks
We use two stacks to store the history. The first stack stores the history from the beginning to the current position, and the second stack stores the history from the current position to the end. When we visit a new url, we clear the second stack and add the new url to the first stack. When we go back, we pop the top url from the first stack and push it to the second stack. When we go forward, we pop the top url from the second stack and push it to the first stack.
class BrowserHistory {
public:
BrowserHistory(string homepage) {
history.push_back(homepage);
currentIndex = 0;
}
void visit(string url) {
while (history.size() > currentIndex + 1) {
history.pop_back();
}
history.push_back(url);
currentIndex++;
}
string back(int steps) {
currentIndex = max(0, currentIndex - steps);
return history[currentIndex];
}
string forward(int steps) {
currentIndex = min((int)history.size() - 1, currentIndex + steps);
return history[currentIndex];
}
private:
vector<string> history;
int currentIndex;
}
;Follow-up:
How would you optimize the solution if the number of visits is very large?
