Skip to content

355. Design Twitter

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 ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
  • List<Integer> getNewsFeed(int userId) Retrieves 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 themself. Tweets must be ordered from most recent to least recent.
  • void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
  • void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

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 <= 500
  • 0 <= tweetId <= 104
  • All the tweets have unique IDs.
  • At most 3 * 104 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

Solution:

class Twitter {
    static class Tweet{
        int tweetId;
        int timeStamp;

        Tweet(int tweetId, int timeStamp){
            this.tweetId = tweetId;
            this.timeStamp = timeStamp;
        }
    }

    private Map<Integer, Set<Integer>> followeesByFollower;
  // 关注者的用户ID,  set: 包含该用户所关注的用户id
    private Map<Integer, List<Tweet>> tweetsByUser;
  // 用户id, list 包含该用户用户的的所有推文
    private PriorityQueue<Tweet> tweetsPQ;
  // 按照时间顺序存储推文 (最新的推文会被优先处理)
    private int timeStamp;
  // 计数器, 用来生成推文的时间戳 (每发布一条新推文, 时间戳就递增1).


    // 构造函数, 初始化各个成员变量
  // Constructor 
    public Twitter() {
        followeesByFollower = new HashMap<Integer, Set<Integer>>();
        tweetsByUser = new HashMap<Integer, List<Tweet>>();
        timeStamp = 0;
        tweetsPQ = new PriorityQueue<>((t1, t2) -> Integer.compare(t2.timeStamp, t1.timeStamp));
    }

    public void postTweet(int userId, int tweetId) {
        Tweet tweet = new Tweet(tweetId, timeStamp++);
        tweetsByUser.computeIfAbsent(userId, k -> new ArrayList<Tweet>()).add(tweet);
    }
  // TC: O(1)
  // SC: O(1)

    public List<Integer> getNewsFeed(int userId) {
        List<Integer> res = new ArrayList<Integer>();
        if (tweetsByUser.containsKey(userId)){
            for (Tweet tweet : tweetsByUser.get(userId)){
                tweetsPQ.offer(tweet);
            }
        }

        if (followeesByFollower.containsKey(userId)){
            for (int followee : followeesByFollower.get(userId)){
                if (tweetsByUser.containsKey(followee)){
                    for (Tweet tweet : tweetsByUser.get(followee)){
                        tweetsPQ.offer(tweet);
                    }
                }
            }
        }
      // O(n^2logn^2)

        while(!tweetsPQ.isEmpty() && res.size() < 10){
            res.add(tweetsPQ.poll().tweetId);
        }

        tweetsPQ.clear();

        return res;
    }
  //  TC O((f * t) * log(f * t))

  //  SC: O(f*t)

    public void follow(int followerId, int followeeId) {
        followeesByFollower.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

  // TC: O(1)
  // SC: O(1)

    public void unfollow(int followerId, int followeeId) {
        if (followeesByFollower.containsKey(followerId)){
            followeesByFollower.get(followerId).remove(followeeId);
        }
    }
  // TC: O(1)
  // SC: O(1)
}

/**
 * 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);
 */

public static int compare(int x, int y)
Parameter :
x : the first int to compare
y : the second int to compare

Return :
This method returns the value zero if (x==y), 
if (x < y) then it returns a value less than zero 
and if (x > y) then it returns a value greater than zero.

tweetsByUser.get(userId) 和 followeesByFollower.get(userId) 都是 O(1)。

遍历 userId 和所有 followee 的推文，假设推文数量为 n。

每次推文被加入 PriorityQueue 的时间复杂度是 O(log n)。
假设一个用户关注了 f 个用户，每个用户的推文数量为 t。那么总体推文的数量为 f * t。

将所有推文加入 PriorityQueue 的时间复杂度是 O((f * t) * log(f * t))。
从 PriorityQueue 中取出最多10条推文，每次操作是 O(log n)，最多10次，时间复杂度为 O(10 * log n) = O(log n)。