Understanding Design Twitter in Java

System design interviews often feature the challenge of Designing Twitter (or a similar social media feed). This problem is highly effective because it tests both Object-Oriented Design (OOD) modeling and algorithmic optimization. The system needs to support basic operations like posting tweets, following or unfollowing other users, and constructing a chronological news feed of the 10 most recent tweets.

Specifically, the required operations are:

• postTweet(userId, tweetId): Composes a new tweet. Tweets must be ordered chronologically.
• follow(followerId, followeeId): Subscribes a user to another user's tweets.
• unfollow(followerId, followeeId): Unsubscribes a user.
• getNewsFeed(userId): Retrieves the 10 most recent tweet IDs in the user's feed, originating from either the user themselves or anyone they currently follow, sorted in descending chronological order.

The main engineering hurdle lies in generating the news feed efficiently under high load. A naive solution that merges all tweets into a giant list and sorts them is too slow. Instead, we model each user's history as a Singly Linked List of tweets and perform a k-way merge using a PriorityQueue (Max-Heap).

The Object-Oriented Data Model

To implement this, we design two core entities:

• Tweet Class: Represents a single post. It acts as a node in a linked list, holding its tweetId, a global timestamp (incremented with each new post), and a next pointer pointing to the next older tweet by the same user. Prepended insertion ensures new posts become the head of the list in O(1) time.
• User Class: Holds a user id, a followed set containing the IDs of other users, and a head reference to the user's newest Tweet node. A user is initialized to automatically follow themselves.

Feed Generation via K-Way Merge

When getNewsFeed(userId) is called:

1. We initialize a Max-Heap (PriorityQueue) that compares tweets by timestamp.
2. We loop through the list of users that the target user follows, retrieving the head tweet of each user's linked list and offering it to the queue.
3. In a loop running at most 10 times, we poll the newest tweet from the heap, add it to our results list, and if that tweet has a next pointer, we insert that subsequent tweet back into the heap.

This guarantees we only look at the most relevant tweets, resulting in an efficient runtime of O(F log F) where F is the number of followed users.

Step-by-Step Scenario Trace

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

• Post Tweets: User 1's tweet list is Tweet(5, time=0) → null. User 2's tweet list is Tweet(6, time=1) → null.
• Follow: User 1 follows User 2, so User 1's follow set is {1, 2}.
• Heap Initialization: When generating the feed for User 1, we insert the head tweets of User 1 (Tweet 5) and User 2 (Tweet 6) into the PriorityQueue. The queue sorts them: [Tweet 6 (time=1), Tweet 5 (time=0)].
• Merge Loop:
  • Iteration 1: We poll the newest tweet Tweet 6 and add it to our feed. Its next pointer is null, so no new tweet is pushed. Feed is [6].
  • Iteration 2: We poll Tweet 5 and add it to our feed. Its next pointer is null. Feed is [6, 5].
  • The queue is empty, so we stop and return [6, 5].

Key Code 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 & Complexity Analysis

By avoiding a full global sort, our k-way merge keeps feed retrieval fast even as users follow hundreds of accounts. Posting a tweet is a constant O(1) operation, and fetching the feed runs in O(F log F) time. This demonstrates how selecting the right combination of data structures can produce highly scalable backend systems.