Design a simplified Twitter: postTweet, getNewsFeed (10 most recent), follow, unfollow.
postTweet(1,5), getNewsFeed(1)→[5], follow(1,2), postTweet(2,6), getNewsFeed(1)→[6,5], unfollow(1,2), getNewsFeed(1)→[5]
HashMap for user tweets (with timestamp), HashMap for follow sets. Merge k sorted tweet streams using a max-heap.
- tweets: Map.
- follows: Map>.
- getNewsFeed: collect all tweets from self and followees, use heap to get top 10.
- follow/unfollow: add/remove from follows set.
import java.util.*;
class Twitter {
Map<Integer, List<int[]>> tweets = new HashMap<>();
Map<Integer, Set<Integer>> follows = new HashMap<>();
int time = 0;
public void postTweet(int userId, int tweetId) {
tweets.computeIfAbsent(userId, k->new ArrayList<>()).add(new int[]{time++, tweetId});
}
public List<Integer> getNewsFeed(int userId) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->b[0]-a[0]); // max-heap by time
Set<Integer> seen = new HashSet<>();
seen.add(userId);
for (int[] t : tweets.getOrDefault(userId, Collections.emptyList())) pq.offer(t);
for (int f : follows.getOrDefault(userId, Collections.emptySet()))
for (int[] t : tweets.getOrDefault(f, Collections.emptyList())) pq.offer(t);
List<Integer> feed = new ArrayList<>();
while (!pq.isEmpty() && feed.size() < 10) feed.add(pq.poll()[1]);
return feed;
}
public void follow(int f, int e) { follows.computeIfAbsent(f, k->new HashSet<>()).add(e); }
public void unfollow(int f, int e) { follows.getOrDefault(f, new HashSet<>()).remove(e); }
}
- Time Complexity: getNewsFeed: O(N log N) where N=total tweets
- Space Complexity: O(N)