Google·Software Engineer·Onsite - Coding / Algorithms·Senior

SeniorPrefer not to say

Apr 2026

Summary

Google SWE coding round, got hit with an LFU cache design problem. Trickier than LRU in ways I didn't fully appreciate going in, mostly because of the tie-breaking rule when multiple keys share the lowest frequency.

Questions Asked (1)

Design and implement an LFU (Least Frequently Used) cache supporting get and put operations, both with O(1) average time complexity. When at capacity, evict the least frequently used key, breaking ties by recency.

Algorithms & Data StructuresSystem Design

Author's notes

I knew LRU cold so I figured LFU would just be a small extension.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and edge cases, then propose a design using a combination of a hash map and a doubly linked list of frequency nodes, each containing a doubly linked list of keys with that frequency. Explain how get and put operations maintain O(1) time by updating frequencies and moving nodes accordingly, and handle eviction by removing the least frequent and least recently used key.

Pro tip: Mention that you would use a dummy head and tail for the frequency list and for each key list to simplify edge cases, and discuss how to handle capacity zero or updates to existing keys.

1. Clarify requirements and constraints

Ask about cache capacity, expected operations, and whether keys/values are integers. Confirm that tie-breaking is by least recently used among least frequently used.

2. Outline data structures

Propose using a hash map for O(1) key lookup, a doubly linked list of frequency nodes (each with a set of keys), and a doubly linked list for keys within the same frequency to maintain recency order.

3. Detail get and put operations

Explain how get retrieves the value, increments the key's frequency, and moves it to the appropriate frequency node. For put, insert or update the key, and if at capacity, evict the least frequent and least recently used key.

4. Analyze complexity and edge cases

Argue that all operations are O(1) average time due to hash map and linked list manipulations. Discuss edge cases like capacity 0, updating existing keys, and eviction when multiple keys have the same frequency.

5. Implement and test

Write clean code with helper functions for node manipulation, and walk through a few test cases to verify correctness and O(1) behavior.

Key Points to Mention

Use a hash map to store key to (value, frequency node) mapping for O(1) access.
Maintain a doubly linked list of frequency nodes in increasing order of frequency.
Each frequency node contains a doubly linked list of keys with that frequency, ordered by recency (most recent at head or tail).
On get or put, update the key's frequency and move it to the next frequency node, creating a new node if necessary.
For eviction, remove the key from the least frequency node's least recently used position (tail or head depending on ordering).
Handle edge cases: capacity 0, updating existing key, and removing empty frequency nodes.

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