Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Amazon SWE interview with a classic LRU cache design question. The scope kept expanding as the conversation went on, which I wasn't fully ready for.

Questions Asked (1)

Design and implement a fixed-capacity cache with get and put operations running in O(1) average time, evicting the least recently used entry when full. Cover how recency gets updated, how duplicate keys are handled, what get returns on a miss, and walk through thread-safety and testing considerations.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

Started fine with the hashmap plus doubly linked list approach, moved the accessed node to the front on both get and put, returned -1 for missing keys.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (fixed capacity, O(1) get/put, LRU eviction, thread-safety expectations). Then describe the classic hash map + doubly linked list design, covering recency updates, duplicate keys, miss behavior, and concurrency. Finally, outline testing and trade-offs.

Pro tip: Mention that you would first ask about the expected read/write ratio and whether thread-safety is required, as this shows you think about real-world constraints before jumping into code.

1. Clarify requirements and constraints

Ask about capacity, expected operations, thread-safety needs, and whether keys/values have any special properties. Confirm that O(1) average time is required for both get and put.

2. Propose data structures

Use a hash map for O(1) key lookup and a doubly linked list to maintain recency order. The map stores key -> node, and the list has most recently used at head and least recently used at tail.

3. Detail operations

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

4. Address thread-safety

Discuss options: use a single lock (simple but may bottleneck), or use concurrent data structures with fine-grained locking (e.g., ConcurrentHashMap + synchronized list operations). Mention trade-offs between simplicity and scalability.

5. Outline testing and edge cases

Test basic get/put, eviction order, duplicate key updates, capacity 1, and concurrent access. Use unit tests with assertions and stress tests for thread-safety.

Key Points to Mention

Hash map provides O(1) average lookup; doubly linked list provides O(1) removal/insertion for recency updates.
On get hit, move the accessed node to the head of the list to mark it as most recently used.
On put with an existing key, update the value and move the node to the head; do not increase size.
On put with a new key when at capacity, evict the tail node (least recently used) and remove its entry from the map.
On get miss, return a sentinel value (e.g., null or -1) as specified; do not modify the cache.
Thread-safety can be achieved with a global lock or more granular locking; consider using ConcurrentHashMap and synchronized blocks for the list operations.

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