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 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:

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.

Solution:

Algorithm Design:

Let's take a closer look at the requirements for getNewsFeed(int userId) method: The requirement says: 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.

We do not have to worry about the content of the tweet since we are only returning the tweet IDs.

The requirement says:
Each item in the news feed must be posted by users who the user followed or by the user.

One edge case could be: when a user has not followed anyone In that case the user would see only his/her posts ordered reverse-chronologically from newest to oldest.

This observation is very important since this immediately give a lot of insight on what data structure would be a good choice for us: for every user we could store their tweets in a LinkedList and whenever the user tweets we add that tweet at the head of the linked list. That way we just traverse from the head of theh linked list towards the tail of the linked list to get the tweets in the reverse chronological order.

Now let's try to extend our solution for situations when a user has followed at least one user. Let's suppose the user has followed (n - 1) users. So right now we have n linkedlists of tweets, which includes linked list of the tweets of the user himself / herself.

For every linkedlist the head has the most recent tweet of the user to whom the linked list belongs.

Using the above discussion how could we create the news feed in a very efficient way ? This is where deep knowledge of data structures come into play.

Use a min heap of tweets based on timestamp of all the tweets at the head of all the linked lists. The most recent tweet would be at the root of the min heap. Grab that tweet and insert the next tweet from the linked list to which the mist recent tweet belonged to the min heap. Now the next recent tweet is at the root of the min heap. Grab that tweet now. Repeat this process until we have gotten all the tweets we need to for the news feed.

Object Oriented Design:

Above discussion gives us all the information we need to design and implement a simple twitter like system.
  • We would need UserTweet class. Each UserTweet object would be a node of the linked list. Each UserTweet ould contain link to the next Tweet of the User it belongs to. Each UserTweet should have a tweetId and timestamp.
  • We would need a User class. Each User should have a userId, list of the users he/she follows and the most recent tweet, which is basically the head of the tweet linked list for that user. Since the list of tweets is a linked list, given the head we can get the rest of the tweets in a reverse-chronological order from newest to oldest, which is a core feature for the system we are building.
  • Twitter class: Twitter class needs to have a map between userId and the corresponding user object since the APIs that Twitter exposes contain userId and not the corresponsding user object, for example: postTweet(int userId, int tweetId), getNewsFeed(int userId), follow(int followerId, int followeeId), unfollow(int followerId, int followeeId)
Based on the discussion above we would code the simplified Twitter system as follows:

Code:


public class UserTweet {
    private int timestamp;
    private int tweetId;
    private UserTweet next; // pointer to chronologically next tweet
    public UserTweet(int tweetId, int timestamp) {
        this.tweetId = tweetId;
        this.timestamp = timestamp;
    }
    public int getTimestamp() {
        return timestamp;
    }
    public int getTweetId() {
        return tweetId;
    }
    public UserTweet getNext() {
        return next;
    }
    public void setNext(UserTweet nextTweet) {
        next = nextTweet;
    }

}

public class User {
    private int userId;
    private UserTweet head; // most recent tweet
    private Set<User> following; // list of users current user is following
    // we are taking Set data structure because there would be no duplicate user ids
    public User(int userId) {
        this.userId = userId;
        head = null;
        following = new HashSet<>();
        following.add(this); // a user always follows himself / herself since he/she sees his/her own posts in his/her news feed.
    }
    public void unfollow(User user) {
        if (user.getUserId() != this.getUserId()) { // a user cannot unfollow himself / herself
            following.remove(user);
        }
    }
    public void follow(User user) {
        following.add(user);
    }
    public Set<User> getFollowees() {
        return following;
    }
    public int getUserId() {
        return userId;
    }
    public UserTweet getMostRecentTweet() {
        return head;
    }
    public void setMostRecentTweet(UserTweet tweet) {
        head = tweet;
    }
}


class Twitter {
    
    public static int counter;
    private Map<Integer, User> useridToUserobject; // we need this map because in follow() and unfollow() methods 
                    // we pass userId and not User object, so we need a mapping between user id and corresponding user object

