Heap · LC #355
Design Twitter
Store tweets with a global timestamp per user, store followee sets per user. getNewsFeed collects all tweets from user+followees and uses a max-heap (or sort) to return the 10 most recent.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Design a simplified Twitter with: `postTweet(userId, tweetId)`, `getNewsFeed(userId)` (10 most recent from user + followees), `follow(follower, followee)`, `unfollow(follower, followee)`.
Sample I/O
postTweet(1, 5), postTweet(1, 3) getNewsFeed(1) → [3, 5] follow(1, 2), postTweet(2, 6) getNewsFeed(1) → [6, 3, 5] unfollow(1, 2) getNewsFeed(1) → [3, 5]
Intuition
How to Think About It
Intuition
Tweets are just (timestamp, tweetId) pairs. A global counter provides recency ordering. The news feed merges k sorted lists (one per followed user) - a classic k-way merge via max-heap.
Core Concept
tweets: Map<userId, [timestamp, tweetId][]>. follows: Map<userId, Set<userId>>. getNewsFeed: gather all tweets from user + followees, max-heap by timestamp, return top 10 tweet IDs.
When to use
System design practice for social feed; k-way merge of sorted streams; any "top-k from multiple sources" pattern.
When NOT to use
Production Twitter would need distributed storage, fan-out on write, and pagination - this is an interview simplification.
Key Insights
What to Know Cold
- Global monotonic timestamp enables cross-user recency comparison without wall clock.
- User implicitly follows themselves for news feed - include userId in the feed-user set.
- Efficient k-way merge: one heap entry per user, each pointing to their latest unread tweet.
- unfollow during iteration of follows set is safe with a Set (no ConcurrentModification).
- getNewsFeed top-10 cap bounds heap operations even if total tweets is large.
1 example
Worked Examples
Social feed with follow/unfollow
User 1 follows user 2; both post tweets; getNewsFeed returns merged recency-ordered list.
HashMap for tweets+follows; sort/heap for top-10 merging.
Output: getNewsFeed(1) → [6, 3, 5] after follow(1,2) and postTweet(2,6)
Models real social-media feed architecture and demonstrates k-way merge from multiple sources.