Table of Contents
Problem Statement
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.
Implement the Twitter class:
Twitter()Initializes your twitter object.void postTweet(int userId, int tweetId)Composes a new tweet with IDtweetIdby the useruserId. Each call to this function will be made with a uniquetweetId.List<Integer> getNewsFeed(int userId)Retrieves the10most 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 themself. Tweets must be ordered from most recent to least recent.void follow(int followerId, int followeeId)The user with IDfollowerIdstarted following the user with IDfolloweeId.void unfollow(int followerId, int followeeId)The user with IDfollowerIdstarted unfollowing the user with IDfolloweeId.
Example 1:
Input ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]] Output [null, null, [5], null, null, [6, 5], null, [5]] Explanation Twitter twitter = new Twitter(); twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5). twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5]. return [5] twitter.follow(1, 2); // User 1 follows user 2. twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6). twitter.getNewsFeed(1); // 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.unfollow(1, 2); // User 1 unfollows user 2. twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.
Constraints:
1 <= userId, followerId, followeeId <= 5000 <= tweetId <= 104- All the tweets have unique IDs.
- At most
3 * 104calls will be made topostTweet,getNewsFeed,follow, andunfollow. - A user cannot follow himself.
Logic
- Always draw a diagram to understand overall system.
- Visualization is very important.
- Complete the dry run first then code.
- Make simple components out of it
- Pay attention to details mentioned in problem statement
Golang Solution
/**
* Your Twitter object will be instantiated and called as such:
* obj := Constructor();
* obj.PostTweet(userId,tweetId);
* param_2 := obj.GetNewsFeed(userId);
* obj.Follow(fansId,actorsId);
* obj.Unfollow(fansId,actorsId);
*/
type User struct {
// UserID is followers
UserID int
// Actors are followee
ActorIDs map[int]struct{}
TweetInfo []Tweet
}
type Tweet struct {
ID int
Timestamp int64 // order by timeStamp in decresing order
}
type Twitter struct {
Users map[int]*User
Mu *sync.Mutex
CurrentTimeStamp int64
}
func Constructor() Twitter {
return Twitter{
Users: make(map[int]*User),
Mu: &sync.Mutex{},
}
}
func (this *Twitter) PostTweet(userID int, tweetID int) {
this.checkAndCreate(userID)
this.Users[userID].TweetInfo = append(this.Users[userID].TweetInfo,
Tweet{
ID: tweetID,
Timestamp: this.GetCurrentTimeStamp(),
})
}
func (this *Twitter) GetNewsFeed(userID int) []int {
result := []Tweet{}
if _, found := this.Users[userID]; !found {
return []int{}
}
result = append(result, this.Users[userID].TweetInfo...)
for actorID, _ := range this.Users[userID].ActorIDs {
// We can use heap here to get top 10 recent tweets
result = append(result, this.Users[actorID].TweetInfo...)
}
sort.Slice(result, func(i, j int) bool {
return result[i].Timestamp > result[j].Timestamp
})
if len(result) > 10 {
result = result[:10]
}
tweetIDs := []int{}
for _, r := range result {
tweetIDs = append(tweetIDs, r.ID)
}
return tweetIDs
}
func (this *Twitter) Follow(followerId int, followeeId int) {
if followerId == followeeId {
return
}
this.checkAndCreate(followerId)
this.checkAndCreate(followeeId)
this.Users[followerId].ActorIDs[followeeId] = struct{}{}
}
func (this *Twitter) Unfollow(followerId int, followeeId int) {
if followerId == followeeId {
return
}
if user, exist := this.Users[followerId]; exist {
delete(user.ActorIDs, followeeId)
}
}
func (this *Twitter) checkAndCreate(userID int) {
if _, found := this.Users[userID]; !found {
this.Users[userID] = &User{
UserID: userID,
ActorIDs: make(map[int]struct{}),
TweetInfo: []Tweet{},
}
}
}
func (this *Twitter) GetCurrentTimeStamp() int64 {
this.Mu.Lock()
defer this.Mu.Unlock()
this.CurrentTimeStamp++
return this.CurrentTimeStamp
}Output
Input
["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
[[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]
Output
[null,null,[5],null,null,[6,5],null,[5]]Please visit https: https://codeandalgo.com for more such contents.
Leave a Reply