Designing Twitter -LeetCode

 Requirements for Twitter System Design

Blank diagram: Lucidchart

1 Functional Requirements:

User Management

A user can create an account, login/logout.

Should be able to post new tweets (can be text, image, video etc).

Should be able to follow other users.

Should have a newsfeed feature consisting of tweets from the people the user is following.

Should be able to search tweets.


Tweets


A user can post a tweet (limited to 280 characters).

A user can delete their own tweet.

Tweets should have a unique ID, text content, timestamp, and author.


Timeline


Each user should be able to view their timeline (tweets from the users they follow, ordered by most recent first).

A user can also view their own tweets.


Likes & Retweets (Optional Enhancement)

A user can like/unlike a tweet.

A user can retweet a tweet.



 NonFunctional Requirements:

High availability with minimal latency.

Ths system should be scalable and efficient.


 Extended Requirements:

Metrices and analytics

Retweet functionality

Favorite tweets



Explanation

  • User Service: handles register/login/logout, profile, follow/unfollow

  • Tweet Service: handles posting/deleting tweets

  • Timeline Service: fetches all tweets from followed users and orders by timestamp

  • DB: relational schema with tables users, tweets, follows, likes, retweets


 Users (user_id PK)
      |
      |<----------+
      |           |
 Follows (follower_id, followee_id)

 Tweets (tweet_id PK, author_id FK)
      |
      +----- Likes (tweet_id FK, user_id FK)
      |
      +----- Retweets (retweet_id PK, original_tweet_id FK, user_id FK)

Question :-


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:


Input

["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"]

[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]

Output

[null, null, [5], null, null, [6, 5], null, [5]]


Explanation

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.

 


Constraints:


1 <= userId, followerId, followeeId <= 500

0 <= tweetId <= 104

All the tweets have unique IDs.

At most 3 * 104 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

A user cannot follow himself.



🧠 Step 1 — Understand the Problem

We need to design a mini Twitter with:

  • postTweet(userId, tweetId) → user posts a tweet

  • getNewsFeed(userId) → get the 10 most recent tweets from:

    • this user

    • users they follow

  • follow(followerId, followeeId)

  • unfollow(followerId, followeeId)

Constraints:

  • max 500 users

  • tweets have unique IDs

  • at most 3*10^4 operations

  • getNewsFeed should be most recent 10 tweets

🧠 Step 2 — Think About the Data We Need

We must track:

🗂 User Follow Relations

We must know which users a user follows
So, use a Map<Integer, Set<Integer>> followMap

  • followMap.get(1) = {2,3,4} → user 1 follows 2,3,4

🗂 Tweets

We must store tweets posted by each user and their time order
So, use a Map<Integer, List<Tweet>> tweetMap
where Tweet is a small class:    


🧠 Step 3 — How to Get Top 10 Most Recent Tweets

When getNewsFeed(userId) is called:

  • Collect all tweets from:

    • this user

    • all followees

  • Sort them by time descending

  • Pick first 10

Efficient approach:

  • Put them into a Max Heap (PriorityQueue) sorted by time

  • Pop 10 elements from the heap

🧠 Step 4 — How Follow & Unfollow Work

follow(a, b)

  • add b to followMap.get(a)

unfollow(a, b)

  • remove b from followMap.get(a)

Don’t allow a user to follow himself.

🧠 Step 5 — Write the Class Skeleton


class Twitter {

    public Twitter() {}

    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) {}

}


🧠 Step 6 — Implement Internals


import java.util.*;

class Twitter {

    private static class Tweet {
        int id;
        int time;
        Tweet(int id, int time) {
            this.id = id;
            this.time = time;
        }
    }

    private Map<Integer, Set<Integer>> followMap;   // follower -> set of followees
    private Map<Integer, List<Tweet>> tweetMap;     // userId -> list of tweets
    private int time;

    public Twitter() {
        followMap = new HashMap<>();
        tweetMap = new HashMap<>();
        time = 0;
    }
   
    public void postTweet(int userId, int tweetId) {
        tweetMap.putIfAbsent(userId, new ArrayList<>());
        tweetMap.get(userId).add(new Tweet(tweetId, time++));
    }
   
    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Tweet> maxHeap = new PriorityQueue<>((a, b) -> b.time - a.time);
       
        // Add own tweets
        if (tweetMap.containsKey(userId)) {
            maxHeap.addAll(tweetMap.get(userId));
        }
       
        // Add tweets from followees
        if (followMap.containsKey(userId)) {
            for (int followee : followMap.get(userId)) {
                if (tweetMap.containsKey(followee)) {
                    maxHeap.addAll(tweetMap.get(followee));
                }
            }
        }
       
        List<Integer> res = new ArrayList<>();
        int count = 0;
        while (!maxHeap.isEmpty() && count < 10) {
            res.add(maxHeap.poll().id);
            count++;
        }
        return res;
    }
   
    public void follow(int followerId, int followeeId) {
        if (followerId == followeeId) return; // can't follow self
        followMap.putIfAbsent(followerId, new HashSet<>());
        followMap.get(followerId).add(followeeId);
    }
   
    public void unfollow(int followerId, int followeeId) {
        if (followMap.containsKey(followerId)) {
            followMap.get(followerId).remove(followeeId);
        }
    }
}


Comments

Post a Comment

Popular posts from this blog

Two Sum II - Input Array Is Sorted

 Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order , find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space .   Example 1: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2]. Example 2: Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3]. Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1,...
Read more

Comparable Vs. Comparator in Java

  In Java , Comparable and Comparator both are interfaces used to sort objects. Comparable It defines  natural ordering  within a class. It is implemented  inside  the class being sorted. It uses the compareTo() method. It allows sorting  by one one . Comparable provides a  single sorting sequence . In other words, we can sort the collection on the basis of a single element such as id, name, and price. Comparable  affects the original class , i.e., the actual class is modified. Comparable is present in  java.lang  package. We can sort the list elements of Comparable type by  Collections.sort(List)  method. Only one compareTo() method can be implemented, restricting flexibility. Comparator It defines  custom sorting logic It is implemented  in a separate class  or using lambda expressions . It uses the compare() method. It allows sorting  by multiple criteria . The Comparator provides  multiple sorting...
Read more

Increasing Triplet Subsequence

 Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.   Example 1: Input: nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid. Example 2: Input: nums = [5,4,3,2,1] Output: false Explanation: No triplet exists. Example 3: Input: nums = [2,1,5,0,4,6] Output: true Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6. Brute Force : Failed for some testcase class Solution {     public boolean increasingTriplet ( int [] nums ) {         int n = nums . length ;         int i = 0 ;         int j =i+ 1 ;         int k =j+ 1 ;         while (i <n && j<n && k<n)         {         if (nums...
Read more