Design Data Structures

Implement a custom data structure (LRU cache, LFU cache, min stack, range queries) meeting specific API and time-complexity requirements.

When to use it

Asked to 'design and implement' a cache, special stack, or data structure.
Combination of multiple primitives (hash map + doubly linked list for LRU).

Signals in the problem statement

'Implement a ...' or 'Design a ...'.
Multiple operations with strict time complexity requirements (e.g. O(1) get, put, delete).

Common pitfalls

Forgetting edge cases in linked-list manipulation (removing head/tail, single-node list).
Not recognizing that O(1) eviction + O(1) lookup requires a combo of hash map + linked list.

Practice Problems

LRU Cache

Medium

Asked at: Amazon, Google, Meta, Microsoft

Practiced

Design a data structure for Least Recently Used (LRU) cache with O(1) get and put operations. Capacity is fixed; when full, evict the least recently used item.

Time: O(1) get/put · Space: O(capacity)

Min Stack

Medium

Asked at: Amazon, Bloomberg, Google

Practiced

Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time.

Time: O(1) all ops · Space: O(n)