Leetcode: Design Twitter
This question is asked at Twitter (Obviously!), Oracle, DoorDash, Paypal, and Amazon.
We want to design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and able to see the 10 most recent tweets in the user feed, so we want to implement a Twitter() class as a result.
Twitter() initializes a Twitter Object.
void postTweet() composes a new tweet with ID tweetID by the user userId, and each call to this function will be made by a unique tweetId.
List<Integer> getNewsFeed(int userId) Retrieves 10 most recent tweet Id's in the user news feed and the tweets are ordered from the most recent to the least recent.
void follow(int followerId, int followeeId) means that the user with the ID followerID started following the user with the followeeId. The same thing happens with the void unfollow() method.
Let's say in input is ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] and [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]] with the output as [null, null, [5], null, null, [6, 5], null, [5]].
Let's look at this step by step.
We first initialize a Twitter interface and have user 1 post a new tweet with id of 5. Then there should be a list of tweet id which will be [5]. Then user 1 follows user 2, and if user 2 posts a tweet, user 2's tweet should be before user 1's tweet. If now User 1 unfollows user 2, then user 2's tweet should no longer show up in user 1's feed.
First, we want to initialize 2 classes, a User and a Tweet. The tweet has an id of time and a next Tweet, which will be as a linked list. We initialize the tweet's id and time of the tweet in order to keep track of the most recent/least recent tweets, etc.
Now, we have a user with an id and a list of tweets. In the constructor, we initialize the HashSet of users that are followed, etc, and add elements to the HashSet to Follow and remove them to unfollow, respectively. Every time the user posts a new tweet, we should add it to the head of the tweet list accordingly, so that the earliest tweets are shown earlier in the linked list. We should finally have a hashmap to see if a user in a tweet exists.
We have a set to indicate the users of followed, the Tweet is tweet_head and the id. To initiate the user, we initialized the followed, the id, and commend (you must follow yourself) and initialize the tweet head. We add to the set for followed and remove from the set for unfollowing. Then we move the new tweet head for posting a new tweet.
For Twitter, we initialize a map of users. Then we compose a new tweet. A follower follows a followee and vice versa in terms of a hash map.
The news feed is the hardest part of creating Twitter. First, we get all tweet lists from one user including itself and all the people followed and add all the heads into a max heap. Every time we poll a tweet from the largest timestamp from the heap, we add the next tweet into the heap. So after all heads, we only need to add 9 tweets at most into this heap before we get the 10 most recent tweets.
Here's the final implementation:
public class Twitter {
private static int timeStamp = 0;
private Map<Integer, User> userMap;
private class Tweet {
public int id;
public int time;
public Tweet next;
//new tweet with id and timestamp
public Tweet(int id) {
this.id = id;
time = timeStamp;
next = null;
}
}
public class User{
public int id;
//who the user follows
public Set<Integer> followed;
//the tweets of the user
public Tweet tweet_head;
//initialize a user, and follow itself.
public User(int id) {
this.id = id;
followed = new HashSet<>();
follow(id);
tweet_head = null;
}
//follow a user in hash
public void follow(int id) {
followed.add(id);
}
//unfollow a user in hash
public void unfollow(int id) {
followed.remove(id);
}
//post the new tweet and add it to the head of linked list
public void post(int id) {
Tweet t = new Tweet(id);
t.next = tweet_head;
tweet_head = t;
}
}
//initialize a new hashMap for users
public Twitter() {
userMap = new HashMap<Integer, User> ();
}
//user posts tweet by putting it in a map of the user
public void postTweet(int userId, int tweetId) {
if(!userMap.containsKey(userId)) {
User u = new User(userId);
userMap.put(userId, u);
}
userMap.get(userId).post(tweetId);
}
//if neither user exists, it's invalid, otherwise, the follower follows the followee.
public void follow(int followerId, int followeeId) {
if(!userMap.containsKey(followerId)) {
User u = new User(followerId);
userMap.put(followerId, u);
}
if(userMap.containsKey(followeeId)) {
User u = new User(followeeId);
userMap.put(followeeId, u);
}
userMap.get(followerId).follow(followeeId);
}
//follower unfollows followee removing from ma[
public void unfollow(int followerId, int followeeId) {
if(!userMap.containsKey(followerId) || followerId == followeeId) return;
userMap.get(followerId).unfollow(followeeId);
}
//arrange HashMap by time and add the tweet in priority queue followed and poll() the first 10 entries.
public List<Integer> getNewFeed(int userId) {
List<Integer> res = new LinkedList<>();
if(!userMap.containsKey(userId)) return res;
Set<Integer> users = userMap.get(userId).followed;
PriorityQueue<Tweet> q = new PriorityQueue<Tweet>(users.size(), (a, b) -> (b.time - a.time));
for(int user: users) {
Tweet t = userMap.get(user).tweet_head;
if(t != null) q.add(t);
}
}
int n = 0;
while(!q.isEmpty() && n < 10) {
Tweet t = q.poll();
res.add(t.id);
n++;
if(t.next != null) {
q.add(t.next);
}
}
return res;
}
Comments
Post a Comment