Which data structure is most efficient for implementing a cache with LRU (Least Recently Used) eviction policy?
- Array
- Linked List
- Hash Map + Doubly Linked List
- Stack
Answer: Hash Map + Doubly Linked List
LRU cache requires O(1) access and O(1) reorder on access. Hash map provides O(1) key lookup; doubly linked list maintains usage order with O(1) move-to-front. Combined, they achieve O(1) get/put operations. Classic system design question for SSC JE and banking IT exams.