Design Twitter
Implement a miniature feed. Users can post unique tweet IDs, follow or unfollow others, and request their 10 most recent visible tweets. A user always sees their own tweets.
Work through the cases
3 examplesInput notation
Commands post user tweet, follow user other, unfollow user other, or feed user, one per line. Post order defines time.Expected result
For each feed, tweet IDs newest first separated by spaces, or empty.Case 1
Input
post 1 10 post 2 20 follow 1 2 feed 1 unfollow 1 2 feed 1
Expected output
20 10 10
Case 2
Input
feed 3 post 3 7 feed 3
Expected output
empty 7
Case 3
Input
post 1 1 post 1 2 feed 1
Expected output
2 1
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Post, follow, and fetch the ten most recent tweets from a user and followees. A full scan of all tweets is wasteful. Store each user’s tweets and follow set, and stamp tweets with a global clock. A feed gathers the latest ten from each relevant user and keeps the ten newest. Follow/unfollow only edit the set.
JavaScript and C++ implementation note: these versions scan the global post list backwards until ten eligible tweets are found. Feed retrieval takes O(P) worst-case time for P stored posts; posting and follow changes take average O(1) time. The source discussion describes the Java/Python implementations.
class Twitter {
private Map<Integer, List<Integer>> userTweets;
private Map<Integer, Set<Integer>> userFollowing;
private Map<Integer, Integer> tweets;
private int time;
/** Initialize your data structure here. */
public Twitter() {
userTweets = new HashMap<>();
userFollowing = new HashMap<>();
tweets = new HashMap<>();
time = 0;
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
userTweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(tweetId);
tweets.put(tweetId, ++time);
}
/**
* Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed
* must be posted by users who the user followed or by the user herself. Tweets must be ordered
* from most recent to least recent.
*/
public List<Integer> getNewsFeed(int userId) {
Set<Integer> following = userFollowing.getOrDefault(userId, new HashSet<>());
Set<Integer> users = new HashSet<>(following);
users.add(userId);
PriorityQueue<Integer> pq
= new PriorityQueue<>(10, (a, b) -> (tweets.get(b) - tweets.get(a)));
for (Integer u : users) {
List<Integer> userTweet = userTweets.get(u);
if (userTweet != null && !userTweet.isEmpty()) {
for (int i = userTweet.size() - 1, k = 10; i >= 0 && k > 0; --i, --k) {
pq.offer(userTweet.get(i));
}
}
}
List<Integer> res = new ArrayList<>();
while (!pq.isEmpty() && res.size() < 10) {
res.add(pq.poll());
}
return res;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
userFollowing.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
userFollowing.computeIfAbsent(followerId, k -> new HashSet<>()).remove(followeeId);
}
}
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* List<Integer> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
*/Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.