Walmart·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Coding round for a software engineer role, just the one question about LRU Cache. Short and to the point.

Questions Asked (1)

Implement an LRU Cache with get and put operations, both in O(1) time.

Algorithms & Data Structures

Author's notes

Classic question but I still fumbled the implementation a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map for O(1) access to cache items and a doubly linked list to maintain the order of usage, with the most recently used at the head and least recently used at the tail. For get, move the accessed node to the head; for put, add new nodes to the head and evict the tail when capacity is exceeded.

Pro tip: Mention that you would use a doubly linked list (not singly) to achieve O(1) removal from the middle, and consider thread-safety if the cache might be accessed concurrently.

1. Clarify requirements

Confirm the cache capacity, whether keys and values are integers, and if thread-safety is required. Also, clarify the expected behavior when updating an existing key.

2. Choose data structures

Select a hash map for O(1) key lookup and a doubly linked list to track usage order. Explain that the hash map stores key to node references, and the list maintains MRU to LRU order.

3. Design operations

For get: if key exists, move its node to the head and return value; else return -1. For put: if key exists, update value and move to head; else create new node, add to head, and if capacity exceeded, remove tail and delete from map.

4. Handle edge cases

Consider capacity 0 or 1, updating an existing key, and eviction when the cache is full. Ensure that the linked list and hash map stay in sync.

5. Analyze complexity

State that both get and put run in O(1) time because hash map operations are O(1) and linked list insertions/removals are O(1) given direct node references.

Key Points to Mention

Hash map provides O(1) access to cache nodes.
Doubly linked list allows O(1) removal and insertion at both ends.
Most recently used item is at the head; least recently used at the tail.
On get, move the accessed node to the head to mark it as recently used.
On put, if capacity is exceeded, remove the tail node and delete its key from the hash map.
Consider thread-safety with locks or concurrent data structures if needed.

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