Amazon·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Apr 2026

Summary

Amazon SWE coding round, one question the whole time: implement an LRU cache with O(1) get and put. Classic problem but the pressure of getting the doubly linked list bookkeeping right under interview conditions is a different beast.

Questions Asked (1)

Implement an LRU cache supporting get(key) and put(key, value) operations, both in O(1) average time, with eviction of the least recently used entry when capacity is exceeded.

Algorithms & Data Structures

Author's notes

The concept clicked fast but I fumbled the implementation details.

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 the hash map provides direct access to nodes, while the linked list maintains the recency order, and walk through the get and put logic including eviction.

Pro tip: Mention that you would use a doubly linked list with sentinel head and tail nodes to simplify edge cases, and discuss thread-safety considerations if the cache might be accessed concurrently.

1. Clarify requirements

Confirm the expected operations, capacity constraints, and whether thread-safety is required. Ask about edge cases like capacity zero or duplicate keys.

2. Choose data structures

Select a hash map for O(1) key lookup and a doubly linked list to track usage order. Explain that the hash map stores key-node pairs, and the list maintains most-recently-used at one end and least-recently-used at the other.

3. Define node and cache structure

Describe the node with key, value, prev, and next pointers. Outline the cache with capacity, map, and head/tail sentinels to simplify insertion and removal.

4. Implement get and put

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

5. Analyze complexity and edge cases

State that both operations are O(1) average due to hash map and constant-time list updates. Discuss edge cases like capacity 1, updating existing key, and eviction when full.

Key Points to Mention

Hash map provides O(1) average time for key lookup.
Doubly linked list allows O(1) removal and insertion at both ends.
Sentinel nodes (head and tail) eliminate null checks and simplify code.
Eviction policy: remove least recently used node from tail.
Update recency on both get and put operations.
Thread-safety can be added with locks or concurrent data structures if needed.

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