    /** Initialize your data structure here. */
    public Twitter() {
        counter = 0;
        useridToUserobject = new HashMap<>();
    }
    
    private boolean exists(int userId) {
        return useridToUserobject.containsKey(userId);   
    }
    
    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if (!exists(userId)) { // if this is the first call to this user, then create the user first
            useridToUserobject.put(userId, new User(userId));  
        }
        counter++; // increment timestamp
        UserTweet tweet = new UserTweet(tweetId, counter);
        User user = useridToUserobject.get(userId);
        if (user.getMostRecentTweet() == null) {
            // this is going to be the first tweet of the user
            user.setMostRecentTweet(tweet);
        }
        else {
            UserTweet previousHead = user.getMostRecentTweet();
            UserTweet newHead = tweet;
            user.setMostRecentTweet(newHead);
            newHead.setNext(previousHead);
        }
    }
    
    /** 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 List<Integer> getNewsFeed(int userId) {
        List<Integer> res = new ArrayList<>();
        if (!exists(userId)) {
            return res;
        }
        PriorityQueue<UserTweet> minHeap = new PriorityQueue<>(new Comparator(){
            public int compare(UserTweet t1, UserTweet t2){
                return t2.getTimestamp() - t1.getTimestamp();
            }
        });
        // intitialize the min heap with the most recent tweet of all followees of the current user
        for (User followee : useridToUserobject.get(userId).getFollowees()) {
            if (followee.getMostRecentTweet() != null) {
                minHeap.add(followee.getMostRecentTweet());
            }
        }
        while ((res.size() < 10) && !minHeap.isEmpty()) {
            UserTweet mostRecentTweet = minHeap.remove();
            res.add(mostRecentTweet.getTweetId());
            if (mostRecentTweet.getNext() != null) {
                minHeap.add(mostRecentTweet.getNext());
            }
        }
        return res;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if (!exists(followerId)) { // create the user if it is not created yet
            useridToUserobject.put(followerId, new User(followerId)); 
        }
        if (!exists(followeeId)) { // create the user if it is not created yet
            useridToUserobject.put(followeeId, new User(followeeId)); 
        }
        User follower = useridToUserobject.get(followerId);
        User followee = useridToUserobject.get(followeeId);
        follower.follow(followee);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
       if (!exists(followerId)) { // create the user if it is not created yet
            useridToUserobject.put(followerId, new User(followerId)); 
        }
        if (!exists(followeeId)) { // create the user if it is not created yet
            useridToUserobject.put(followeeId, new User(followeeId)); 
        } 
        User follower = useridToUserobject.get(followerId);
        User followee = useridToUserobject.get(followeeId);
        follower.unfollow(followee);
    }
}

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



In a System Design interview, your interviewer might ask you the following follow-up questions:

Further Enhancements:


What changes we need to make to enable Delete Tweet feature?

We would need a doubly linked list instead of singly linked list so that when we delete a tweet object we can do the following operation:
Tweet prev = tweetToBeDeleted.prev;
Tweet next = tweetToBedeleted.next;
prev.next = next;
next.prev = prev;


Here we are just returning 10 most recent tweets, whereas in real-world users go on scrolling to see more tweets. How could we implement this ?

A server call to getNewsFeed(int userId) should return way more than 10 tweetes and store in the client. The client side code should implement something similar to pagination, where in first call it would slice the whole resultset and show tweets with indices 0 to 9, then if the user scrolls more the client would show tweets with indices 10 to 19 and so on. So basically the client side code would go on displaying next 10 records as the user scrolls more. People familiar with Javascript would quickly recognize how similar it is to the array slice() function in Javacsript client side code.

Let's suppose the server-side call to getNewsFeed(int userId) return 1000 tweets and a users is continuing to scroll to see more than 1000 tweets. In that we would need to extend the getNewsFeed(int userId) implementation to return next 1000 tweets. This is why often when you you scroll too much to see older tweets you would encounter higher latency.



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave