Salesforce·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026

Summary

Salesforce coding interview, got hit with the LFU cache design problem. Not the worst session I've had but definitely not a gimme either.

Questions Asked (1)

Design and implement an LFU (Least Frequently Used) cache class with get and put operations, both running in O(1) average time. On eviction, remove the least frequently used key, and break ties by removing the least recently used among those.

Algorithms & Data StructuresSystem Design

Author's notes

I knew LRU cold but LFU is a different beast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a combination of a hash map and a doubly linked list of frequency nodes, where each frequency node contains a doubly linked list of keys with that frequency. This allows O(1) access, update, and eviction by maintaining pointers to the least frequently used node and the least recently used key within it.

Pro tip: Emphasize that the design must handle both frequency updates and recency ordering within the same frequency, and discuss how to maintain O(1) by using sentinel nodes and careful pointer manipulation.

1. Clarify requirements and constraints

Confirm that both get and put must be O(1) average time, and that eviction removes the least frequently used key, breaking ties by least recently used. Ask about cache capacity and whether keys/values are integers or generic.

2. Design the data structures

Propose a hash map from key to a node containing value and frequency, and a doubly linked list of frequency nodes. Each frequency node has a doubly linked list of keys with that frequency, ordered by recency (most recent at head).

3. Implement get operation

If key exists, retrieve its node, increment its frequency, and move it to the appropriate frequency list. If the frequency node doesn't exist, create it and insert it in the correct position relative to the current frequency node.

4. Implement put operation

If key exists, update value and increment frequency (similar to get). If key is new, check capacity; if full, evict the least frequently used key (tail of the lowest frequency list). Then insert the new key with frequency 1.

5. Handle edge cases and optimize

Discuss handling capacity 0, updating frequency nodes when lists become empty, and using sentinel nodes to simplify pointer operations. Mention that all operations remain O(1) due to constant number of pointer updates.

Key Points to Mention

Use of a hash map for O(1) key lookup and a doubly linked list of frequency nodes for O(1) frequency updates.
Each frequency node contains a doubly linked list of keys to maintain recency order within the same frequency.
Eviction: remove the least frequently used key from the tail of the lowest frequency list; if multiple, the tail is the least recently used.
Frequency increment: move key from its current frequency list to the next higher frequency list, creating a new frequency node if needed.
Sentinel nodes (dummy head and tail) to simplify insertion and deletion in linked lists.
Time complexity: all operations are O(1) average because each step involves a constant number of pointer changes and hash map operations.

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