LRU / LFU Cache

class Node:
    """Doubly linked list node holding a cache entry.
    Stores key (needed for hash map deletion on eviction) and value."""
    __slots__ = ('key', 'val', 'prev', 'next')  # Memory optimization

    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    """Least Recently Used cache with O(1) get and put.
    
    Data structure: HashMap + Doubly Linked List
    - HashMap: key → Node (for O(1) lookup)
    - DLL: ordered by recency (head = most recent, tail = least recent)
    - Sentinel head/tail eliminate null-check edge cases
    """

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}  # key → Node

        # Sentinel (dummy) head and tail nodes
        # Real data lives between these two sentinels
        self.head = Node()  # Dummy head — most recent end
        self.tail = Node()  # Dummy tail — least recent end
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        """Unlink a node from wherever it is in the list. O(1).
        Works for any position — no special cases needed thanks to sentinels."""
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node):
        """Insert node right after the dummy head (most recent position). O(1)."""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        """Retrieve value by key. Moves accessed item to front (most recent).
        Returns -1 if key not found."""
        if key not in self.cache:
            return -1
        node = self.cache[key]
        # This key was just accessed — make it the most recently used
        self._remove(node)
        self._add_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        """Insert or update a key-value pair.
        If cache is at capacity, evicts the least recently used item."""
        if key in self.cache:
            # Key exists — update value and move to front
            self._remove(self.cache[key])

        # Create new node (or replacement node if key existed)
        node = Node(key, value)
        self.cache[key] = node
        self._add_to_front(node)

        # Check capacity — evict LRU if over limit
        if len(self.cache) > self.cap:
            lru = self.tail.prev  # The node just before dummy tail = least recent
            self._remove(lru)
            del self.cache[lru.key]  # This is why nodes store the key!


# Usage — matches LeetCode 146 exactly
cache = LRUCache(2)
cache.put(1, 1)        # cache: {1=1}
cache.put(2, 2)        # cache: {1=1, 2=2}
print(cache.get(1))    # 1 — moves key 1 to front
cache.put(3, 3)        # evicts key 2 (LRU), cache: {1=1, 3=3}
print(cache.get(2))    # -1 (evicted)
cache.put(4, 4)        # evicts key 1 (LRU, since 3 was accessed more recently via put)
print(cache.get(1))    # -1 (evicted)
print(cache.get(3))    # 3 (still in cache)
print(cache.get(4))    # 4 (still in cache)

from collections import OrderedDict

class LRUCacheSimple(OrderedDict):
    """LRU Cache using Python's OrderedDict.
    
    OrderedDict maintains insertion order AND supports move_to_end().
    This is a legitimate 10-line implementation. Some interviewers
    accept it; others want the from-scratch version. Know both.
    
    In production, this is actually what you'd use — no need to
    reinvent doubly linked lists when the stdlib has you covered.
    """

    def __init__(self, capacity: int):
        super().__init__()
        self.cap = capacity

    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key)  # Mark as most recently used
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.cap:
            self.popitem(last=False)  # Remove oldest (leftmost) item

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.cache = new Map();

    // Sentinel nodes — the dummy trick
    this.head = { key: null, val: null, prev: null, next: null };
    this.tail = { key: null, val: null, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _addToFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;
    const node = this.cache.get(key);
    this._remove(node);
    this._addToFront(node);
    return node.val;
  }

  put(key, value) {
    if (this.cache.has(key)) this._remove(this.cache.get(key));

    const node = { key, val: value, prev: null, next: null };
    this.cache.set(key, node);
    this._addToFront(node);

    if (this.cache.size > this.cap) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.cache.delete(lru.key);
    }
  }
}

// Note: JavaScript's Map preserves insertion order, so you could
// also implement LRU by deleting and re-inserting on access.
// But the explicit DLL approach matches what interviewers expect.

from collections import defaultdict, OrderedDict

