Problem: Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user's news feed. Your design should support the following methods:
- PostTweet(userId, tweetId): Compose a new tweet.
- GetNewsFeed(userId): 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.
- Follow(followerId, followeeId): Follower follows a followee.
- Unfollow(followerId, followeeId): Follower unfollows a followee.
Example:
Twitter twitter = new Twitter(); // User 1 posts a new tweet (id = 5). twitter.postTweet(1, 5); // User 1's news feed should return a list with 1 tweet id -> [5]. twitter.getNewsFeed(1); // User 1 follows user 2. twitter.follow(1, 2); // User 2 posts a new tweet (id = 6). twitter.postTweet(2, 6); // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. // Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5. twitter.getNewsFeed(1); // User 1 unfollows user 2. twitter.unfollow(1, 2); // User 1's news feed should return a list with 1 tweet id -> [5], // since user 1 is no longer following user 2. twitter.getNewsFeed(1);
Approach: There are many approaches to solve this problem but I think in real life GetNewsFeed is most frequently used operation so we should look to optimize this method even if we have to spend more time on other operations.
Taking the above thing into consideration, I came up with following approach:
Created a Tweet class:
private class Tweet
{
public int TweetId { get; set; }
public int TweetTime { get; set; } // a counter for now
}
I am going to maintain following maps:
- FollowerMap: Key is the user id and value is the list of user ids which key user id is following.
- FolloweeMap: Basically reverse of FollowerMap where value is the list of user ids who are following the key user id.
- FeedMap: Key is the user id and value is the list of tweets in user's news feed. This actually contains user's and his followee's tweets in sorted order.
- TweetHistoryMap: Key is user id and value is his all tweets in sorted order.
- UsersfeedMap: Key is user id and value is another map in which key is user's followee id and value is followee's tweets part of the user's news feed. It will help in case user unfollow a user and we need to remove all the tweets of unfollowed user from user's news feed.
Now the algorithm for all the methods is as follows:
- PostTweet: Create a tweet using tweetid. Now do the following:
- Add Tweet to TweetHistoryMap.
- Get all the userIds who are following this user from FolloweeMap and then for each follower:
- Add the tweet to FeedMap for followerId.
- Add the tweet to UsersfeedMap for followerId and given user id.
- GetNewsFeed: Return the top 10 tweets' ids from FeedMap for the given user id.
- Follow:
- Add entry to FollowerMap.
- Merge followee's tweet history into follower's FeedMap based on TweetTime using FeedMap and TweetHistoryMap. Add the tweets to UsersfeedMap too which were added into follower's FeedMap.
- Add entry to FolloweeMap.
- UnFollow:
- Remove entry from FollowerMap.
- Remove entry from FolloweeMap.
- Get all the tweets of the followee in the follower's news feed (FeedMap) using UsersfeedMap and remove all the tweets from FeedMap. To make this operation efficient, we are using LinkedList instead of just List in the FeedMap and TweetHistoryMap. UsersfeedMap contains the list of the references to nodes in the FeedMap.
Implementation in C#:
public class Twitter
{
private class Tweet
{
public int TweetId { get; set; }
public int TweetTime { get; set; }
}
private Dictionary<int, HashSet<int>> followerMap;
private Dictionary<int, HashSet<int>> followeeMap;
private Dictionary<int, LinkedList<Tweet>> feedMap;
private Dictionary<int, LinkedList<Tweet>> tweetHistoryMap;
private Dictionary<int, Dictionary<int, List<LinkedListNode<Tweet>>>> usersfeedMap;
private int time = 0;
private const int MAX_TWEET = 10;
/** Initialize your data structure here. */
public Twitter()
{
this.followerMap = new Dictionary<int, HashSet<int>>();
this.followeeMap = new Dictionary<int, HashSet<int>>();
this.feedMap = new Dictionary<int, LinkedList<Tweet>>();
this.usersfeedMap = new Dictionary<int, Dictionary<int, List<LinkedListNode<Tweet>>>>();
this.tweetHistoryMap = new Dictionary<int, LinkedList<Tweet>>();
this.time = 0;
}
/** Compose a new tweet. */
public void PostTweet(int userId, int tweetId)
{
Tweet tweet = new Tweet { TweetId = tweetId, TweetTime = time++ };
this.AddTweetToUserHistory(userId, tweet);
this.MaintainFeedHistory(userId, tweet);
}
/** 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 IList<int> GetNewsFeed(int userId)
{
return this.feedMap.ContainsKey(userId) ? this.feedMap[userId].Take(MAX_TWEET).Select(t => t.TweetId).ToList() : new List<int>();
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void Follow(int followerId, int followeeId)
{
if (followerId == followeeId)
{
return;
}
if (!this.followerMap.ContainsKey(followerId))
{
this.followerMap.Add(followerId, new HashSet<int>());
}
if (this.followerMap[followerId].Add(followeeId))
{
this.AddTweetsonFollow(followerId, followeeId);
}
if (!this.followeeMap.ContainsKey(followeeId))
{
this.followeeMap.Add(followeeId, new HashSet<int>());
}
this.followeeMap[followeeId].Add(followerId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void Unfollow(int followerId, int followeeId)
{
if (followerId == followeeId)
{
return;
}
if (this.followerMap.ContainsKey(followerId))
{
this.followerMap[followerId].Remove(followeeId);
}
if (this.followeeMap.ContainsKey(followeeId))
{
this.followeeMap[followeeId].Remove(followerId);
}
this.RemoveTweetsOnUnFollow(followerId, followeeId);
}
private void MaintainFeedHistory(int userId, Tweet tweet)
{
HashSet<int> targetUsers = this.followeeMap.ContainsKey(userId) ? this.followeeMap[userId] : new HashSet<int>();
targetUsers.Add(userId);
foreach (int uId in targetUsers)
{
if (!this.feedMap.ContainsKey(uId))
{
this.feedMap.Add(uId, new LinkedList<Tweet>());
}
LinkedListNode<Tweet> tweetNode = this.feedMap[uId].AddFirst(tweet);
if (uId != userId)
{
this.AddTweetToUserFeedMap(uId, userId, tweetNode);
}
}
}
private void AddTweetToUserFeedMap(int followerId, int followeeId, LinkedListNode<Tweet> tweetNode)
{
if (!this.usersfeedMap.ContainsKey(followerId))
{
this.usersfeedMap.Add(followerId, new Dictionary<int, List<LinkedListNode<Tweet>>>());
}
if (!this.usersfeedMap[followerId].ContainsKey(followeeId))
{
this.usersfeedMap[followerId].Add(followeeId, new List<LinkedListNode<Tweet>>());
}
this.usersfeedMap[followerId][followeeId].Add(tweetNode);
}
private void AddTweetToUserHistory(int userId, Tweet tweet)
{
if (!this.tweetHistoryMap.ContainsKey(userId))
{
this.tweetHistoryMap.Add(userId, new LinkedList<Tweet>());
}
this.tweetHistoryMap[userId].AddFirst(tweet);
}
private void RemoveTweetsOnUnFollow(int followerId, int followeeId)
{
if (this.usersfeedMap.ContainsKey(followerId))
{
if (this.usersfeedMap[followerId].ContainsKey(followeeId))
{
List<LinkedListNode<Tweet>> tweetNodes = this.usersfeedMap[followerId][followeeId];
foreach(LinkedListNode<Tweet> tweetNode in tweetNodes)
{
this.feedMap[followerId].Remove(tweetNode);
}
this.usersfeedMap[followerId].Remove(followeeId);
}
}
}
private void AddTweetsonFollow(int followerId, int followeeId)
{
LinkedList<Tweet> followeeTweets = this.tweetHistoryMap.ContainsKey(followeeId) ? this.tweetHistoryMap[followeeId] : null;
LinkedList<Tweet> followerTweetsFeed = this.feedMap.ContainsKey(followerId) ? this.feedMap[followerId] : new LinkedList<Tweet>();
LinkedListNode<Tweet> followeeTweetsItr = followeeTweets?.First;
LinkedListNode<Tweet> followerTweetsFeedItr = followerTweetsFeed?.First;
while (followeeTweetsItr != null && followerTweetsFeedItr != null)
{
if (followeeTweetsItr.Value.TweetTime > followerTweetsFeedItr.Value.TweetTime)
{
LinkedListNode<Tweet> tweetNode = followerTweetsFeed.AddBefore(followerTweetsFeedItr, followeeTweetsItr.Value);
this.AddTweetToUserFeedMap(followerId, followeeId, tweetNode);
followeeTweetsItr = followeeTweetsItr.Next;
}
else
{
followerTweetsFeedItr = followerTweetsFeedItr.Next;
}
}
if (followerTweetsFeedItr == null)
{
followerTweetsFeedItr = followerTweetsFeed?.Last;
while (followeeTweetsItr != null)
{
LinkedListNode<Tweet> tweetNode = followerTweetsFeedItr == null ?
followerTweetsFeed.AddLast(followeeTweetsItr.Value)
: followerTweetsFeed.AddAfter(followerTweetsFeedItr, followeeTweetsItr.Value);
this.AddTweetToUserFeedMap(followerId, followeeId, tweetNode);
followeeTweetsItr = followeeTweetsItr.Next;
followerTweetsFeedItr = followerTweetsFeed.Last;
}
}
if (!this.feedMap.ContainsKey(followerId))
{
this.feedMap[followerId] = followerTweetsFeed;
}
}
}
Complexity:
- PostTweet: O(n) where n is the number of followers.
- GetNewsFeed: O(n) where n is the number of tweets to return.
- Follow: O(m + n) where m and n is the number of tweets in follower's news feed and followee's history respectively.
- Unfollow: O(n) where n is the number of followee's tweets in the follower's news feed.
No comments:
Post a Comment