LeetCode //C - 355. Design Twitter

355. Design Twitter

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 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<=10^4$
• All the tweets have unique IDs.
• At most $3\ast 10^4$ calls will be made to postTweet, getNewsFeed, follow, and unfollow.

From: LeetCode
Link: 355. Design Twitter

Solution:

Ideas:

• Sorting Tweets: The sorting step ensures that the tweets are ordered from the most recent to the least recent based on the timestamp. This is crucial for correctly generating the news feed.
• Efficiency: The sorting approach used here is simple but might not be the most efficient for larger datasets. In practice, more advanced data structures or algorithms could be used to optimize performance.
• Scalability: This implementation assumes a manageable number of users and tweets. For very large datasets, additional optimizations and considerations would be required.

Code:

#define MAX_USERS 500

typedef struct Tweet {
    int tweetId;
    int timestamp;
    struct Tweet *next;
} Tweet;

typedef struct User {
    int userId;
    Tweet *tweets;
    struct User **followees;
    int followeeCount;
} User;

typedef struct Twitter {
    User *users[MAX_USERS];
    int timestamp;
} Twitter;

Tweet* createTweet(int tweetId, int timestamp) {
    Tweet *newTweet = (Tweet*)malloc(sizeof(Tweet));
    newTweet->tweetId = tweetId;
    newTweet->timestamp = timestamp;
    newTweet->next = NULL;
    return newTweet;
}

User* createUser(int userId) {
    User *newUser = (User*)malloc(sizeof(User));
    newUser->userId = userId;
    newUser->tweets = NULL;
    newUser->followees = (User**)malloc(MAX_USERS * sizeof(User*));
    newUser->followeeCount = 0;
    return newUser;
}

Twitter* twitterCreate() {
    Twitter *twitter = (Twitter*)malloc(sizeof(Twitter));
    for (int i = 0; i < MAX_USERS; ++i) {
        twitter->users[i] = NULL;
    }
    twitter->timestamp = 0;
    return twitter;
}

void twitterPostTweet(Twitter* obj, int userId, int tweetId) {
    if (obj->users[userId] == NULL) {
        obj->users[userId] = createUser(userId);
    }
    
    Tweet *newTweet = createTweet(tweetId, obj->timestamp++);
    newTweet->next = obj->users[userId]->tweets;
    obj->users[userId]->tweets = newTweet;
}

int* twitterGetNewsFeed(Twitter* obj, int userId, int* retSize) {
    *retSize = 0;
    int *newsFeed = (int*)malloc(10 * sizeof(int));
    
    if (obj->users[userId] == NULL) {
        return newsFeed;
    }
    
    // Collect all relevant tweets
    Tweet *tweets[1000];
    int tweetCount = 0;
    
    // Add user's own tweets
    Tweet *current = obj->users[userId]->tweets;
    while (current != NULL && tweetCount < 1000) {
        tweets[tweetCount++] = current;
        current = current->next;
    }
    
    // Add tweets from followed users
    for (int i = 0; i < obj->users[userId]->followeeCount; ++i) {
        User *followee = obj->users[userId]->followees[i];
        current = followee->tweets;
        while (current != NULL && tweetCount < 1000) {
            tweets[tweetCount++] = current;
            current = current->next;
        }
    }
    
    // Sort the tweets by timestamp in descending order
    for (int i = 0; i < tweetCount - 1; ++i) {
        for (int j = i + 1; j < tweetCount; ++j) {
            if (tweets[i]->timestamp < tweets[j]->timestamp) {
                Tweet *temp = tweets[i];
                tweets[i] = tweets[j];
                tweets[j] = temp;
            }
        }
    }
    
    // Populate the newsFeed with the 10 most recent tweets
    for (int i = 0; i < tweetCount && i < 10; ++i) {
        newsFeed[i] = tweets[i]->tweetId;
    }
    
    *retSize = (tweetCount < 10) ? tweetCount : 10;
    
    return newsFeed;
}

void twitterFollow(Twitter* obj, int followerId, int followeeId) {
    if (obj->users[followerId] == NULL) {
        obj->users[followerId] = createUser(followerId);
    }
    if (obj->users[followeeId] == NULL) {
        obj->users[followeeId] = createUser(followeeId);
    }
    
    User *follower = obj->users[followerId];
    User *followee = obj->users[followeeId];
    
    for (int i = 0; i < follower->followeeCount; ++i) {
        if (follower->followees[i] == followee) {
            return; // Already following
        }
    }
    
    follower->followees[follower->followeeCount++] = followee;
}

void twitterUnfollow(Twitter* obj, int followerId, int followeeId) {
    if (obj->users[followerId] == NULL) return;
    
    User *follower = obj->users[followerId];
    for (int i = 0; i < follower->followeeCount; ++i) {
        if (follower->followees[i]->userId == followeeId) {
            follower->followees[i] = follower->followees[follower->followeeCount - 1];
            follower->followeeCount--;
            return;
        }
    }
}

void twitterFree(Twitter* obj) {
    for (int i = 0; i < MAX_USERS; ++i) {
        if (obj->users[i] != NULL) {
            User *user = obj->users[i];
            Tweet *tweet = user->tweets;
            while (tweet != NULL) {
                Tweet *temp = tweet;
                tweet = tweet->next;
                free(temp);
            }
            free(user->followees);
            free(user);
        }
    }
    free(obj);
}

/**
 * Your Twitter struct will be instantiated and called as such:
 * Twitter* obj = twitterCreate();
 * twitterPostTweet(obj, userId, tweetId);
 
 * int* param_2 = twitterGetNewsFeed(obj, userId, retSize);
 
 * twitterFollow(obj, followerId, followeeId);
 
 * twitterUnfollow(obj, followerId, followeeId);
 
 * twitterFree(obj);
*/