Algorithms & Data Structuresmedium
Design an LRU Cache
Design a data structure for a least-recently-used (LRU) cache with a fixed capacity. Implement get(key) and put(key, value), both in O(1) average time. When the cache is full, put evicts the least recently used entry.
Be ready to discuss thread safety, and what changes for an LFU variant.