Designing a Twitter Feed

labuladongOriginalAbout 1653 words

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

LeetCode	Difficulty
355. Design Twitter	🟠

Prerequisites

Before reading this article, you should first learn:

LeetCode problem #355 "Design Twitter" is not only an interesting question itself but also combines the algorithm for merging multiple sorted linked lists with object-oriented design (OO design), making it highly practical. This article will guide you through this problem.

As for which features of Twitter are related to algorithms, you'll understand once we describe the problem requirements.

I. Problem Description and Application Scenarios

Twitter and Weibo have similar functionalities. We mainly need to implement the following APIs:

class Twitter {

    // user posts a tweet
    public void postTweet(int userId, int tweetId) {}
    
    // return the most recent tweet ids from the
    // users that this user follows (including
    // at most 10 tweets, and these tweets must be sorted in reverse chronological order
    public List<Integer> getNewsFeed(int userId) {}
    
    // follower follows followee, create new if Id doesn't exist
    public void follow(int followerId, int followeeId) {}
    
    // follower unfollows followee, do nothing if Id doesn't exist
    public void unfollow(int followerId, int followeeId) {}
}

举个具体的例子，方便大家理解 API 的具体用法：

Twitter twitter = new Twitter();

twitter.postTweet(1, 5);
// User 1 posted a new tweet 5

twitter.getNewsFeed(1);
// return [5], because users follow themselves by default

twitter.follow(1, 2);
// User 1 followed user 2

twitter.postTweet(2, 6);
// User 2 posted a new tweet (id = 6)

twitter.getNewsFeed(1);
// return [6, 5]
// Explanation: User 1 follows themselves and user 2, so their most recent tweets are returned
// Also, 6 must come before 5 because 6 was posted more recently

twitter.unfollow(1, 2);
// User 1 unfollowed user 2

twitter.getNewsFeed(1);
// return [5]

This scenario is very common in our daily life. Take the social media feed as an example: suppose I just added a celebrity's WeChat, and then I refresh my social media feed. The celebrity's posts will appear in my feed, sorted by time along with other posts. The difference is that Twitter is a one-way follow, while WeChat friends are like mutual followers. Unless, of course, someone is blocked...

Most of these APIs are easy to implement, but the core challenge is the getNewsFeed function. The results must be in chronological order, but the problem is that user followings are dynamic. How do we handle this?

This is where algorithms come into play: If we store each user's tweets in a linked list, where each node contains a tweet id and a timestamp time (to record the posting time for comparison), and this list is sorted by time, then if a user follows k other users, we can use an algorithm to merge k sorted linked lists to get a sorted feed list, thus correctly implementing getNewsFeed!

We'll discuss the specific algorithm shortly. However, even if we master the algorithm, how should we program the representation of a user user and a tweet tweet to smoothly apply the algorithm? This involves simple object-oriented design, which we will delve into step by step.

II. Object-Oriented Design

Based on the previous analysis, we need a User class to store user information, and a Tweet class to store tweet information, which will also serve as nodes in the linked list. Let's set up the overall framework first:

class Twitter {
    private static int timestamp = 0;
    private static class Tweet {}
    private static class User {}

    // Here are the other API methods
    public void postTweet(int userId, int tweetId) {}
    public List<Integer> getNewsFeed(int userId) {}
    public void follow(int followerId, int followeeId) {}
    public void unfollow(int followerId, int followeeId) {}
}

The reason for placing the Tweet and User classes inside the Twitter class is that the Tweet class requires a global timestamp timestamp, and the User class needs the Tweet class to record the tweets sent by users. Therefore, they are both implemented as inner classes. However, for clarity and simplicity, each inner class and API method will be implemented separately in the following sections.

Implementation of the Tweet Class

Based on the previous analysis, the Tweet class is straightforward to implement: each Tweet instance needs to record its own tweetId and the posting time time. Additionally, as a linked list node, it should have a next pointer pointing to the next node.

class Tweet {
    private int id;
    private int time;
    private Tweet next;

    // Need to pass in the tweet content (id) and posting time
    public Tweet(int id, int time) {
        this.id = id;
        this.time = time;
        this.next = null;
    }
}

Implementation of the User Class

Let's consider what information a user needs to store in a real-world scenario: userId, a list of followed users, and a list of tweets posted by the user. The list of followed users should be stored using a set (Hash Set) because it does not allow duplicates and supports quick lookup. The list of tweets should be stored using a linked list to facilitate operations such as ordered merging. Here's a diagram to help understand:

Additionally, following object-oriented design principles, actions like "follow", "unfollow", and "post" should be behaviors of the User class. Since the list of followed users and tweets are stored within the User class, we should also add the methods follow, unfollow, and post to the User class:

