← Amazon Interview Insights

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

IntermediatePrefer not to say
Jun 2026

Summary

Amazon SWE coding round, one question the whole time: design an LFU cache from scratch. Not a warmup, not a follow-up. Just that.

Questions Asked (1)

Q1

Design an LFU (Least Frequently Used) cache that supports get and put operations in O(1) time, evicting the least frequently used entry when capacity is reached.

Algorithms & Data StructuresSystem Design
Author's notes

I knew LRU cold but LFU tripped me up at first because you need to track frequency AND recency within the same frequency bucket.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: O(1) get and put, and how to handle ties in frequency. Then propose a design using a hash map for key-to-node mapping and a doubly linked list of frequency buckets, each containing a doubly linked list of nodes with that frequency. Explain how get and put update frequencies and evict the least frequently used node in O(1).

Pro tip: Mention that you can optimize by using a min-frequency pointer to avoid scanning for the lowest frequency, and discuss tie-breaking (e.g., LRU among same frequency) to show attention to detail.

1. Clarify requirements and constraints

Confirm that both get and put must be O(1), and discuss how to handle frequency ties (e.g., evict least recently used among least frequently used).

2. Design core data structures

Use a hash map for O(1) key lookup, and a doubly linked list of frequency nodes, each containing a doubly linked list of cache entries with that frequency.

3. Implement get operation

If key exists, retrieve the node, increment its frequency, and move it to the appropriate frequency list; update min frequency if needed. Return the value.

4. Implement put operation

If key exists, update value and increment frequency. If new, insert with frequency 1; if capacity exceeded, evict the least frequently used node (and LRU among ties) from the min frequency list.

5. Analyze complexity and edge cases

Explain how each operation is O(1) due to constant-time list manipulations and hash map access. Discuss edge cases like capacity 0, updating existing keys, and frequency overflow.

Key Points to Mention

  • Use of two hash maps: one for key-to-node mapping, and optionally one for frequency-to-bucket mapping to quickly access frequency lists.
  • Doubly linked lists for O(1) removal and insertion, both for frequency buckets and for nodes within a bucket.
  • Maintain a min_freq variable to track the lowest frequency in O(1) for eviction.
  • Tie-breaking policy: typically evict the least recently used among the least frequently used, requiring an LRU order within each frequency bucket.
  • Handling of get and put updates: increment frequency and move node to the next frequency bucket, creating new buckets as needed.
  • Time complexity: O(1) for both get and put due to constant-time operations on hash maps and linked lists.

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