.jpg)
Design Browser History
Problem
Design a browser history system that supports visiting URLs and navigating back and forward.
Implement a class BrowserHistory with the following operations:
- BrowserHistory(homepage) → Initializes with homepage
- visit(url) → Visits a new URL and clears forward history
- back(steps) → Move back by given steps
- forward(steps) → Move forward by given steps
Return the current page after each operation.
Example
Operations
BrowserHistory("google.com")
visit("facebook.com")
visit("youtube.com")
back(1)
back(1)
forward(1)
visit("linkedin.com")
forward(2)
back(2)
back(7)
Output
google.com
facebook.com
youtube.com
facebook.com
google.com
facebook.com
linkedin.com
linkedin.com
google.com
google.com
Approach 1 — Using Doubly Linked List
Idea
Browser navigation naturally fits a Doubly Linked List because:
- Back → move to previous node
- Forward → move to next node
- Visit new page → remove forward history
Each node stores:
- URL
- prev pointer
- next pointer
Steps
- Create node for homepage
- Maintain pointer current
- visit(url):
- Create new node
- Attach after current
- Delete forward history
- Move current
- back(steps):
- Move current to prev up to steps
- forward(steps):
- Move current to next up to steps
Time Complexity
All operations → O(steps)
Worst case → O(N)
Space Complexity
O(N)
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
#include "string"
using namespace std;
class Node {
public:
string url;
Node* prev;
Node* next;
Node(string u) {
url = u;
prev = next = NULL;
}
};
class BrowserHistory {
Node* current;
public:
BrowserHistory(string homepage) {
current = new Node(homepage);
}
void visit(string url) {
Node* newNode = new Node(url);
current->next = newNode;
newNode->prev = current;
current = newNode;
}
string back(int steps) {
while (steps-- && current->prev)
current = current->prev;
return current->url;
}
string forward(int steps) {
while (steps-- && current->next)
current = current->next;
return current->url;
}
};
int main() {
BrowserHistory bh("google.com");
bh.visit("facebook.com");
bh.visit("youtube.com");
cout << bh.back(1) << endl;
cout << bh.back(1) << endl;
cout << bh.forward(1) << endl;
bh.visit("linkedin.com");
cout << bh.forward(2) << endl;
cout << bh.back(2) << endl;
cout << bh.back(7) << endl;
return 0;
}
Java Implementation
class Node {
String url;
Node prev, next;
Node(String u) {
url = u;
prev = null;
next = null;
}
}
class BrowserHistory {
Node current;
BrowserHistory(String homepage) {
current = new Node(homepage);
}
void visit(String url) {
Node node = new Node(url);
// Clear forward history
current.next = null;
node.prev = current;
current.next = node;
current = node;
}
String back(int steps) {
while (steps > 0 && current.prev != null) {
current = current.prev;
steps--;
}
return current.url;
}
String forward(int steps) {
while (steps > 0 && current.next != null) {
current = current.next;
steps--;
}
return current.url;
}
}
public class Main {
public static void main(String[] args) {
BrowserHistory bh = new BrowserHistory("google.com");
bh.visit("facebook.com");
bh.visit("youtube.com");
System.out.println(bh.back(1)); // facebook.com
System.out.println(bh.back(1)); // google.com
System.out.println(bh.forward(1)); // facebook.com
bh.visit("linkedin.com");
System.out.println(bh.forward(2)); // linkedin.com
System.out.println(bh.back(2)); // google.com
System.out.println(bh.back(7)); // google.com
}
}Python Implementation
class Node:
def __init__(self, url):
self.url = url
self.prev = None
self.next = None
class BrowserHistory:
def __init__(self, homepage):
self.current = Node(homepage)
def visit(self, url):
node = Node(url)
self.current.next = node
node.prev = self.current
self.current = node
def back(self, steps):
while steps and self.current.prev:
self.current = self.current.prev
steps -= 1
return self.current.url
def forward(self, steps):
while steps and self.current.next:
self.current = self.current.next
steps -= 1
return self.current.url
Output
facebook.com
google.com
facebook.com
linkedin.com
google.com
google.comApproach 2 — Using Two Stacks
Idea
Maintain two stacks:
- Back Stack → pages behind current
- Forward Stack → pages ahead of current
- Current Page
Operations:
Visit(url):
- Push current → back stack
- Set current = url
- Clear forward stack
Back(steps):
- Move current → forward stack
- Pop from back stack
Forward(steps):
- Move current → back stack
- Pop from forward stack
Time Complexity
O(1) per operation
Space Complexity
O(N)
Example Used
Operations
BrowserHistory("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
google.com
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
#include "stack"
#include "string"
using namespace std;
class BrowserHistory {
stack backStack;
stack forwardStack;
string current;
public:
BrowserHistory(string homepage) {
current = homepage;
}
void visit(string url) {
backStack.push(current);
current = url;
while (!forwardStack.empty())
forwardStack.pop();
}
string back(int steps) {
while (steps > 0 && !backStack.empty()) {
forwardStack.push(current);
current = backStack.top();
backStack.pop();
steps--;
}
return current;
}
string forward(int steps) {
while (steps > 0 && !forwardStack.empty()) {
backStack.push(current);
current = forwardStack.top();
forwardStack.pop();
steps--;
}
return current;
}
};
int main() {
BrowserHistory bh("google.com");
bh.visit("facebook.com");
bh.visit("youtube.com");
cout << bh.back(1) << endl;
cout << bh.back(1) << endl;
cout << bh.forward(1) << endl;
bh.visit("linkedin.com");
cout << bh.forward(2) << endl;
cout << bh.back(2) << endl;
cout << bh.back(7) << endl;
return 0;
}
Java Implementation
import java.util.Stack;
class BrowserHistory {
Stack backStack = new Stack<>();
Stack forwardStack = new Stack<>();
String current;
BrowserHistory(String homepage) {
current = homepage;
}
void visit(String url) {
backStack.push(current);
current = url;
forwardStack.clear();
}
String back(int steps) {
while (steps > 0 && !backStack.isEmpty()) {
forwardStack.push(current);
current = backStack.pop();
steps--;
}
return current;
}
String forward(int steps) {
while (steps > 0 && !forwardStack.isEmpty()) {
backStack.push(current);
current = forwardStack.pop();
steps--;
}
return current;
}
}
public class Main {
public static void main(String[] args) {
BrowserHistory bh = new BrowserHistory("google.com");
bh.visit("facebook.com");
bh.visit("youtube.com");
System.out.println(bh.back(1)); // facebook.com
System.out.println(bh.back(1)); // google.com
System.out.println(bh.forward(1)); // facebook.com
bh.visit("linkedin.com");
System.out.println(bh.forward(2)); // linkedin.com
System.out.println(bh.back(2)); // google.com
System.out.println(bh.back(7)); // google.com
}
}Python Implementation
class BrowserHistory:
def __init__(self, homepage):
self.backStack = []
self.forwardStack = []
self.current = homepage
def visit(self, url):
self.backStack.append(self.current)
self.current = url
self.forwardStack.clear()
def back(self, steps):
while steps and self.backStack:
self.forwardStack.append(self.current)
self.current = self.backStack.pop()
steps -= 1
return self.current
def forward(self, steps):
while steps and self.forwardStack:
self.backStack.append(self.current)
self.current = self.forwardStack.pop()
steps -= 1
return self.current
bh = BrowserHistory("google.com")
bh.visit("facebook.com")
bh.visit("youtube.com")
print(bh.back(1))
print(bh.back(1))
print(bh.forward(1))
bh.visit("linkedin.com")
print(bh.forward(2))
print(bh.back(2))
print(bh.back(7))
JavaScript Implementation
class BrowserHistory {
constructor(homepage) {
this.backStack = [];
this.forwardStack = [];
this.current = homepage;
}
visit(url) {
this.backStack.push(this.current);
this.current = url;
this.forwardStack = [];
}
back(steps) {
while (steps-- && this.backStack.length) {
this.forwardStack.push(this.current);
this.current = this.backStack.pop();
}
return this.current;
}
forward(steps) {
while (steps-- && this.forwardStack.length) {
this.backStack.push(this.current);
this.current = this.forwardStack.pop();
}
return this.current;
}
}
let bh = new BrowserHistory("google.com");
bh.visit("facebook.com");
bh.visit("youtube.com");
console.log(bh.back(1));
console.log(bh.back(1));
console.log(bh.forward(1));
bh.visit("linkedin.com");
console.log(bh.forward(2));
console.log(bh.back(2));
console.log(bh.back(7));
Output
facebook.com
google.com
facebook.com
linkedin.com
google.com
google.com
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
