LRU Cache

Problem

Implement an LRU cache with O(1) get/put. NVIDIA often opens with this, then pivots into systems and multithreading follow-ups.

Example

capacity 2: put(1,1),put(2,2),get(1)->1,put(3,3) evicts 2

Constraints

• Up to 2 × 10^5 calls

Follow-up

Make it thread-safe; then 'how would CUDA streams change your design for a GPU-side cache?'