Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Google SWE interview with a classic caching problem. Nothing too exotic but the O(1) constraint is where people trip up if they haven't seen it before.

Questions Asked (1)

Design a fixed-capacity key-value cache that supports get and put operations, evicting the least recently used entry when full. Both operations must run in O(1) average time.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The get and put parts are easy enough to describe but the O(1) eviction is where you have to actually think.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (capacity, eviction policy, thread-safety) and then propose a design using a hash map and a doubly linked list to achieve O(1) operations. Explain how the hash map provides direct access to nodes, while the linked list maintains recency order, and walk through the get and put operations step by step.

Pro tip: Mention that you would use a doubly linked list with sentinel nodes to simplify edge cases, and discuss how to make the cache thread-safe (e.g., using locks or concurrent data structures) since Google often cares about concurrency.

1. Clarify Requirements

Ask about capacity, eviction policy (LRU), expected operation mix, and whether thread-safety is required. Confirm that both get and put must be O(1) average time.

2. Propose Data Structures

Suggest using a hash map (for O(1) key lookup) and a doubly linked list (to track recency order). Explain that the hash map stores key -> node references, and the linked list stores nodes with key-value pairs.

3. Detail Operations

For get: if key exists, move the node to the front (most recently used) and return value; else return -1. For put: if key exists, update value and move to front; else create new node, add to front, and if capacity exceeded, remove the least recently used node (tail) and delete its key from the hash map.

4. Handle Edge Cases and Concurrency

Discuss edge cases like capacity 0 or 1, and how to handle null values. If thread-safety is needed, mention using a mutex or a concurrent hash map with atomic operations, or a lock-free approach.

5. Analyze Complexity and Trade-offs

Confirm that both operations are O(1) average time due to hash map and linked list operations. Discuss trade-offs: memory overhead of pointers, potential for hash collisions, and alternative designs (e.g., using an array with timestamps but that would be O(n)).

Key Points to Mention

Hash map provides O(1) average lookup, but worst-case O(n) due to collisions; mention that in practice it's O(1).
Doubly linked list allows O(1) removal and insertion when we have a reference to the node.
Use sentinel head and tail nodes to avoid null checks and simplify code.
When evicting, remove the tail node (least recently used) and delete its key from the hash map.
Thread-safety: use a lock (e.g., synchronized in Java) or a concurrent data structure; discuss read-write locks for better concurrency.
Consider memory constraints: each entry stores key, value, and two pointers; if memory is tight, discuss alternatives like using a circular buffer with timestamps (but that would not be O(1) for get).

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