Verkada Inc.·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Verkada coding round, one problem the whole time. It was the LFU cache design question which I'd seen before but still fumbled parts of the implementation under pressure.

Questions Asked (1)

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

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I knew the problem going in and still got tripped up on the tie-breaking logic.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a combination of a hash map for key-value storage and a frequency-based doubly linked list structure to achieve O(1) operations. Each frequency bucket contains a doubly linked list of keys with that frequency, ordered by recency. On access, move the key to the next frequency bucket; on eviction, remove the least recently used key from the lowest frequency bucket.

Pro tip: Mention that you can optimize memory by using a single doubly linked list for each frequency and reusing nodes, and discuss how to handle edge cases like updating an existing key or capacity zero. Also, briefly compare with LRU to show understanding of trade-offs.

1. Clarify requirements and constraints

Confirm that get and put must be O(1), and that eviction is based on least frequency, then least recent. Ask about cache size, key/value types, and concurrency if relevant.

2. Design the data structures

Propose a hash map mapping keys to nodes, and a doubly linked list of frequency buckets. Each bucket contains a doubly linked list of keys with that frequency, ordered by recency.

3. Implement get and put operations

For get, retrieve the node, update its frequency, and move it to the appropriate bucket. For put, insert or update the key, and if at capacity, evict the least frequent, least recent key.

4. Handle edge cases and optimizations

Address updating existing keys, capacity zero, and maintaining min frequency pointer. Discuss potential memory optimizations and concurrency if needed.

5. Analyze complexity and trade-offs

Explain why operations are O(1) and discuss trade-offs compared to other eviction policies like LRU or FIFO.

Key Points to Mention

Use of hash map for O(1) key lookup
Frequency buckets as doubly linked lists to maintain recency order
Min frequency pointer to quickly find eviction candidate
Updating frequency on both get and put operations
Handling ties by least recently used within the same frequency
Time and space complexity analysis: O(1) time, O(capacity) space

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