Leetcode 355. Design Twitter

Problem Explanation:

Let's go through an example to understand the problem clearly. Suppose, we have a social media app like Twitter where users can make posts, follow/unfollow other users, and see their news feeds that contain the last 10 most recent posts made by them or the people they are following. The most recent post appears first.

Let's assume we have a User 1.

  1. User 1 created a new post with tweet id 5.
  2. When User 1 checks the newsfeed, they should see their post with id 5.
  3. Now, User 1 follows User 2.
  4. User 2 creates a new post with tweet id 6.
  5. When User 1 checks the newsfeed, User 1 will see User 2's post with id 6 first (because it is the most recent), then their own post with id 5.
  6. User 1 decides to unfollow User 2.
  7. When User 1 checks the newsfeed, User 1 will now only see their own post with id 5, because they are no longer following User 2.

Approach of the solution:

The solution to the problem uses a combination of data structures and algorithms for efficient operations.

  • It uses unordered_map to store all the user objects, where each user id is a key.
  • Each user has a Tweet linked list to store all the tweets posted by the users.
  • Each user also has a unordered_set to store all the users they follow.
  • When a tweet is posted, it adds the tweet at the start of the user's Tweet linked list.
  • While getting the newsfeed, a max heap (a heap data structure that is primarily used for getting the maximum value from a group of elements) is built from the most recent tweets of the current user and all the users that the current user follows. The most recent tweets are found and added to the newsfeed.

The Time complexity for postTweet and follow/unfollow operation is O(1). The time complexity for getNewsFeed is O(n*logk), where n is the total number of tweets and k is the maximum number of tweets a user can see in news feed.

Steps of the algorithm:

Let's take small example -

Suppose there are two users - User 1 and User 2 Initial System - {} (Empty)

  1. User 1 post a tweet with id 5. System - {1:[5]}
  2. User 1 checks the news feed. System doesn't change, News Feed - [5]
  3. User 1 follows User 2. System remains same because User 2 hasn't posted any tweet.
  4. User 2 posts a tweet with id 6. System - {1:[5], 2:[6]}
  5. User 2 checks their news feed. System doesn't change, News Feed for User 2 - [6]
  6. User 1 checks their news feed. System doesn't change, News Feed for User 1 - [6, 5] (6 is most recent so it appears first)
  7. User 1 unfollows User 2. System doesn't change, because unfollow operation only affect news feed.
  8. User 1 checks their news feed. System doesn't change, News Feed for User 1 - [5] (User 1 no longer follows User 2)
  9. Finally, system remains - {1:[5], 2:[6]}

Python

class Tweet: def init(self, id, time): self.id = id self.time = time self.next = None

class User: def init(self, id): self.id = id self.tweets = None self.following = set() self.follow(id)

1def follow(self, id):
2    self.following.add(id)
3
4def unfollow(self, id):
5    if id in self.following:
6        self.following.remove(id)
7
8def post(self, tweet):
9    tweet.next = self.tweets
10    self.tweets = tweet

class Twitter: def init(self): self.time = 0 self.tweets = {} self.users = {}

1def getUser(self, userId):
2    if userId not in self.users:
3        self.users[userId] = User(userId)
4    return self.users[userId]
5
6def postTweet(self, userId, tweetId):
7    user = self.getUser(userId)
8    tweet = Tweet(tweetId, self.time)
9    self.time += 1
10    user.post(tweet)
11
12def getNewsFeed(self, userId):
13    user = self.getUser(userId)
14    heap = []
15    tweets = [u.tweets for id in user.following for u in [self.getUser(id)] if u.tweets]
16    while tweets:
17        tweet = max(tweets, key=lambda t: t.time)
18        index = tweets.index(tweet)
19        tweets[index] = tweet.next
20        if not tweets[index]:
21            tweets.pop(index)
22        heap.append(tweet.id)
23        if len(heap)>10:
24            heap.pop(0)
25    return heap
26
27def follow(self, followerId, followeeId):
28    follower, followee = self.getUser(followerId), self.getUser(followeeId)
29    follower.follow(followeeId)
30
31def unfollow(self, followerId, followeeId):
32    if followerId != followeeId:
33        follower = self.getUser(followerId)
34        follower.unfollow(followeeId)

JavaScript

