Design Twitter
mediumTime: O(k log n)Space: O(n)
Signals to notice
design simplified Twittermerge k sorted tweet streamsOOP + heap
Brute force first
For each getNewsFeed, collect all tweets from followed users and sort — O(total tweets).
The key insight
Each user has a linked list of tweets (newest first). getNewsFeed: put heads of all followed users' lists in a max-heap (by time). Pop 10 times, pushing each popped user's next tweet. O(k log k).
What must stay true
The max-heap merges k sorted streams to find the 10 most recent tweets across all followed users — same as merge-k-sorted-lists.
Easy way to go wrong
Storing tweets globally — keeping tweets per-user makes follow/unfollow independent of tweet data and avoids cleanup on unfollow.