Structural• Patterns: Proxy

Cache (LRU / LFU)

Medium

Problem Summary

Design a thread-safe in-memory cache supporting eviction policies like Least Recently Used (LRU) or Least Frequently Used (LFU).

Functional Scope

Constant time complexity O(1) for get and put operations.
Clean eviction trigger once the cache reaches max capacity limit.
Full thread-safety under concurrent reads and writes.

Entity-Relationship (ER) Schema

LRUCache [1] <---> [*] Node
LRUCache [1] <---> [1] DoublyLinkedList

Design Approach

Combine a HashMap (for O(1) lookups) with a custom Doubly Linked List (for O(1) updates/removals). Protect operations using locks or synchronization blocks.

Core Classes & Models

Cache (Interface)LRUCache (LinkedListNode, DoublyLinkedList, Map)Node (Key, Value, Prev, Next)

Code Blueprint

public class LRUCache {
    private Map<Integer, Node> map = new ConcurrentHashMap<>();
    public synchronized int get(int key) { return -1; }
}