Design Problems (LRU Cache, Twitter, Rate Limiter, etc.)

Design Problems (LRU Cache, Twitter, Rate Limiter, etc.)

Problem Scenario / Typical Use Case

Imagine you are building a high-traffic web service, such as a social media feed or an API gateway. You need to store frequently accessed data, limit request rates, or retrieve recent events efficiently.

Naively storing all data or scanning logs for each request leads to performance bottlenecks. Design Patterns for system problems provide scalable, maintainable, and efficient solutions.

Basic Idea

Design problems often involve:

1. LRU Cache: Keep the most recently used items in memory while evicting older ones to manage limited capacity.
2. Twitter / News Feed Systems: Retrieve recent posts efficiently while maintaining dynamic user connections.
3. Rate Limiters: Control request frequency to prevent abuse or overload.

Techniques commonly include:

• Combining hashmaps and linked lists for quick lookup and eviction.
• Priority queues or heaps for managing recent or top-k elements.
• Sliding windows or token buckets for request control.

Advantages

• Performance Optimization: Efficient memory and request handling.
• Scalability: Supports high-load systems with predictable behavior.
• Flexibility: Can adapt to multiple real-world scenarios like caching, feeds, or throttling.

Limitations / Considerations

• Complexity: Requires careful choice of data structures and concurrency control.
• Memory Usage: High capacity caches or queues can consume significant memory.
• Consistency: Distributed systems may need additional mechanisms for synchronization.

Practical Examples / Thought Triggers

1. LRU Cache: Quickly retrieve frequently accessed items while evicting the least used.
2. Twitter Feed: Maintain the most recent tweets for each user efficiently.
3. Rate Limiter: Limit API requests per user per time interval.

Thought Triggers:

• What data structures will give both O(1) access and O(1) update for my use case?
• How will my system behave under high load or concurrent access?
• Should I consider distributed versions for scalability and fault tolerance?

Implementation Example

Here’s a Python example for an LRU Cache using OrderedDict:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

# Example usage
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # Output: 1
cache.put(3, 3)      # Evicts key 2
print(cache.get(2))  # Output: -1

This demonstrates efficient caching with O(1) access and eviction.

Related Articles

• Top-K Elements / Heap Patterns: Useful for recent or trending item tracking.
• Sliding Window Patterns: Relevant for rate limiting or rolling statistics.
• Hashmaps & Frequency Counting: Core technique for fast lookup in design problems.