LRU Cache Implementation - Oracle Coding Interview

Implement a fixed-capacity Least Recently Used (LRU) cache and discuss Java-specific design considerations.

You will build an LRU cache class that exposes the standard get(key) and put(key, value) operations. get should return the stored value or -1 if the key is absent and must mark an accessed entry as recently used. put must insert or update a key, mark it as recently used, and—when capacity is reached—evict the least recently used entry before inserting a new key. Keys and values are integers for the coding stage and capacity is a positive integer set at construction.

Interview flow: you typically start by describing a target API and invariants (O(1) access, correct LRU ordering), propose a data structure (hash table + doubly linked list), sketch node layout and operations, then implement get/put with careful pointer updates. After a correct implementation, expect follow-ups on complexity, corner cases (capacity 0, duplicate puts), and Java-specific variants.

Skill signals you should show: O(1) time reasoning, ability to maintain ordering with a doubly linked list, correct hash table usage for direct lookup, attention to edge cases and memory/cycle concerns. For Java follow-ups, be prepared to discuss collection choices (LinkedHashMap vs custom), thread-safety strategies (synchronization, ConcurrentHashMap, locks), GC and reference types, equals()/hashCode() implications, and how to add metrics or persistence without breaking core semantics.