1
2javascript
3class Tweet {
4  constructor(id, time) {
5    this.id = id;
6    this.time = time;
7    this.next = null;
8  }
9}
10
11class User {
12  constructor(id) {
13    this.id = id;
14    this.tweets = null;
15    this.following = new Set();
16    this.follow(id);
17  }
18
19  follow(id) {
20    this.following.add(id);
21  }
22
23  unfollow(id) {
24    this.following.delete(id);
25  }
26
27  post(tweet) {
28    tweet.next = this.tweets;
29    this.tweets = tweet;
30  }
31}
32
33class Twitter {
34  constructor() {
35    this.time = 0;
36    this.tweets = {};
37    this.users = {};
38  }
39
40  getUser(userId) {
41    if (!(userId in this.users)) {
42      this.users[userId] = new User(userId);
43    }
44    return this.users[userId];
45  }
46
47  postTweet(userId, tweetId) {
48    const user = this.getUser(userId);
49    const tweet = new Tweet(tweetId, this.time);
50    this.time += 1;
51    user.post(tweet);
52  }
53
54  getNewsFeed(userId) {
55    const user = this.getUser(userId);
56    let heap = [];
57    let tweets = [...user.following].flatMap(id => (this.getUser(id).tweets ? this.getUser(id).tweets : []));
58    while (tweets.length) {
59      let tweet = tweets.reduce((max, t) => (t.time > max.time ? t : max));
60      let index = tweets.indexOf(tweet);
61      tweets[index] = tweet.next;
62      if (!tweets[index]) tweets.splice(index, 1);
63      heap.push(tweet.id);
64      if (heap.length > 10) heap.shift();
65    }
66    return heap;
67  }
68
69  follow(followerId, followeeId) {
70    let follower = this.getUser(followerId);
71    follower.follow(followeeId);
72  }
73
74  unfollow(followerId, followeeId) {
75    if (followerId !== followeeId) {
76      let follower = this.getUser(followerId);
77      follower.unfollow(followeeId);
78    }
79  }
80}

Java

1
2java
3class Tweet {
4  int id;
5  int time;
6  Tweet next;
7
8  public Tweet(int id, int time) {
9    this.id = id;
10    this.time = time;
11    this.next = null;
12  }
13}
14
15class User {
16  int id;
17  Tweet tweet;
18  Set<Integer> followed;
19
20  public User(int id) {
21    this.id = id;
22    this.followed = new HashSet<>();
23    follow(id); 
24  }
25
26  public void follow(int id){
27    followed.add(id);
28  }
29
30  public void unfollow(int id){
31    followed.remove(id);
32  }
33
34  public void post(Tweet t){
35    t.next = tweet;
36    tweet = t;
37  }
38}
39
40class Twitter {
41  private static int timeStamp;
42  private Map<Integer, User> userMap;
43
44  public Twitter() {
45    userMap = new HashMap<>();
46    timeStamp = 0;
47  }
48
49  public User getUser(int id) {
50    if (!userMap.containsKey(id)) {
51      User u = new User(id);
52      userMap.put(id, u);
53    }
54    return userMap.get(id);
55  }
56
57  public void postTweet(int userId, int tweetId) {
58    User user = getUser(userId);
59    Tweet t = new Tweet(tweetId, timeStamp++);
60    user.post(t);
61  }
62
63  public List<Integer> getNewsFeed(int userId) {
64    List<Integer> result = new LinkedList<>();
65    if(!userMap.containsKey(userId)) return result;
66    User u = getUser(userId);
67    PriorityQueue<Tweet> q = new PriorityQueue<Tweet>(u.followed.size(), (a,b)->(b.time-a.time));
68    for(int user: u.followed){
69      Tweet t = userMap.get(user).tweet;
70      if(t != null) q.add(t);
71    }
72    int count = 0;
73    while(!q.isEmpty() && count<10){
74      Tweet t = q.poll();
75      result.add(t.id);
76      count++;
77      if(t.next != null) q.add(t.next);
78    }
79    return result;
80  }
81
82  public void follow(int followerId, int followeeId) {
83    User u = getUser(followerId);
84    u.follow(followeeId);
85  }
86
87  public void unfollow(int followerId, int followeeId) {
88    if(followeeId == followerId) return;
89    getUser(followerId).unfollow(followeeId);
90  }
91}

As the example suggests, this problem is all about following the steps as explained. Prior knowledge of Data Structures such as LinkedList, Set and Queue as well as some utility methods can come in handy in solving this problem according to the algorithm described.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