Solution For Design Browser History

Design Browser History problem on LeetCode is a problem that requires you to implement a class BrowserHistory that represents the history of a browser as a doubly linked list. The browser history should support the following operations:

1. visit(url): Adds a new url to the history and sets it as the current page.
2. back(steps): Moves back by steps in the history. If there are not enough pages in the history, then move to the first page.
3. forward(steps): Moves forward by steps in the history. If there are not enough pages in the history, then move to the last page.
4. getCurrentUrl(): Returns the current url.
5. clearHistory(): Clears the history.

To solve this problem, we can implement the BrowserHistory class using a doubly linked list. We will have a head and a tail pointer that will represent the first and last nodes in the list respectively. We will also keep track of the current node, which will be the node that represents the current page.

To implement the visit(url) operation, we will create a new node and append it to the end of the list. We will set the current node to this new node.

To implement the back(steps) operation, we will move back steps nodes in the list, starting from the current node. If we reach the head of the list, we will stop at the head. We will update the current node to be the node we stopped at.

To implement the forward(steps) operation, we will move forward steps nodes in the list, starting from the current node. If we reach the tail of the list, we will stop at the tail. We will update the current node to be the node we stopped at.

To implement the getCurrentUrl() operation, we will return the url of the current node.

To implement the clearHistory() operation, we will set the head and tail pointers to null, and set the current node to null.

Here’s the code implementation in Java:

class Node {
String url;
Node prev;
Node next;
public Node(String url) {
this.url = url;
this.prev = null;
this.next = null;
}
}

class BrowserHistory {
Node head;
Node tail;
Node curr;
public BrowserHistory(String homepage) {
head = new Node(homepage);
tail = head;
curr = head;
}
public void visit(String url) {
Node node = new Node(url);
tail.next = node;
node.prev = tail;
tail = node;
curr = tail;
}
public String back(int steps) {
while (curr.prev != null && steps > 0) {
curr = curr.prev;
steps–;
}
return curr.url;
}
public String forward(int steps) {
while (curr.next != null && steps > 0) {
curr = curr.next;
steps–;
}
return curr.url;
}
public String getCurrentUrl() {
return curr.url;
}
public void clearHistory() {
head = null;
tail = null;
curr = null;
}
}

The time complexity of all the operations is O(steps) because we are traversing steps nodes in the list. The space complexity of the class is O(n) because we are creating and storing n nodes in the doubly linked list.

Step by Step Implementation For Design Browser History

You are given a browser history which consists of homepage URLs and clickable URLs on that page.

Implement the BrowserHistory class:

BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
void visit(string url) visits url from the current page. It clears up all the forward history.
string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.

 

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.
*/

class BrowserHistory {
    List urls;
    int cur;
    public BrowserHistory(String homepage) {
        urls = new ArrayList<>();
        urls.add(homepage);
        cur = 0;
    }
    
    public void visit(String url) {
        urls = urls.subList(0, cur + 1);
        urls.add(url);
        cur++;
    }
    
    public String back(int steps) {
        cur = Math.max(0, cur - steps);
        return urls.get(cur);
    }
    
    public String forward(int steps) {
        cur = Math.min(urls.size() - 1, cur + steps);
        return urls.get(cur);
    }
}

class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.cur = 0
        

    def visit(self, url: str) -> None:
        self.history = self.history[:self.cur+1]
        self.history.append(url)
        self.cur += 1
        

    def back(self, steps: int) -> str:
        self.cur = max(0, self.cur-steps)
        return self.history[self.cur]
        

    def forward(self, steps: int) -> str:
        self.cur = min(len(self.history)-1, self.cur+steps)
        return self.history[self.cur]

// Your browser history consists of URLs you have visited // in the order they were visited. Implement the BrowserHistory // class:

class BrowserHistory {
  constructor(homepage) {
    // Initialize your data structure here
    // The homepage is the first url you visit
    this.history = [homepage];
    this.current = 0;
  }

  visit(url) {
    // adds url to history in the order it was visited
    this.history.push(url);
    this.current += 1;
  }

  back(steps) {
    // Moves back in history by the given number of steps.
    // If you go back further than the available history, you stop at the first page.
    this.current = Math.max(0, this.current - steps);
  }

  forward(steps) {
    // Moves forward in history by the given number of steps.
    // If you go forward further than the available history, you stop at the last page.
    this.current = Math.min(this.history.length - 1, this.current + steps);
  }

  current() {
    // returns the current url
    return this.history[this.current];
  }
}

class BrowserHistory {
public:
    BrowserHistory(string homepage) {
        this->homepage = homepage;
        this->cur = 0;
    }
    
    void visit(string url) {
        this->history.erase(this->history.begin() + this->cur + 1, this->history.end());
        this->history.push_back(url);
        this->cur++;
    }
    
    string back(int steps) {
        this->cur = max(0, this->cur - steps);
        return this->history[this->cur];
    }
    
    string forward(int steps) {
        this->cur = min((int)this->history.size() - 1, this->cur + steps);
        return this->history[this->cur];
    }
private:
    vector history;
    int cur;
    string homepage;
};

using System; 

public class BrowserHistory {
    
    List history;
    int currentPage;
    
    public BrowserHistory(string homepage) {
        history = new List();
        history.Add(homepage);
        currentPage = 0;
    }
    
    public void Visit(string url) {
        history.Add(url);
        currentPage++;
    }
    
    public string Back(int steps) {
        currentPage = Math.Max(0, currentPage - steps);
        return history[currentPage];
    }
    
    public string Forward(int steps) {
        currentPage = Math.Min(history.Count - 1, currentPage + steps);
        return history[currentPage];
    }
}