Design Twitter
mediumTime: O(k log n)Space: O(n)
Recognize the pattern
design simplified Twittermerge k sorted tweet streamsOOP + heap
Brute force idea
For each getNewsFeed, collect all tweets from followed users and sort — O(total tweets).
Better approach
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).
Key invariant
The max-heap merges k sorted streams to find the 10 most recent tweets across all followed users — same as merge-k-sorted-lists.
Watch out for
Storing tweets globally — keeping tweets per-user makes follow/unfollow independent of tweet data and avoids cleanup on unfollow.