class LFUCache:
    """Least Frequently Used cache with O(1) get and put (LC 460).
    
    Three data structures working together:
    1. key_to_val: key → value (for O(1) value lookup)
    2. key_to_freq: key → frequency (for O(1) frequency lookup)
    3. freq_to_keys: frequency → OrderedDict of keys (for O(1) LRU within each frequency)
    
    Plus min_freq to track which frequency bucket to evict from.
    """

    def __init__(self, capacity: int):
        self.cap = capacity
        self.key_to_val = {}
        self.key_to_freq = {}
        self.freq_to_keys = defaultdict(OrderedDict)  # freq → {key: None, ...}
        self.min_freq = 0

    def _update_freq(self, key):
        """Increment a key's frequency and move it to the right bucket."""
        freq = self.key_to_freq[key]
        self.key_to_freq[key] = freq + 1

        # Remove from current frequency bucket
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:
                self.min_freq += 1  # This bucket is empty — min moves up

        # Add to new frequency bucket (at the end = most recent)
        self.freq_to_keys[freq + 1][key] = None

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

    def put(self, key: int, value: int) -> None:
        if self.cap <= 0:
            return

        if key in self.key_to_val:
            self.key_to_val[key] = value
            self._update_freq(key)
            return

        # Evict if at capacity
        if len(self.key_to_val) >= self.cap:
            # Remove the LRU item from the min-frequency bucket
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]

        # Insert new item with frequency 1
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.min_freq = 1  # New item always has frequency 1

import time

class TTLLRUCache:
    """LRU Cache with Time-To-Live expiration.
    
    Expiration is handled lazily: expired entries are only removed
    when accessed. Simple and sufficient for most use cases.
    """
    def __init__(self, capacity: int, default_ttl: float = 60.0):
        self.cap = capacity
        self.default_ttl = default_ttl
        self.cache = {}
        self.head = {'key': None, 'val': None, 'expires': 0, 'prev': None, 'next': None}
        self.tail = {'key': None, 'val': None, 'expires': 0, 'prev': None, 'next': None}
        self.head['next'] = self.tail
        self.tail['prev'] = self.head
        self.hits = 0
        self.misses = 0

    def _remove(self, node):
        node['prev']['next'] = node['next']
        node['next']['prev'] = node['prev']

    def _add_to_front(self, node):
        node['next'] = self.head['next']
        node['prev'] = self.head
        self.head['next']['prev'] = node
        self.head['next'] = node

    def get(self, key):
        if key not in self.cache:
            self.misses += 1
            return None
        node = self.cache[key]
        if time.time() > node['expires']:  # Lazy expiration
            self._remove(node)
            del self.cache[key]
            self.misses += 1
            return None
        self._remove(node)
        self._add_to_front(node)
        self.hits += 1
        return node['val']

    def put(self, key, value, ttl=None):
        if ttl is None: ttl = self.default_ttl
        if key in self.cache: self._remove(self.cache[key])
        node = {'key': key, 'val': value, 'expires': time.time() + ttl,
                'prev': None, 'next': None}
        self.cache[key] = node
        self._add_to_front(node)
        while len(self.cache) > self.cap:
            lru = self.tail['prev']
            self._remove(lru)
            del self.cache[lru['key']]

    @property
    def hit_rate(self):
        total = self.hits + self.misses
        return self.hits / total if total > 0 else 0.0


api_cache = TTLLRUCache(capacity=100, default_ttl=30.0)
api_cache.put("user:123", {"name": "Alice", "role": "admin"})
api_cache.put("product:456", {"name": "Widget", "price": 29.99}, ttl=300)
print(api_cache.get("user:123"))  # Cache hit
print(f"Hit rate: {api_cache.hit_rate:.1%}")

from functools import lru_cache
import time

# Without caching: exponential time O(2^n)
def fib_slow(n):
    if n < 2: return n
    return fib_slow(n - 1) + fib_slow(n - 2)

