Approach
-
To solve the problem, we will be using a doubly-linked list. We do so because, in a doubly-linked list, backward and forward movement can be easily implemented, and creating the linked list can be done in linear time.
- The implementation given in this article is done in Java. So, let’s start with our approach without any ado.
- Create a constructor for our linked list. Here, we have named our linked list Site. It has three attributes- prv(Site), next(Site), url(String).
- Initialize the nodes of Site with the incoming urls.
- Now come to the class BrowserHistory. Create a new doubly linked list. In our solution code, we named it curr.
- As per the problem statement, class BrowserHistory has four member functions. Their uses and implementation are as follows:
- BrowserHistory(string homepage): initialize the homepage with the incoming string value. This is our fixed homepage and will not be changed.
- void visit(String url): visit the given url. By visiting the url, we mean to create a new node; the url of this node will be the incoming url, that is, curr.next is the url of the new node. Link this node to the previous nodes.
- String back(int steps): travel back steps number of nodes. We try to traverse our linked list as long as the curr.prv value is not null and steps-- is not zero. We return the url of the destination node.
- String forward(int steps): travel forward steps number of nodes. We try to traverse our linked list as long as the curr.next value is not null and steps-- is not zero. We return the url of the destination node.
- To run the code, create a class BrowserImplement and create a main() method.
- Inside the main() method, create a new linked list object of the type BrowserHistory and call the functions as per your requirements.
Java Implementation
class Site {
public Site prv;
public Site next;
public final String url;
public Site(final String url) {
this.url = url;
}
}
class BrowserHistory {
private Site curr;
public BrowserHistory(String homepage) {
curr = new Site(homepage);
System.out.println("Homepage: " + homepage);
}
public void visit(String url) {
curr.next = new Site(url);
curr.next.prv = curr;
curr = curr.next;
System.out.println("Directing to: " + url);
}
public String back(int steps) {
System.out.println("\nCurrently at: " + curr.url);
System.out.println("Going Back " + steps + " step/s");
while (curr.prv != null && steps-- > 0)
curr = curr.prv;
return curr.url;
}
public String forward(int steps) {
System.out.println("\nCurrently at: " + curr.url);
System.out.println("Going Forward " + steps + " step/s");
while (curr.next != null && steps-- > 0)
curr = curr.next;
return curr.url;
}
}
public class BrowserImplement {
public static void main(String[] args) {
BrowserHistory bh = new BrowserHistory("MyHome.com");
bh.visit("google.com");
bh.visit("codingninjas.com");
bh.visit("youtube.com");
String back_step = bh.back(1);
System.out.println("Redirected to " + back_step);
String fwd_step = bh.forward(2);
System.out.println("Redirected to " + fwd_step);
System.out.println("");
bh.visit("linkedin.com");
back_step = bh.back(6);
System.out.println("Redirected to " + back_step);
}
}
OUTPUT
Homepage: MyHome.com
Directing to: google.com
Directing to: codingninjas.com
Directing to: youtube.com
Currently at: youtube.com
Going Back 1 step/s
Redirected to codingninjas.com
Currently at: codingninjas.com
Going Forward 2 step/s
Redirected to youtube.com
Directing to: linkedin.com
Currently at: linkedin.com
Going Back 6 step/s
Redirected to MyHome.com
Complexities
Time Complexity
In the given implementation, the back() and forward() functions have O(steps) complexity. Thus overall complexity is, T(n) = O(n); where n is the number of steps.
Space Complexity
In the given implementation, we create a doubly-linked list of size n to store all the urls. Thus, Space complexity = O(n); where n is the number of nodes.
Frequently Asked Questions
Are there other ways of solving the Design Browser History problem?
Yes, we can implement Design Browser History by using a singly-linked list or an array of strings. But these implementations are not feasible enough. In the case of a single-linked list, we can traverse only forward. So, to go back, we have to calculate the destination node first and then travel to it from the beginning. In the case of arrays, we might end up declaring either a small array or a big array.
Can we implement the problem using multiple tabs?
It is possible that some websites are opened in a new tab and some in the old tabs. For multiple tabs, we can create multiple linked lists to handle each tab.
Conclusion
To summarize the article, we discussed the Design Browser History problem thoroughly. We saw the problem statement, example, explanation, one of the approaches, and finally, the solution code. We also covered a few FAQs at the end.
Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Cheers!
117+ registered 