Design Browser History | DSA & Design With Lucifer

1. Classic DSA and Design based question , this question is testing your understanding of how you use a appropriate data structure and use it to solve real world problems. I will be primarily coding in java :) (Favoritism)

2. So the question is we need to design a browser history with visit , backward and forward methods. Lets understand in detail :-

   1. How do we generally start with our study sessions ?
      We we decide a topic , then search videos related to the topic on youtube.com , then probably if we don't understand we search for articles on geeksforgeeks.com , then we visit Leetcode.com to solve the problem.

      Now , suddenly you think to rewatch the video again , so you move to youtube.com , then moved again to leetcode.com

      if we carefully observe , for such design problems , we need a data structure that is flexible , and we need something to track , user's flow.

      So we can choose data structure - ArrayList or Deque and even a doubly linkedlist is fine (think upon this) and can have two pointers int curr (to track current position) and int last (to track last site visited by user).

   2. Lets start structuring the approach , we will design the class similar to leetcode question.

      class Browserhistory {
      public Browserhistory(String homepage) {
      //other methods
      }

      }

3. Let's start codingg

   class BrowserHistory {
       ArrayList <String> history = new ArrayList<>();
       int curr = 0;  // two pointers curr and last
       int last = 0;
   
       public BrowserHistory(String homepage) {
           history.add(homepage); //add the start page to the arraylist 
       }
       
       public void visit(String url) {
           curr++; //when user moves from homepage to site 1 , inc curr value 
           if(curr<history.size()) history.set(curr,url); // this checks if the site already exist , we override it
           else history.add(url); //else we will add the site to the list 
           last = curr; //set last = curr 
       }
       
       public String back(int steps) {
           curr = Math.max(0,curr-steps); //  it clamp the pointer so it never goes out of valid range.
           return history.get(curr); 
           
       }
       
       public String forward(int steps) {
           curr = Math.min(last, curr + steps);
           return history.get(curr);
           
       }
   }
   

Second Approach - Using Deques

class BrowserHistory {                                        // backHistory  → stores pages you came FROM (so you can go back)
// forwardHistory → stores pages you left (so you can go forward)
// Think: backHistory = ← stack,  forwardHistory = → stack
Deque<String> backHistory    = new ArrayDeque<>();
Deque<String> forwardHistory = new ArrayDeque<>();

// current = the page you are ON right now
String current;

// Constructor — called once when browser starts
// Sets the homepage as the first current page
// No back/forward history yet — fresh browser
public BrowserHistory(String homepage) {
    current = homepage;
}

public void visit(String url) {

    // Before leaving current page, save it to back history
    // so that back() can return to it later
    // e.g. current="youtube" → backHistory: [youtube]
    backHistory.push(current);

    // Visiting a NEW page always wipes forward history
    // Just like a real browser — you can't go "forward"
    // to pages you haven't visited yet in this path
    // e.g. was on google→youtube→github, went back to youtube,
    //      now visit twitter → github is gone forever
    forwardHistory.clear();

    // Now actually land on the new page
    current = url;
}

public String back(int steps) {

    // steps-- means: use current value of steps, THEN decrement
    // so if steps=3, loop runs when steps=3,2,1 (3 times total)
    //
    // !backHistory.isEmpty() = safety check
    // stops early if we run out of back history
    // e.g. back(100) on a 3-page history → just goes to page 0
    while (steps-- > 0 && !backHistory.isEmpty()) {

        // Before going back, save current page to forward history
        // so forward() can return to it
        // e.g. current="github" → forwardHistory: [github]
        forwardHistory.push(current);

        // Pop the most recent page from back history
        // and make it the current page
        // e.g. backHistory was [youtube, google]
        //      current becomes "youtube"
        //      backHistory is now [google]
        current = backHistory.pop();
    }

    // Return wherever we landed after going back N steps
    return current;
}

public String forward(int steps) {

    // Same pattern as back() but in reverse direction
    // steps-- counts down, stops if forwardHistory runs out
    while (steps-- > 0 && !forwardHistory.isEmpty()) {

        // Before going forward, save current page to back history
        // so back() can return to it again
        // e.g. current="youtube" → backHistory: [youtube, google]
        backHistory.push(current);

        // Pop the most recent page from forward history
        // and make it the current page
        // e.g. forwardHistory was [github, twitter]
        //      current becomes "github"
        //      forwardHistory is now [twitter]
        current = forwardHistory.pop();
    }

    // Return wherever we landed after going forward N steps
    return current;
}

}

Time and Space Complexities

For ArrayList approach:

Space: O(n)

For Deque approach:

Space: O(n)

That's it

THANKS FOR READING CUTIES <3