MediumNeetCode150Hash TableDesignHeap (Priority Queue)OOP
Design Twitter
Design simplified Twitter.
Examples
Input
Twitter: postTweet(1,hello), getNewsFeed(1)=[hello]
Output
null,null,[1]
Feed shows tweets from self and followed users.
Constraints
- •
1 <= userId <= 500 - •
0 <= tweetId <= 10^4 - •
All calls valid
Approaches
Store tweets, merge on feed.
CodeT: O(F*N) getNewsFeed | S: O(N+F*N) storage
Merge k sorted feeds.
CodeT: O(k * log k * 10) | S: O(N) heap + storage
Same approach.
CodeT: O(1) post, O(F*logF) feed | S: O(N) store
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Hash Map + List | O(F*N) getNewsFeed | O(N+F*N) storage | Store tweets, merge on feed. |
| Hash Map + Heap | O(k * log k * 10) | O(N) heap + storage | Merge k sorted feeds. |
| Hash Map + Min Heap | O(1) post, O(F*logF) feed | O(N) store | Same approach. |
Hash Map + List
T: O(F*N) getNewsFeedS: O(N+F*N) storage
Store tweets, merge on feed.
Hash Map + Heap
T: O(k * log k * 10)S: O(N) heap + storage
Merge k sorted feeds.
Hash Map + Min Heap
T: O(1) post, O(F*logF) feedS: O(N) store
Same approach.
Common Mistakes
Not handling no follows
Wrong tweet ordering
Not limiting feed to 10