These days, interviewers are increasingly testing design and implementation skills rather than just algorithmic problem-solving. If you're preparing for interviews, make sure you're comfortable with these problems!
1. LRU Cache
Build a cache that evicts the least recently used item when full. You need O(1) for both get and put, which means combining a hash map with a doubly linked list.
Follow-ups:
2. Min Stack
Implement a stack that can return its minimum element in O(1) time. Simple but elegant - teaches you to maintain auxiliary information efficiently.
Follow-ups:
- Max Stack (LC 716)
- Try implementing without extra space by encoding min with each element
3. Implement Trie (Prefix Tree)
Build the foundation for autocomplete and spell checkers. A tree where each node represents a character, perfect for prefix-based operations.
Follow-ups:
- Design Add and Search Words (LC 211) - supports wildcards
- Word Search II (LC 212) - uses Trie for optimization
- Replace Words (LC 648)
- Implement Magic Dictionary (LC 676)
4. Design HashMap
Build a hash map from scratch without using built-in hash tables. You'll handle hash functions, collision resolution, and understand what's happening under the hood.
Follow-ups:
- Design HashSet (LC 705)
- Implement with open addressing instead of chaining
- Add resizing when load factor exceeds threshold
5. Insert Delete GetRandom O(1)
Support insert, delete, and get random element - all in O(1). The trick is combining an ArrayList for random access with a HashMap for O(1) lookup. The delete operation is beautifully clever.
Follow-ups:
6. Design Twitter
Build a simplified Twitter with post, follow, unfollow, and timeline features. Tests your ability to model real-world systems and efficiently merge sorted lists from multiple users.
7. Design a Stack With Increment Operation
A stack where you can increment the bottom k elements. Naive approach is O(k), but lazy propagation makes it O(1). Great introduction to deferred operations.
Follow-ups:
- Think about how databases use similar techniques for deferred constraint checking
8. Time Based Key-Value Store
Store versioned values with timestamps and retrieve the value at or before any timestamp. Teaches you about versioning systems and binary search on historical data.
Follow-ups:
- Design In-Memory File System (LC 588)
- Think about how Git stores versioned data
9. Design Circular Queue
Implement a queue with fixed size using an array. The wraparound logic and distinguishing between full and empty states is trickier than it looks.
Follow-ups:
10. Snapshot Array
Support set, snap, and get operations where snap creates a version checkpoint. The key is not copying the entire array - only store what changed in each snapshot.
Bonus Problems Worth Checking Out
- Design Browser History (LC 1472)
- Design Underground System (LC 1396)
- Design Phone Directory (LC 379)
- Design Search Autocomplete System (LC 642)
- All O'one Data Structure (LC 432)
- Design Authentication Manager (LC 1797)
- Serialize and Deserialize Binary Tree (LC 297)
Add few more best problems in the comments below !!
Good luck with your interviews! 🚀