Design Problems

🎯 Design Problems: Hit Counter & Browser History

The Story of Your Digital Footprints

Imagine you have a magic notebook that remembers everything you do. Every time you visit a website, it writes it down. Every time someone knocks on your door, it counts. That’s exactly what we’re building today!

🔔 Design Hit Counter

What Is a Hit Counter?

Think of a Hit Counter like a tally sheet at a bakery door. Every time a customer walks in, you make a mark. At the end of the day, you can count how many customers came!

But here’s the twist: You only care about the last 5 minutes. Old marks fade away!

The Birthday Party Example 🎂

Imagine you’re counting how many kids ring your doorbell at a birthday party:

• 12:00 - Tommy rings (count = 1)
• 12:01 - Sarah rings (count = 2)
• 12:02 - Mike rings (count = 3)
• 12:06 - You check: “How many in last 5 min?”
  • Tommy’s ring at 12:00 is too old! Only Sarah and Mike count.
  • Answer: 2 kids

How Do We Build This?

We need two magic powers:

1. hit(timestamp) - Record when someone visits
2. getHits(timestamp) - Count visits in last 300 seconds

The Simple Approach: A Queue 📋

class HitCounter {
  constructor() {
    this.hits = []; // Our magic list
  }

  hit(timestamp) {
    this.hits.push(timestamp);
  }

  getHits(timestamp) {
    // Remove old hits (older than 5 min)
    const cutoff = timestamp - 300;
    while (this.hits.length &&
           this.hits[0] <= cutoff) {
      this.hits.shift();
    }
    return this.hits.length;
  }
}

The Smart Approach: Fixed Buckets 🪣

What if MANY people visit at the same second? Let’s be smarter!

Think of 300 buckets (one for each second in 5 minutes):

class HitCounter {
  constructor() {
    this.times = new Array(300).fill(0);
    this.hits = new Array(300).fill(0);
  }

  hit(timestamp) {
    const idx = timestamp % 300;
    if (this.times[idx] !== timestamp) {
      this.times[idx] = timestamp;
      this.hits[idx] = 1;
    } else {
      this.hits[idx]++;
    }
  }

  getHits(timestamp) {
    let total = 0;
    for (let i = 0; i < 300; i++) {
      if (timestamp - this.times[i] < 300) {
        total += this.hits[i];
      }
    }
    return total;
  }
}

Why Buckets Are Better?

🌐 Design Browser History

What Is Browser History?

You know when you click the ← Back and → Forward buttons in your browser? That’s what we’re building!

The Storybook Analogy 📚

Imagine reading a storybook:

• You’re on Page 5
• You go back to Page 3 (back button)
• Now you turn to a NEW page, Page 10
• What happens to pages 4 and 5? They disappear!

That’s exactly how browser history works!

graph TD
    A["Visit Google"] --> B["Visit Amazon"]
    B --> C["Visit Netflix"]
    C --> D["Press Back"]
    D --> E["Now at Amazon"]
    E --> F["Visit Twitter"]
    F --> G["Netflix is GONE!"]

Building Browser History

We need four magic powers:

1. visit(url) - Go to a new page
2. back(steps) - Go back in history
3. forward(steps) - Go forward in history

The Code Solution 🛠️

class BrowserHistory {
  constructor(homepage) {
    this.history = [homepage];
    this.current = 0;
  }

  visit(url) {
    // Delete everything after current
    this.history = this.history.slice(
      0, this.current + 1
    );
    this.history.push(url);
    this.current++;
  }

  back(steps) {
    // Don't go before beginning!
    this.current = Math.max(
      0, this.current - steps
    );
    return this.history[this.current];
  }

  forward(steps) {
    // Don't go past the end!
    this.current = Math.min(
      this.history.length - 1,
      this.current + steps
    );
    return this.history[this.current];
  }
}

Let’s Walk Through It! 🚶

const browser = new BrowserHistory("google.com");

browser.visit("facebook.com");
// history: [google, facebook], current: 1

browser.visit("youtube.com");
// history: [google, facebook, youtube], 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("twitter.com");
// youtube is ERASED!
// history: [google, facebook, twitter], current: 2

The Two-Stack Trick 🎭

Some clever folks use TWO stacks instead of one list:

class BrowserHistory {
  constructor(homepage) {
    this.backStack = [];
    this.forwardStack = [];
    this.currentPage = homepage;
  }

  visit(url) {
    this.backStack.push(this.currentPage);
    this.currentPage = url;
    this.forwardStack = []; // Clear forward!
  }

  back(steps) {
    while (steps > 0 &&
           this.backStack.length > 0) {
      this.forwardStack.push(this.currentPage);
      this.currentPage = this.backStack.pop();
      steps--;
    }
    return this.currentPage;
  }

  forward(steps) {
    while (steps > 0 &&
           this.forwardStack.length > 0) {
      this.backStack.push(this.currentPage);
      this.currentPage = this.forwardStack.pop();
      steps--;
    }
    return this.currentPage;
  }
}

🧠 Key Takeaways

Hit Counter Wisdom

• Problem: Count events in a sliding time window
• Simple: Use a queue, remove old items
• Smart: Use fixed buckets for O(1) space

Browser History Wisdom

• Problem: Navigate with back/forward
• Key insight: Visiting new page erases forward history
• Options: Single array or two stacks

💡 When Would You Use These?

🎉 You Did It!

You just learned two powerful design patterns:

1. Hit Counter - Counting events in a time window using queues or buckets
2. Browser History - Managing navigation with arrays or stacks

These patterns appear everywhere in real software. Now when you press “Back” in your browser, you know exactly what’s happening behind the scenes!

Remember: Great design is about choosing the right data structure for the job. A queue for events, an array for history. Simple tools, powerful results! 🚀