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

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE interview with a classic LRU cache design question. Pretty standard for this level but the O(1) constraint is where things get interesting and where I almost fumbled it.

Questions Asked (1)

Design and implement an LRU cache with get and put operations, both running in O(1) time. Evict the least recently used entry when capacity is exceeded.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I knew the answer involved a hash map and a doubly linked list but explaining why it needs to be doubly linked took me a second longer than it should have.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a hash map combined with a doubly linked list to achieve O(1) operations. Walk through the design, implement the core methods, and discuss edge cases and trade-offs.

Pro tip: Mention that you would use a doubly linked list with sentinel head and tail nodes to simplify edge cases and avoid null checks. Also, discuss thread-safety considerations if the cache might be accessed concurrently.

1. Clarify Requirements

Ask about capacity constraints, thread-safety, and whether the cache should be generic. Confirm that both get and put must be O(1).

2. Propose Data Structures

Explain that a hash map provides O(1) access to nodes, and a doubly linked list maintains recency order. Together they enable O(1) get and put.

3. Design the Algorithm

Detail how get moves the accessed node to the front (most recently used), and put inserts or updates, evicting the tail (least recently used) when capacity is exceeded.

4. Implement Core Operations

Write clean code for get and put, using helper methods for adding to front and removing nodes. Handle edge cases like updating an existing key and evicting when full.

5. Analyze and Optimize

Discuss time and space complexity (O(1) time, O(capacity) space). Mention potential optimizations like using a custom node class or sentinel nodes to simplify code.

Key Points to Mention

Hash map for O(1) key lookup, mapping keys to nodes in the linked list.
Doubly linked list to maintain recency order, with most recently used at the head and least recently used at the tail.
Sentinel head and tail nodes to avoid null checks and simplify insertion/removal.
Eviction policy: when capacity is exceeded, remove the tail node (least recently used) and delete its key from the hash map.
Thread-safety considerations: use locks or concurrent data structures if the cache is shared across threads.
Time complexity: O(1) for both get and put; space complexity: O(capacity).

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