Design Twitter

XXX. Twitter Clone

Design

Data Structure

Problem Statement:

Design a simplified version of Twitter. The system should support the following:

1. Post a new tweet.
2. Retrieve the 10 most recent tweets in the user's news feed. Each item in the news feed must be posted by users who the user follows or by the user themselves. Tweets must be ordered from most recent to least recent.
3. Follow a user.
4. Unfollow a user.

Algorithm:

1. Maintain a User class to represent a user and their activity.
2. Use a Tweet class to represent a tweet, storing its ID, timestamp, and a link to the next tweet for efficient traversal.
3. Implement methods for posting tweets, retrieving the news feed, following, and unfollowing users.
4. For the news feed, use a priority queue to retrieve the 10 most recent tweets efficiently.

Complexity:

Time Complexity:

• postTweet: O(1)
• getNewsFeed: O(n log k), where n is the total number of tweets from followed users and k is the number of tweets to retrieve (at most 10).
• follow and unfollow: O(1)

Space Complexity: O(n), where n is the total number of tweets.

Java Implementation:

public class Twitter {
    private static int timeStamp = 0;

    // Map to store users and their data
    private Map userMap;

    // Nested Tweet class to store tweet information
    private class Tweet {
        public int id;
        public int time;
        public Tweet next;

        public Tweet(int id) {
            this.id = id;
            time = timeStamp++;
            next = null;
        }
    }

    // Nested User class to represent each user
    public class User {
        public int id;
        public Set followed;
        public Tweet tweet_head;

        public User(int id) {
            this.id = id;
            followed = new HashSet<>();
            follow(id); // Users follow themselves by default
            tweet_head = null;
        }

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

        public void unfollow(int id) {
            followed.remove(id);
        }

        // Post a new tweet and add it to the head of the tweet list
        public void post(int id) {
            Tweet t = new Tweet(id);
            t.next = tweet_head;
            tweet_head = t;
        }
    }

    /** Initialize your data structure here. */
    public Twitter() {
        userMap = new HashMap<>();
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        if (!userMap.containsKey(userId)) {
            User u = new User(userId);
            userMap.put(userId, u);
        }
        userMap.get(userId).post(tweetId);
    }

    /** Retrieve the 10 most recent tweet IDs in the user's news feed. */
    public List getNewsFeed(int userId) {
        List res = new LinkedList<>();

        if (!userMap.containsKey(userId)) return res;

        Set users = userMap.get(userId).followed;
        PriorityQueue q = new PriorityQueue<>(users.size(), (a, b) -> (b.time - a.time));

        // Add the tweet heads of all followed users to the priority queue
        for (int user : users) {
            Tweet t = userMap.get(user).tweet_head;
            if (t != null) {
                q.add(t);
            }
        }

        // Retrieve up to 10 most recent tweets
        int n = 0;
        while (!q.isEmpty() && n < 10) {
            Tweet t = q.poll();
            res.add(t.id);
            n++;
            if (t.next != null) {
                q.add(t.next);
            }
        }

        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 (!userMap.containsKey(followerId)) {
            User u = new User(followerId);
            userMap.put(followerId, u);
        }
        if (!userMap.containsKey(followeeId)) {
            User u = new User(followeeId);
            userMap.put(followeeId, u);
        }
        userMap.get(followerId).follow(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if (!userMap.containsKey(followerId) || followerId == followeeId) return;
        userMap.get(followerId).unfollow(followeeId);
    }
}