Design Problems

🎯 Design Problems: Hit Counter & Browser History

The Story of Tracking and Memory

Imagine you have a magic notebook. Every time something cool happens, you write it down. But here’s the twist—you only care about what happened in the last 5 minutes!

That’s exactly what a Hit Counter does. And your Browser History? It’s like remembering which pages of a book you read, so you can flip back and forth!

Let’s dive into two super fun design problems that teach you how computers remember and organize things.

🔢 Design Hit Counter

What Is a Hit Counter?

Think of a Hit Counter like a clicker at a museum entrance:

• Every time someone walks in → CLICK!
• The guard asks: “How many people came in the last 5 minutes?”

Your job is to build that clicker—but smarter!

The Problem

Design a system that:

1. Records a hit when something happens (like visiting a website)
2. Tells you the count of hits in the past 300 seconds (5 minutes)

Real-Life Analogy 🎪

Imagine you’re counting cars passing your house:

• At 1:00 PM → 3 cars pass
• At 1:02 PM → 5 cars pass
• At 1:06 PM → 2 cars pass
• Someone asks at 1:06 PM: “How many cars in the last 5 minutes?”

You look at your notes and add up: 3 + 5 + 2 = 10 cars!

How We Solve It

We use a queue (like a line at a store):

from collections import deque

class HitCounter:
    def __init__(self):
        # Queue stores (timestamp, count)
        self.hits = deque()

    def hit(self, timestamp):
        # Record this hit
        self.hits.append(timestamp)

    def getHits(self, timestamp):
        # Remove old hits (older than 5 min)
        while self.hits and \
              self.hits[0] <= timestamp - 300:
            self.hits.popleft()
        return len(self.hits)

Breaking It Down 🧩

Why a Queue? 🤔

A queue is perfect because:

• First In, First Out (FIFO)
• Old hits leave from the front
• New hits enter from the back
• Like people exiting a movie theater!

graph TD
    A["New Hit Arrives"] --> B["Add to Back of Queue"]
    B --> C{Check Old Hits}
    C -->|Too Old?| D["Remove from Front"]
    C -->|Still Valid| E["Keep in Queue"]
    D --> F["Count Remaining"]
    E --> F

Optimized Version 🚀

If many hits happen at the same second:

class HitCounter:
    def __init__(self):
        self.times = [0] * 300
        self.hits = [0] * 300

    def hit(self, timestamp):
        idx = timestamp % 300
        if self.times[idx] != timestamp:
            self.times[idx] = timestamp
            self.hits[idx] = 1
        else:
            self.hits[idx] += 1

    def getHits(self, timestamp):
        total = 0
        for i in range(300):
            if timestamp - self.times[i] < 300:
                total += self.hits[i]
        return total

Key Insight 💡

We use an array of 300 buckets:

• Each bucket = 1 second
• Old data gets overwritten automatically!
• Space: O(300) = O(1) constant!

🌐 Design Browser History

What Is Browser History?

When you browse the internet:

• You visit Page A → Page B → Page C
• Press Back → Go to Page B
• Press Forward → Go to Page C
• Visit new Page D → Forward history is gone!

It’s like reading a book with bookmarks, but if you jump to a new chapter, you lose all bookmarks ahead!

Real-Life Analogy 📚

Imagine walking through rooms:

• Room A → Room B → Room C (you’re in C)
• Walk back to B (now in B)
• Walk forward to C (back in C)
• Discover new Room D from B → Room C path disappears!

The Problem

Design a class with:

1. visit(url) → Go to a new page
2. back(steps) → Go back, return current URL
3. forward(steps) → Go forward, return current URL

The Solution 🎯

We use two stacks or a list with pointer:

class BrowserHistory:
    def __init__(self, homepage):
        self.history = [homepage]
        self.current = 0

    def visit(self, url):
        # Clear forward history
        self.history = self.history[:self.current+1]
        self.history.append(url)
        self.current += 1

    def back(self, steps):
        # Can't go before index 0
        self.current = max(0, self.current - steps)
        return self.history[self.current]

    def forward(self, steps):
        # Can't go past last index
        self.current = min(
            len(self.history) - 1,
            self.current + steps
        )
        return self.history[self.current]

Visual Journey 🗺️

graph TD
    A["Start: [Home]<br>current=0"] --> B["visit#40;'A'#41;<br>[Home, A]<br>current=1"]
    B --> C["visit#40;'B'#41;<br>[Home, A, B]<br>current=2"]
    C --> D["back#40;1#41;<br>current=1<br>Return: 'A'"]
    D --> E["visit#40;'C'#41;<br>[Home, A, C]<br>current=2<br>B is gone!"]

Step-by-Step Example 📝

browser = BrowserHistory("google.com")
# history = ["google.com"], current = 0

browser.visit("facebook.com")
# history = ["google.com", "facebook.com"]
# current = 1

browser.visit("youtube.com")
# history = ["google.com", "facebook.com",
#            "youtube.com"]
# current = 2

browser.back(1)  # Returns "facebook.com"
# current = 1

browser.back(1)  # Returns "google.com"
# current = 0

browser.forward(1)  # Returns "facebook.com"
# current = 1

browser.visit("linkedin.com")
# history = ["google.com", "facebook.com",
#            "linkedin.com"]
# current = 2
# NOTE: youtube.com is GONE!

Why This Design? 🤷

The Magic of Truncation ✂️

When you visit a new page after going back:

1. Everything after current position is deleted
2. New URL is added
3. Pointer moves to new URL

This mimics real browser behavior perfectly!

🎭 Comparing Both Designs

🌟 Why These Problems Matter

These aren’t just interview questions—they’re real-world skills:

1. Hit Counter → Analytics dashboards, rate limiters
2. Browser History → Any undo/redo system!

Think about it:

• Ctrl+Z in your text editor? Browser History logic!
• Website showing “1000 visitors in last hour”? Hit Counter!

🎯 Key Takeaways

Hit Counter

• ✅ Use queue for time-based data
• ✅ Remove expired entries efficiently
• ✅ Consider bucket optimization for high traffic

Browser History

• ✅ List + pointer = simple and powerful
• ✅ Truncate on new visit (clear forward history)
• ✅ Cap movements at boundaries

🚀 You Did It!

You just learned two fundamental design patterns:

1. Time-window tracking (Hit Counter)
2. State navigation with branching (Browser History)

These patterns appear everywhere in software—from streaming apps to code editors. Now you know the magic behind them!

Keep building, keep learning! 🎉