Design Problems

Design Problems: Hit Counter & Browser History 🎯

The Story of Counting & Remembering

Imagine you have a magic notebook that helps you with two important jobs:

1. Counting visitors at a candy shop (like counting how many kids came in the last 5 minutes)
2. Remembering your path through a maze (so you can go back and forward)

These are exactly what Hit Counter and Browser History do in programming!

🍬 Part 1: Design Hit Counter

The Candy Shop Story

You own a candy shop. The shop owner asks you:

“How many kids visited in the last 5 minutes?”

Not “how many kids visited today” — just the last 5 minutes!

Why Is This Tricky?

Think about it like a moving window:

• At 3:00 PM, you count visits from 2:55-3:00
• At 3:01 PM, you count visits from 2:56-3:01
• Old visits “fall off” as time moves forward!

graph TD
    A["Time: 3:00 PM"] --> B["Window: 2:55-3:00"]
    C["Time: 3:01 PM"] --> D["Window: 2:56-3:01"]
    E["Old visits drop off!"]

The Bucket Trick 🪣

Imagine 300 small buckets (one for each second in 5 minutes):

• Each bucket remembers visits for that second
• When a new visit comes, find the right bucket
• To count total: add up all buckets!

Simple Example

// Think of it like 300 buckets
// for 5 minutes = 300 seconds
int[] hits = new int[300];
int[] times = new int[300];

What happens when someone visits at second 45?

• Find bucket 45 (using: 45 % 300 = 45)
• Check if it’s fresh (same timestamp)
• If fresh: add 1 to count
• If old: reset to 1

The Code (Like Following a Recipe)

class HitCounter {
    int[] hits;  // count per bucket
    int[] times; // when was bucket used

    public HitCounter() {
        hits = new int[300];
        times = new int[300];
    }

    public void hit(int timestamp) {
        int bucket = timestamp % 300;
        if (times[bucket] != timestamp) {
            // Old bucket! Clean it
            times[bucket] = timestamp;
            hits[bucket] = 1;
        } else {
            // Same second, add one more
            hits[bucket]++;
        }
    }

    public int getHits(int timestamp) {
        int total = 0;
        for (int i = 0; i < 300; i++) {
            // Only count if within 5 min
            if (timestamp - times[i] < 300) {
                total += hits[i];
            }
        }
        return total;
    }
}

Why 300 Buckets?

5 minutes = 300 seconds. We only care about the last 300 seconds, so:

• Bucket 0 = seconds 0, 300, 600, 900…
• Bucket 1 = seconds 1, 301, 601, 901…
• And so on!

This is called the modulo trick: timestamp % 300

Real Life Examples 🌟

🌐 Part 2: Design Browser History

The Maze Walker Story

You’re walking through a maze of rooms. You want to:

1. Visit new rooms (go forward)
2. Go back to previous rooms
3. Go forward again if you went back

But here’s the twist: If you visit a NEW room after going back, you forget all the rooms ahead!

The Two-Pointer Dance 💃

Think of it like a book with a bookmark:

• The book has many pages you visited
• Your bookmark shows where you are NOW
• Going back = moving bookmark left
• Going forward = moving bookmark right
• Visiting new page = tear out all pages after bookmark!

graph TD
    A["Pages: Google, Amazon, Facebook"] --> B["Bookmark at Facebook"]
    B --> C["Go Back 1"]
    C --> D["Bookmark at Amazon"]
    D --> E["Visit Netflix"]
    E --> F["Pages: Google, Amazon, Netflix"]
    F --> G["Facebook is GONE!"]

Simple Example

// Our history book
List<String> history = new ArrayList<>();
// Our bookmark position
int current = -1;

The Full Code

class BrowserHistory {
    List<String> history;
    int current;

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

    public void visit(String url) {
        // Tear out pages after bookmark
        while (history.size() > current + 1) {
            history.remove(history.size() - 1);
        }
        // Add new page
        history.add(url);
        current++;
    }

    public String back(int steps) {
        // Move bookmark left
        current = Math.max(0, current - steps);
        return history.get(current);
    }

    public String forward(int steps) {
        // Move bookmark right
        current = Math.min(
            history.size() - 1,
            current + steps
        );
        return history.get(current);
    }
}

Walking Through an Example

Start: homepage = "google.com"
History: [google.com]  Current: 0

visit("amazon.com")
History: [google.com, amazon.com]  Current: 1

visit("facebook.com")
History: [google.com, amazon.com, facebook.com]  Current: 2

back(1) → returns "amazon.com"
History: [google.com, amazon.com, facebook.com]  Current: 1

back(1) → returns "google.com"
History: [google.com, amazon.com, facebook.com]  Current: 0

forward(1) → returns "amazon.com"
History: [google.com, amazon.com, facebook.com]  Current: 1

visit("netflix.com")
History: [google.com, amazon.com, netflix.com]  Current: 2
// facebook.com is GONE forever!

Key Insight: Why Remove Forward Pages?

When you go back in a browser and visit a new page, you create a new path. The old forward pages no longer make sense!

It’s like in a maze:

• You went: Room A → Room B → Room C
• You went back to Room B
• You found a NEW door to Room D
• Now Room C doesn’t exist on your path anymore!

🎯 Comparing Both Designs

🧠 Key Takeaways

Hit Counter Remember:

1. Use buckets for time-based counting
2. Modulo operator reuses old buckets
3. Check timestamps to know if bucket is fresh
4. Sum only valid buckets within time window

Browser History Remember:

1. List stores pages in order
2. Pointer tracks current position
3. Back/Forward move pointer within bounds
4. New visit clears forward history

🚀 You’ve Got This!

These problems teach us something beautiful:

• Hit Counter: How to count things in a sliding window of time
• Browser History: How to manage a path with back/forward/new

Both are about managing state over time — a fundamental skill in programming!

Next time you click the back button in your browser, you’ll know exactly what’s happening behind the scenes! 🎉