Oracle·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Oracle SWE interview with a classic LRU cache design question. Pretty standard stuff for this kind of role but the O(1) constraint is where people either nail it or fall apart.

Questions Asked (1)

Design and implement an in-memory LRU cache that supports get and put operations, both running in O(1) time. The cache should evict the least recently used entry when it exceeds capacity.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The O(1) requirement is the whole puzzle here.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a hash map combined with a doubly linked list to achieve O(1) get and put. Walk through the design, implement the core operations, and discuss edge cases and trade-offs.

Pro tip: Mention that you would use a doubly linked list with sentinel head and tail nodes to simplify edge cases and avoid null checks, and discuss thread-safety considerations if the cache is to be used in a concurrent environment.

1. Clarify Requirements

Ask about capacity constraints, expected operations, thread-safety, and whether keys/values are generic. Confirm that O(1) time is required for both get and put.

2. Propose Data Structures

Explain that a hash map provides O(1) access to nodes, and a doubly linked list maintains recency order. The map stores key -> node, and the list orders nodes from most to least recently used.

3. Detail Operations

Describe get: if key exists, move node to front and return value; else return -1. Describe put: if key exists, update value and move to front; else create new node, add to front, and if capacity exceeded, remove tail node and delete its key from map.

4. Implement Core Logic

Write clean code for the LRU cache class, using helper methods for adding to front and removing nodes. Use sentinel nodes to simplify list operations.

5. Discuss Edge Cases and Trade-offs

Cover capacity 0 or 1, updating existing keys, and thread-safety. Mention that synchronization or concurrent data structures may be needed for multi-threaded use, and discuss alternative eviction policies.

Key Points to Mention

Hash map provides O(1) lookup, doubly linked list provides O(1) insertion/deletion and maintains recency order.
Sentinel head and tail nodes eliminate null checks and simplify edge cases.
Get operation must move accessed node to the front (most recently used).
Put operation must handle both existing and new keys, and evict the least recently used (tail) when capacity is exceeded.
Time complexity: O(1) for both get and put; space complexity: O(capacity).
Thread-safety considerations: use locks or ConcurrentHashMap with synchronized list operations for concurrent environments.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.