Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Java Implementation
3.2.
Complexities
4.
Frequently Asked Questions
4.1.
Are there other ways of solving the Design Browser History problem?
4.2.
Can we implement the problem using multiple tabs?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Design Browser History

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Linked List

Introduction

Every day, we visit hundreds of websites or search using various search engines like Google. Sometimes we want to go back to the previous page again or go to the next page (if any). Have you ever wondered how it is done? Somewhere in our memory, there is a space allotted where all our browsing history is stored. When we press the back button on our browser, that memory is responsible for taking us to the correct website.

This article discusses the Design Browser History problem. The tasks to be performed by us are similar to a regular browser. These types of problems are easy to understand but trivial to implement. There are many ways to implement the problem but having a solution with the least time complexity is better.

Problem Statement

We have a browser with one tab. We start on a homepage; we can visit various pages using URLs. We can also go back and forth depending on the number of steps passed as arguments. Implement the BrowserHistory class as-

  • BrowserHistory(string homepage): initialize the object with the homepage of the browser.
  • void visit(string URL): Visit the URL from the current page and clear up all the forward history.
  • string back(int steps): Return the current URL after moving back in history at most steps.
  • string forward(int steps): Return the current URL after moving forward in history at most steps. 

Example and Explanation

INPUT

["BrowserHistory", "visit", "visit", "visit", "back", "forward", "visit","back",

[["MyHome.com"], ["google.com"], ["codingninjas.com"], ["youtube.com"],[1],[2], ["linkedin.com"],[6]]
 

OUTPUT

[null, null, null, null, "codingninjas.com", "youtube.com", null, "MyHome.com"]
 

  • In the given input sequence, we first initialize our homepage with the value MyHome.com.
  • Then, we visit the three sites- google.com, codingninjas.com, and youtube.com.  
  • We then move back by one step, then forward by two steps, and visit linkedin.com.
  • Finally, we move back by six steps. Even though we cannot traverse six steps back, we try to traverse as far as possible and return the last valid url.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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!

Previous article
Create a List in Reverse Order by Merging Two Sorted Linked List
Next article
Design Browser History (Doubly linked list)
Live masterclass