# With caching: O(n) time, O(n) space
@lru_cache(maxsize=128)  # Cache up to 128 unique inputs
def fib_fast(n):
    if n < 2: return n
    return fib_fast(n - 1) + fib_fast(n - 2)

start = time.time()
print(fib_fast(100))  # 354224848179261915075 — instant
print(f"Time: {time.time() - start:.6f}s")

# Check cache statistics
print(fib_fast.cache_info())
# CacheInfo(hits=98, misses=101, maxsize=128, currsize=101)
# 98 cache hits = 98 recursive calls skipped!

# Real-world: memoize expensive database queries
@lru_cache(maxsize=1000)
def get_user_permissions(user_id):
    """Cache user permissions to avoid repeated DB queries.
    First call: hits the database. Subsequent calls: instant."""
    # Imagine this queries a database (100ms round trip)
    return {"user_id": user_id, "roles": ["admin", "editor"]}

import time

class DNSCache:
    """Simplified DNS resolver cache with LRU eviction and TTL.
    
    Real DNS caches (in your OS, browser, and ISP) work similarly:
    - Cache DNS responses with their TTL (time-to-live)
    - Evict least recently used entries when full
    - A cache hit saves 10-100ms per lookup
    
    Typical sizes: browser cache ~1000 entries, OS cache ~10000
    """
    def __init__(self, capacity=1000):
        self.cache = {}  # domain → (ip, expiry, prev, next)
        self.cap = capacity
        self.hits = 0
        self.misses = 0
        # Using OrderedDict for simplicity here
        from collections import OrderedDict
        self.lru = OrderedDict()

    def resolve(self, domain):
        """Resolve a domain name to an IP address."""
        now = time.time()

        if domain in self.lru:
            ip, expiry = self.lru[domain]
            if now < expiry:
                self.lru.move_to_end(domain)
                self.hits += 1
                return ip  # Cache hit! Saved ~50ms
            else:
                del self.lru[domain]  # Expired

        # Cache miss — do actual DNS lookup (simulated)
        self.misses += 1
        ip, ttl = self._dns_lookup(domain)

        self.lru[domain] = (ip, now + ttl)
        self.lru.move_to_end(domain)

        # Evict if over capacity
        while len(self.lru) > self.cap:
            self.lru.popitem(last=False)

        return ip

    def _dns_lookup(self, domain):
        """Simulate a real DNS lookup (would take 10-100ms)."""
        # Returns (ip_address, ttl_seconds)
        return (f"93.184.216.{hash(domain) % 256}", 300)

    @property
    def hit_rate(self):
        total = self.hits + self.misses
        return self.hits / total if total else 0


dns = DNSCache(capacity=100)
# First visit — cache miss
dns.resolve("google.com")    # Miss: ~50ms lookup
# Second visit — cache hit  
dns.resolve("google.com")    # Hit: <0.001ms (instant)
print(f"DNS cache hit rate: {dns.hit_rate:.0%}")  # 50%

# Redis LRU configuration (redis.conf):
# maxmemory 256mb
# maxmemory-policy allkeys-lru
#
# Policies available:
#   allkeys-lru    → LRU across ALL keys (most common)
#   volatile-lru   → LRU only on keys with TTL set
#   allkeys-lfu    → LFU across all keys (Redis 4.0+)
#   allkeys-random → Random eviction (simple, sometimes sufficient)
#   noeviction     → Return error when memory is full

import redis

# Connect to Redis configured as LRU cache
r = redis.Redis(host='localhost', port=6379)

# Cache an API response with 5-minute TTL
r.setex("api:user:123", 300, '{"name": "Alice", "role": "admin"}')

# Read from cache — O(1)
cached = r.get("api:user:123")
if cached:
    print(f"Cache hit: {cached.decode()}")
else:
    print("Cache miss — fetch from database")
    # ... fetch from DB, then cache the result

# Check memory usage
info = r.info("memory")
print(f"Used memory: {info['used_memory_human']}")
print(f"Evicted keys: {info.get('evicted_keys', 0)}")