// static int timestamp = 0
class User {
    private int id;
    public Set<Integer> followed;
    // head node of the linked list of tweets posted by the user
    public Tweet head;

    public User(int userId) {
        followed = new HashSet<>();
        this.id = userId;
        this.head = null;
        // follow oneself
        follow(id);
    }

    public void follow(int userId) {
        followed.add(userId);
    }

    public void unfollow(int userId) {
        // cannot unfollow oneself
        if (userId != this.id)
            followed.remove(userId);
    }

    public void post(int tweetId) {
        Tweet twt = new Tweet(tweetId, timestamp);
        timestamp++;
        // insert the newly created tweet at the head of the linked list
        // tweets closer to the front have larger time values
        twt.next = head;
        head = twt;
    }
}

几个 API 方法的实现

class Twitter {
    private static int timestamp = 0;
    private static class Tweet {...}
    private static class User {...}

    // We need a mapping to associate userId with User objects
    private HashMap<Integer, User> userMap = new HashMap<>();

    // user posts a tweet
    public void postTweet(int userId, int tweetId) {
        // If userId doesn't exist, create a new one
        if (!userMap.containsKey(userId))
            userMap.put(userId, new User(userId));
        User u = userMap.get(userId);
        u.post(tweetId);
    }
    
    // follower follows followee
    public void follow(int followerId, int followeeId) {
        // If follower doesn't exist, create a new one
		if(!userMap.containsKey(followerId)){
			User u = new User(followerId);
			userMap.put(followerId, u);
		}
        // If followee doesn't exist, create a new one
		if(!userMap.containsKey(followeeId)){
			User u = new User(followeeId);
			userMap.put(followeeId, u);
		}
		userMap.get(followerId).follow(followeeId);
    }
    
    // follower unfollows followee, do nothing if Id doesn't exist
    public void unfollow(int followerId, int followeeId) {
        if (userMap.containsKey(followerId)) {
            User flwer = userMap.get(followerId);
            flwer.unfollow(followeeId);
        }
    }

    // Returns the most recent tweet ids from the user's followees (including himself)
    // At most 10 tweets, and these tweets must be sorted in reverse chronological order
    public List<Integer> getNewsFeed(int userId) {
        // Need to understand the algorithm, see below
    }
}

III. Algorithm Design

To implement the algorithm for merging k sorted linked lists, you need to use a Priority Queue. This data structure is the most important application of a binary heap. You can think of it as automatically sorting the elements you insert. When disordered elements are inserted, they are placed in the correct position, allowing you to retrieve elements in a sorted order, either from smallest to largest or vice versa. For more details, you can refer to this article on Implementing a Priority Queue with a Binary Heap.

PriorityQueue pq
# Insert in random order
for i in {2,4,1,9,6}:
    pq.add(i)
while pq not empty:
    # Extract the first (smallest) element each time
    print(pq.pop())

# Output in order: 1,2,4,6,9

With the help of this powerful data structure, we can easily implement this core functionality. Note that we set the priority queue to be sorted in descending order based on the time attribute, because a larger time value means a closer time, and it should be prioritized:

class Twitter {
    // To save space, omit the code part given above...

    public List<Integer> getNewsFeed(int userId) {
        List<Integer> res = new ArrayList<>();
        if (!userMap.containsKey(userId)) return res;
        // User IDs in the follow list
        Set<Integer> users = userMap.get(userId).followed;
        // Automatically sort by time attribute from
        // large to small, with capacity equal to the size
        PriorityQueue<Tweet> pq = 
            new PriorityQueue<>(users.size(), (a, b)->(b.time - a.time));

        // First insert all linked list head nodes into the priority queue
        for (int id : users) {
            Tweet twt = userMap.get(id).head;
            if (twt == null) continue;
            pq.add(twt);
        }

        while (!pq.isEmpty()) {
            // Returning a maximum of 10 items is enough
            if (res.size() == 10) break;
            // Pop the one with the largest time value (most recently published)
            Tweet twt = pq.poll();
            res.add(twt.id);
            // Insert the next Tweet for sorting
            if (twt.next != null) 
                pq.add(twt.next);
        }
        return res;
    }
}

The process is as follows, and below is a GIF I created to illustrate the process of merging linked lists. Suppose there are three Tweet linked lists sorted in descending order by the time attribute. We merge them in descending order and add them to res. Note that the numbers in the linked list nodes in the image represent the time attribute, not the id attribute:

At this point, the design of a highly simplified Twitter timeline feature is complete. For more problems related to data structure design, refer to Classic Exercises on Data Structure Design.