Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Amazon SWE coding round centered on LRU Cache, which sounds manageable until you realize they want the full doubly-linked-list plus hashmap implementation and will steer you away from language shortcuts. The interviewer was clearly testing whether you understood the data structure, not just whether you could produce working code.

Questions Asked (1)

Implement an LRU cache with O(1) get and put operations. On capacity overflow, evict the least recently used key. A get counts as a use.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to reach for OrderedDict and call it a day.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and constraints, then propose a hash map combined with a doubly linked list to achieve O(1) operations. Explain how get and put work, including updating the order and evicting the least recently used item when capacity is exceeded.

Pro tip: Mention that using a doubly linked list with sentinel head and tail nodes simplifies edge cases and avoids null checks, showing attention to code robustness. Also, discuss potential concurrency considerations if the cache might be accessed by multiple threads, demonstrating awareness of real-world scenarios.

1. Clarify requirements

Confirm the expected operations (get, put), capacity behavior, and any constraints like thread safety or key/value types. Ask if the cache should be thread-safe or if there are any performance requirements beyond O(1).

2. Choose data structures

Propose a hash map for O(1) key lookup and a doubly linked list to maintain usage order. Explain that the hash map stores key to node references, and the linked list orders nodes from most to least recently used.

3. Define operations

Describe get: if key exists, move its node to the front (most recently used) 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 the tail node (least recently used) and delete its key from the map.

4. Handle edge cases

Discuss edge cases such as capacity 0 or 1, updating an existing key, and eviction when the cache is full. Mention using sentinel nodes to simplify insertion and removal.

5. Analyze complexity and trade-offs

State that both get and put are O(1) time and O(capacity) space. Mention alternative implementations (e.g., using OrderedDict in Python) and trade-offs like memory overhead vs. simplicity.

Key Points to Mention

Hash map provides O(1) access to cache nodes.
Doubly linked list maintains recency order with O(1) insertion/removal.
Get operation must update recency (move to front).
Eviction removes the least recently used item (tail of list).
Sentinel nodes (dummy head and tail) simplify edge cases.
Time complexity: O(1) for both get and put; space complexity: O(capacity).

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