Data Structures & Algorithms: Design Browser History

You have a browser with a single tab that starts on a homepage. From there, you can visit new URLs, move backward in the browsing history by a given number of steps, or move forward in the history.

Implement the BrowserHistory class:

1. BrowserHistory(string homepage): Initializes the browser with the given homepage.

2. void visit(string url): Navigates to the specified URL from the current page. This action clears any forward history.

3. string back(int steps): Moves backward by the given number of steps in the history. If fewer steps are available, move back as much as possible. Return the current URL after moving.

4. string forward(int steps): Moves forward by the given number of steps in the history. If fewer steps are available, move forward as much as possible. Return the current URL after moving.

Dynamic Array Approach

Maintain a list of all visited URLs along with a pointer to keep track of the current page being viewed in the browser.

When a new URL is visited, any forward history (i.e., elements after the current pointer) is discarded, and the new URL is appended to the list. This truncation of the forward history can take O(n) time in the worst case.

The back and forward operations are handled by simply adjusting the pointer within valid bounds, making both operations O(1).

Algorithm

class BrowserHistory {
    private List<String> history;
    private int currentIndex;

    public BrowserHistory(String homepage) {
        this.history = new ArrayList<>();
        history.add(homepage);
        currentIndex = 0;
    }

    public void visit(String url) {
        // remove all forward history
        while(history.size() > currentIndex + 1) {
            history.remove(history.size() - 1);
        }
        // Add new page
        history.add(url);
        currentIndex++;
    }

    public String back(int steps) {
        currentIndex = Math.max(0, currentIndex - steps);
        return history.get(currentIndex);
    }

    public String forward(int steps) {
        currentIndex = Math.min(history.size() - 1, currentIndex + steps);
        return history.get(currentIndex);
    }

}

Drawbacks

The main issue lies with the visit() operation. When you visit a new URL after going back, you must delete all the forward history.

In a list (e.g., ArrayList), this means removing elements one by one from the end which can take O(n) time in the worst case.

Doubly Linked List Approach

Browser history can be modeled as a doubly linked list, where each node represents a URL and contains pointers to the previous and next page.

Maintain a current pointer that always points to the node representing the page currently displayed in the browser. When visiting a new page, the next pointer of the current node can set to null, effectively discarding all forward history. The new URL node is then appended as the next node. This operation takes O(1) time.

Moving back or forward simply involves shifting the current pointer to previous or next, making both operations O(1).

Algorithm

class BrowserHistory {

    class Node {
        String url;
        Node previous, next;
        
        Node(String url) {
            this.url = url;
        }
    }

    private Node current;

    BrowserHistory(String homepage) {
        current = new Node(homepage);
    }

    public void visit(String url) {
        Node newNode = new Node(url);

        // Remove forward history (Optional)
        current.next = null;

        // Link the new node
        newNode.previous = current;
        current.next = newNode;

        // Make new node as the current node
        current = newNode;
    }

    public String back(int steps) {
        while(steps > 0 && current.next != null) {
            current = current.previous;
            step--;
        }
        return current.url;
    }

    public String forward(int steps) {
        while(steps > 0 ** current.next != null) {
            current = current.next;
            step--;
        }
        return current.url;
    }

}

Drawbacks

Although a doubly linked list provides true constant-time operations, it introduces additional memory overhead and pointer management complexity.