Understanding Design Twitter in Java

Introduction & Problem Explanation

Designing a simplified version of a social network like Twitter is a classic Object-Oriented Design (OOD) and algorithms problem. The system must support core social media interactions like posting tweets, following or unfollowing users, and generating a dynamic news feed of the 10 most recent tweets.

Specifically, the system must implement:

• postTweet(userId, tweetId): Compose a new tweet by a user. Each tweet must be ordered chronologically.
• follow(followerId, followeeId): Allow a follower to subscribe to a followee's tweets.
• unfollow(followerId, followeeId): Unsubscribe a follower from a followee's tweets.
• getNewsFeed(userId): Retrieve the 10 most recent tweet IDs in the user's news feed, collected from both the user and anyone they follow, sorted in descending chronological order.

The primary challenge is generating the news feed efficiently. Instead of copying all tweets into a global list and sorting them—which is highly inefficient—we model each user's tweets as a Singly Linked List and perform a k-way merge using a PriorityQueue (Max-Heap) to gather the top 10 tweets.

The Algorithmic Approach

Object Modeling + K-Way Merge (O(F log F) News Feed Generation)

We model the entities object-oriented style:

• Tweet Class: Acts as a node in a linked list. It contains a tweetId, a global time timestamp (incremented on each post), and a next reference pointing to the next older tweet from the same user.
• User Class: Stores a user id, a followed set containing the user IDs of people they follow, and a head reference pointing to the head of their Tweet linked list. By default, a user follows themselves so their own posts appear in their feed.
• News Feed Generation: To merge tweets from F followed users:
  1. We fetch the head tweet of each followed user and insert it into a Max-PriorityQueue sorted by timestamp.
  2. We poll the newest tweet from the queue, add its ID to the result feed, and if the tweet has a next pointer, we insert that next tweet back into the queue.
  3. We repeat this process until we have retrieved 10 tweets or the queue runs dry. This avoids looking at older, irrelevant tweets.

Step-by-Step Execution Walkthrough

Let's trace a scenario where User 1 follows User 2. User 1 posts Tweet 5, and User 2 posts Tweet 6:

1. Step 1 (Post Tweets):
   • User 1 posts Tweet 5 (timestamp t=0). User 1's tweet list: Tweet(5, t=0) → null.
   • User 2 posts Tweet 6 (timestamp t=1). User 2's tweet list: Tweet(6, t=1) → null.
2. Step 2 (Follow):
   • User 1 follows User 2. User 1's followed set: {1, 2}.
3. Step 3 (getNewsFeed(1)):
   • Gather head tweets for followed users {1, 2}:
     User 1 head: Tweet(5, t=0)
     User 2 head: Tweet(6, t=1)
   • Insert heads into Max-PriorityQueue. PQ state: [Tweet(6, t=1), Tweet(5, t=0)] (newest first).
4. Step 4 (Extract News Feed):
   • Extraction 1: Poll newest tweet from PQ: Tweet(6, t=1). Append ID 6 to feed list.
     Feed: [6]. Since Tweet(6).next is null, nothing is added back.
   • Extraction 2: Poll next newest tweet from PQ: Tweet(5, t=0). Append ID 5 to feed list.
     Feed: [6, 5]. Since Tweet(5).next is null, nothing is added back.
   • PQ is now empty. Return result feed: [6, 5].

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• t.next = head; head = t;: Prepends the new tweet to the user's list. This runs in O(1) time and naturally places the newest tweet at the head position.
• PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);: A custom Max-Heap comparator. This ensures that when we peek or poll from the queue, we always fetch the tweet with the highest timestamp (most recent).
• if (t.next != null) pq.offer(t.next);: The k-way merge step. Since each user's tweet list is already sorted, we only need to compare the next oldest tweet of the user whose tweet we just pulled.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.*;

public class DesignTwitter {

    public static class Twitter {
        // Global chronological counter to stamp tweets upon creation
        private static int timeStamp = 0;
        
        // Singly Linked List Node representing a tweet
        static class Tweet {
            int id;
            int time;
            Tweet next;
            
            public Tweet(int id) {
                this.id = id;
                this.time = timeStamp++;
            }
        }
        
        // Class representing a user with their follow list and tweet history
        static class User {
            int id;
            Set<Integer> followed;
            Tweet head;
            
            public User(int id) {
                this.id = id;
                this.followed = new HashSet<>();
                follow(id); // A user follows themselves to see their own tweets
            }
            
            void follow(int userId) { 
                followed.add(userId); 
            }
            
            void unfollow(int userId) { 
                if (userId != id) {
                    followed.remove(userId); 
                }
            }
            
            void post(int tweetId) {
                Tweet t = new Tweet(tweetId);
                t.next = head; // Prepend to linked list
                head = t;
            }
        }

        // Map to keep track of all users in the system
        private final Map<Integer, User> userMap = new HashMap<>();

        public Twitter() {
            // Constructor
        }

        // Compose a new tweet
        public void postTweet(int userId, int tweetId) {
            userMap.putIfAbsent(userId, new User(userId));
            userMap.get(userId).post(tweetId);
        }

        // Retrieve the 10 most recent tweets in the user's news feed
        public List<Integer> getNewsFeed(int userId) {
            List<Integer> res = new ArrayList<>();
            if (!userMap.containsKey(userId)) {
                return res;
            }
            
            // Max-Heap to sort tweets by timestamp (newest first)
            PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);
            
            // Push the head tweet of each followed user into the heap
            for (int uid : userMap.get(userId).followed) {
                Tweet t = userMap.get(uid).head;
                if (t != null) {
                    pq.offer(t);
                }
            }
            
            // Retrieve top 10 tweets using k-way merge
            while (!pq.isEmpty() && res.size() < 10) {
                Tweet t = pq.poll();
                res.add(t.id);
                if (t.next != null) {
                    pq.offer(t.next); // Add next oldest tweet from the same user
                }
            }
            return res;
        }

        // Follow a user
        public void follow(int followerId, int followeeId) {
            userMap.putIfAbsent(followerId, new User(followerId));
            userMap.putIfAbsent(followeeId, new User(followeeId));
            userMap.get(followerId).follow(followeeId);
        }

        // Unfollow a user
        public void unfollow(int followerId, int followeeId) {
            if (userMap.containsKey(followerId)) {
                userMap.get(followerId).unfollow(followeeId);
            }
        }
    }

    public static void main(String[] args) {
        Twitter twitter = new Twitter();
        System.out.println("--- Design Twitter Demonstration ---");
        
        System.out.println("User 1 posting Tweet 5...");
        twitter.postTweet(1, 5);
        System.out.println("News Feed for User 1: " + twitter.getNewsFeed(1) + " (Expected: [5])");
        
        System.out.println("\nUser 1 follows User 2...");
        twitter.follow(1, 2);
        System.out.println("User 2 posting Tweet 6...");
        twitter.postTweet(2, 6);
        System.out.println("News Feed for User 1: " + twitter.getNewsFeed(1) + " (Expected: [6, 5])");
        
        System.out.println("\nUser 1 unfollows User 2...");
        twitter.unfollow(1, 2);
        System.out.println("News Feed for User 1: " + twitter.getNewsFeed(1) + " (Expected: [5])");
    }
}

Conclusion

Designing Twitter demonstrates the efficiency of custom objects and list abstractions. By modeling tweets as linked lists and merging them through a Max-Priority Queue, we compile a localized news feed in logarithmic time, keeping operations fast and scalable.