Structural• Patterns: Proxy, Strategy, Singleton

Cache (LRU / LFU)

Medium

Problem Summary

Design a high-performance in-memory Cache engine supporting O(1) reads and writes, configurable eviction strategies (LRU, LFU), thread safety, and transparent database proxy shielding.

Functional Scope

O(1) time complexity for get(key) and put(key, value).
Automatic eviction of the least recently used (LRU) or least frequently used (LFU) item upon reaching capacity.
Thread safety with high read throughput using ReadWriteLock or segmented striping.
Pluggable EvictionStrategy interface.
Optional TTL (time-to-live) expiration.

Entity-Relationship (ER) Schema

CacheProxy [1] --> [1] CacheEngine
CacheEngine [1] --> [1] EvictionStrategy
LRUCache [1] --> [1] DoublyLinkedList
LRUCache [1] --> [1] HashMap

Design Approach

Use a Doubly Linked List coupled with a Hash Table to achieve O(1) get and put operations. Protect concurrency using read/write locks so cache hits can execute concurrently.

Core Classes & Models

Cache (General interface: get, put, remove)LRUCache (Doubly linked list + Hash map implementation)Node (Key, value, prev, next references)EvictionStrategy (Pluggable eviction interface)CacheProxy (Transparent cache-aside database wrapper)

Code Blueprint

102 lines

/**
 * Low-Level Design: In-Memory Cache System
 * Design Patterns Applied:
 *  - Proxy Pattern: Cache proxy intercepting database queries with transparent read-through
 *  - Strategy Pattern: Pluggable eviction strategies (LRU, LFU, FIFO)
 *  - Singleton Pattern: Centralized cache manager
 */

import java.util.*;

// --- [DESIGN PATTERN: Strategy] Cache eviction strategy ---
interface EvictionStrategy<K> {
    void onKeyAccessed(K key);
    K evictKey();
}

class LRUEvictionStrategy<K> implements EvictionStrategy<K> {
    private final LinkedHashSet<K> accessOrder = new LinkedHashSet<>();

    @Override
    public void onKeyAccessed(K key) {
        accessOrder.remove(key);
        accessOrder.add(key);
    }

    @Override
    public K evictKey() {
        Iterator<K> it = accessOrder.iterator();
        if (it.hasNext()) {
            K oldest = it.next();
            it.remove();
            return oldest;
        }
        return null;
    }
}

// --- [DESIGN PATTERN: Proxy] Read-through database proxy ---
interface DataStore<K, V> {
    V get(K key);
}

class DatabaseStore implements DataStore<String, String> {
    @Override
    public String get(String key) {
        System.out.println("💾 [Database I/O] Costly DB lookup for key: " + key);
        return "Record_For_" + key;
    }
}

class CacheProxy implements DataStore<String, String> {
    private final DataStore<String, String> db;
    private final int capacity;
    private final Map<String, String> storage = new HashMap<>();
    private final EvictionStrategy<String> evictionStrategy;

    public CacheProxy(DataStore<String, String> db, int capacity, EvictionStrategy<String> evictionStrategy) {
        this.db = db;
        this.capacity = capacity;
        this.evictionStrategy = evictionStrategy;
    }

    @Override
    public synchronized String get(String key) {
        if (storage.containsKey(key)) {
            System.out.println("⚡ [Cache HIT] key: " + key);
            evictionStrategy.onKeyAccessed(key);
            return storage.get(key);
        }

        System.out.println("❌ [Cache MISS] key: " + key);
        String val = db.get(key);
        put(key, val);
        return val;
    }

    public synchronized void put(String key, String value) {
        if (storage.size() >= capacity && !storage.containsKey(key)) {
            String evicted = evictionStrategy.evictKey();
            if (evicted != null) {
                storage.remove(evicted);
                System.out.println("🗑️ [Eviction] Evicted least recently used key: " + evicted);
            }
        }
        storage.put(key, value);
        evictionStrategy.onKeyAccessed(key);
    }
}

public class Main {
    public static void main(String[] args) {
        DatabaseStore db = new DatabaseStore();
        CacheProxy cache = new CacheProxy(db, 2, new LRUEvictionStrategy<>());

        System.out.println("--- Starting Cache Simulation ---");
        cache.get("user:1"); // MISS
        cache.get("user:1"); // HIT
        cache.get("user:2"); // MISS
        cache.get("user:3"); // MISS -> causes eviction of user:1 or user:2
        cache.get("user:1"); // MISS (re-fetched from DB)
    }
}