dsa2 min read
Kth Largest Element in a Stream — Min-Heap Design [Amazon Easy]
Design a class to find the kth largest element in a data stream. Min-heap of size k: the top is always the answer. Full C++, Java, JavaScript and Python.
Read →
Design
59 articles
dsa2 min read
Maximum Frequency Stack [Hard] — Frequency + Group Stacks
Design a stack that pops the most frequent element (breaking ties by recency) using frequency and group-stacks mapping.
Read →
dsa1 min read
Online Election — Precompute Leader + Binary Search
Answer election queries for who is leading at time t by precomputing the leader at each vote and binary searching.
Read →
dsa1 min read
Time Based Key-Value Store — Binary Search on Timestamps
Implement get(key, timestamp) using binary search on stored sorted timestamps for O(log n) retrieval.
Read →
dsa2 min read
LRU Cache [Medium] — Doubly Linked List + HashMap
Design a Least Recently Used cache with O(1) get and put operations using a HashMap combined with a doubly linked list.
Read →
dsa2 min read
Insert Delete GetRandom O(1) [Medium] — Array + HashMap Design
Design a set with O(1) insert, delete, and getRandom using a dynamic array combined with a HashMap for index tracking.
Read →
dsa2 min read
Encode and Decode TinyURL — HashMap Bidirectional Mapping
Design a URL shortener using two hash maps for O(1) encode and decode operations.
Read →
dsa2 min read
Design HashMap — Chaining with Linked Lists
Implement a hash map from scratch using an array of buckets with chaining for collision resolution.
Read →
dsa2 min read
Design HashSet — Bit Array or Chaining Approach
Implement a hash set from scratch supporting add, remove, and contains in O(1) average time.
Read →
dsa2 min read
Time Based Key-Value Store — HashMap + Binary Search
Design a time-stamped key-value store supporting set and get(key, timestamp) using binary search on sorted timestamps.
Read →
dsa2 min read
LFU Cache — HashMap + Frequency Buckets + DLL
Implement an LFU cache with O(1) get/put using three hash maps: key→val, key→freq, freq→OrderedDict.
Read →
dsa2 min read
All O'one Data Structure — DLL of Buckets + HashMap
Design a data structure supporting inc/dec and getMaxKey/getMinKey in O(1) using a doubly linked list of frequency buckets.
Read →
dsa2 min read
Design Twitter — HashMap + Heap for News Feed
Design Twitter with follow/unfollow and getNewsFeed using per-user tweet lists and a min-heap merge.
Read →
dsa3 min read
Design Twitter
Design a simplified Twitter with follow/unfollow and a news feed showing the 10 most recent tweets from followed users.
Read →
dsa2 min read
Maximum Frequency Stack
Design a stack that pops the most frequent element, breaking ties by most recently pushed, using frequency-bucket stacks.
Read →
dsa1 min read
Seat Reservation Manager
Design a seat manager that reserves the lowest numbered available seat and unreserves seats using a min-heap.
Read →
dsa2 min read
Flatten Multilevel Doubly Linked List — DFS Stack
Flatten a multilevel doubly linked list by inserting child sub-lists inline using DFS or an explicit stack.
Read →
dsa1 min read
Design Linked List — Sentinel Doubly Linked List
Implement a doubly linked list with sentinel head and tail nodes for clean O(1) insertions and deletions.
Read →
dsa2 min read
LRU Cache — Doubly Linked List + HashMap Implementation
Implement LRU Cache from scratch using a doubly linked list with sentinel nodes and a hash map for O(1) operations.
Read →
dsa2 min read
Design Browser History — Doubly Linked List Implementation
Design a browser history with visit, back, and forward operations using a doubly linked list for O(1) navigation.
Read →
dsa1 min read
Implement Stack Using Queues — Single Queue Rotation
Implement a stack using one queue by rotating all elements after each push to bring the new element to the front.
Read →
dsa1 min read
Implement Queue Using Stacks — Amortized O(1) Two-Stack
Implement a queue using two stacks with amortized O(1) operations by lazily transferring from inbox to outbox.
Read →
dsa1 min read
Min Stack — Parallel Min Tracking Stack
Design a stack with O(1) getMin by maintaining a parallel min-tracking stack alongside the main stack.
Read →
dsa1 min read
Number of Recent Calls — Sliding Window Queue
Count ping requests within the last 3000ms using a queue that slides expired entries off the front.
Read →
dsa1 min read
Online Stock Span — Monotonic Stack with Accumulated Span
Calculate the stock price span (consecutive days <= today) using a monotonic stack that accumulates spans.
Read →
dsa1 min read
Design Circular Queue — Array with Head and Tail Pointers
Implement a circular queue using a fixed-size array with head and tail pointers and a size counter.
Read →
dsa1 min read
Flatten Nested List Iterator — Stack-Based Lazy Expansion
Implement an iterator for a nested list using a stack that lazily expands nested lists as elements are consumed.
Read →
dsa1 min read
Design Hit Counter — Queue with Timestamp Expiry
Design a hit counter that returns hits in the past 5 minutes using a queue to expire old timestamps.
Read →
dsa2 min read
Maximum Frequency Stack — Bucket-per-Frequency Design
Design a frequency stack with O(1) push and pop-max-frequency using a map of frequency to stack of elements.
Read →
dsa2 min read
Find Median from Data Stream — Two Heaps
Find the median dynamically as numbers are added using two heaps: a max-heap for the lower half and min-heap for upper.
Read →
dsa1 min read
Serialize and Deserialize Binary Tree — BFS Level Order
Serialize a binary tree to a string using BFS level-order and deserialize back using a queue for reconstruction.
Read →
dsa2 min read
Implement Trie (Prefix Tree) — Insert/Search/StartsWith
Implement a Trie with insert, search, and startsWith operations. Core data structure for all prefix-based problems.
Read →
dsa1 min read
Design Add and Search Words — Trie with Wildcard DFS
Trie that supports wildcard '.' matching any character. DFS through trie when '.' encountered, trying all children.
Read →
dsa1 min read
Stream of Characters — Reverse Suffix Trie
Query if any word ends at the current stream position. Insert reversed words into trie; maintain suffix deque to match from current position backwards.
Read →
dsa1 min read
Prefix and Suffix Search — Combined Key Trie
Find word with given prefix AND suffix. Insert 'suffix#word' for each suffix of each word into trie; query combines prefix+suffix search.
Read →
dsa1 min read
Map Sum Pairs — Trie with Value Propagation
Implement insert(key, val) and sum(prefix) returning sum of values for all keys with given prefix. Trie with value at end node.
Read →
dsa2 min read
Encode and Decode Strings — Delimiter and Length-Prefix Schemes
Design an encode/decode scheme for a list of strings. Length-prefix encoding (4-byte header per string) is collision-proof unlike delimiter-based approaches.
Read →
dsa2 min read
Meta — Flatten Nested List Iterator (Stack-Based)
Implement an iterator for a nested list that flattens it lazily. Meta favors this for testing iterator design, stack usage, and lazy evaluation.
Read →
dsa2 min read
Meta — Read N Characters Given read4 (Buffered Read)
Implement a read() function using a read4() primitive. Two variants: read once and read multiple times. Tests buffer management and pointer arithmetic.
Read →
dsa2 min read
Amazon — Kth Largest Element in a Stream (Min-Heap)
Design a stream that always returns the kth largest element after each add. Uses a min-heap of size k — the top is always the kth largest.
Read →
dsa2 min read
System Design DSA — Complete Guide (LRU, LFU, Caches, Data Structures)
Master system design problems that test data structure knowledge: LRU/LFU caches, Twitter feed, file systems, and 15+ design problems with full implementations.
Read →
dsa4 min read
Design Twitter — Social Media Feed with Top K Posts
Design a simplified Twitter where users post tweets and follow each other, with getNewsFeed returning the 10 most recent tweets from followed users using a min-heap merge.
Read →
dsa2 min read
Design a File System — Trie-Based Path Storage
Implement a file system that creates paths and associates values with them. Uses a Trie or HashMap to map full paths to values with O(L) operations.
Read →
dsa3 min read
Design Hit Counter — Count Requests in Last 300 Seconds
Design a hit counter that counts hits in the last 5 minutes using a deque-based sliding window or circular buffer with O(1) amortised operations.
Read →
dsa3 min read
Time Based Key-Value Store — Binary Search on Timestamps
Design a key-value store that returns values at or before a given timestamp. Uses a hashmap of sorted (timestamp, value) lists with binary search for O(log n) get.
Read →
dsa3 min read
Design Search Autocomplete System — Trie with Frequency Ranking
Design a search autocomplete system that returns top 3 historical queries matching the current prefix, sorted by frequency then lexicographically. Uses a Trie with per-node frequency maps.
Read →
dsa2 min read
Design Browser History — Stack-Based Navigation
Design a browser with visit, back, and forward navigation. Uses two stacks (or a doubly-ended array with pointer) for O(1) visit and O(steps) navigation.
Read →
dsa2 min read
Design a Leaderboard — Score Tracking with Top K
Design a leaderboard that tracks player scores, supports score additions, top K sum queries, and player resets using a hashmap with sorted aggregation.
Read →
dsa3 min read
Design Snake Game — Deque-Based State Machine
Simulate a snake game on a grid where the snake eats food to grow and dies if it hits walls or itself. Uses a deque for O(1) head/tail and a set for O(1) body collision checks.
Read →
dsa3 min read
Design Skiplist — Probabilistic Sorted Structure
Implement a skip list from scratch supporting search, add, and erase in O(log n) expected time. Uses layered linked lists with probabilistic level assignment.
Read →
dsa2 min read
Design Log Storage System — Timestamp Range Retrieval
Design a log storage system that retrieves log IDs within a timestamp range at a specified granularity (Year, Month, Day, Hour, Minute, Second).
Read →
dsa2 min read
Design Phone Directory — Available Number Pool
Design a phone directory managing available and allocated numbers with O(1) get, check, and release using a queue of free numbers and a boolean availability array.
Read →
dsa3 min read
Design In-Memory Database — Multi-Field Filtering
Design an in-memory key-value database that supports set, get, delete, and rank operations. Demonstrates combining hashmaps with sorted structures for efficient multi-key queries.
Read →
dsa2 min read
Design Min Stack — O(1) Minimum with Auxiliary Stack
Implement a stack that supports push, pop, top, and retrieving the minimum element in O(1) time using an auxiliary min-stack that tracks minimums at each level.
Read →
dsa2 min read
Find Median from Data Stream — Two-Heap Approach
Maintain a running median from a data stream using two heaps: a max-heap for the lower half and a min-heap for the upper half, rebalancing after each insertion.
Read →
dsa2 min read
Design Circular Queue — Ring Buffer Implementation
Implement a circular queue (ring buffer) with fixed capacity supporting enQueue, deQueue, Front, Rear, isEmpty, and isFull in O(1) time using head and tail pointers.
Read →
dsa2 min read
Design URL Shortener (TinyURL) — Hashing and Encoding
Design a URL shortener like TinyURL that encodes long URLs to short codes and decodes them back. Uses base-62 encoding with a counter or random string generation.
Read →
dsa1 min read
Design Parking System — Counter-Based Slot Management
Design a parking system with big, medium, and small spaces. O(1) addCar checks if space is available and decrements the counter, returning whether the car was parked.
Read →
dsa4 min read
System Design DSA — Master Recap & Pattern Cheatsheet
Complete recap of all 20 system design DSA problems: pattern classification, time complexities, key data structures, and decision framework for choosing the right design approach.
Read →