algoadvance

Leetcode 355. Design Twitter

Problem Statement

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and retrieve the 10 most recent tweet ids in the user’s news feed. Your design should support the following methods:

  1. postTweet(int userId, int tweetId): Compose a new tweet.
  2. getNewsFeed(int userId): Retrieve 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 themselves. Tweets must be ordered from most recent to least recent.
  3. follow(int followerId, int followeeId): Follower follows a followee. If the operation is invalid, it should be a no-op.
  4. unfollow(int followerId, int followeeId): Follower unfollows a followee. If the operation is invalid, it should be a no-op.

Clarifying Questions

  1. Capacity Constraints: Is there any limit on the number of users, follows, or tweets?
  2. Time Sensitivity: Should the system be optimized for more frequent operations (reads vs. writes)?
  3. Thread Safety: Will the system be used in a multi-threaded environment where thread safety is a concern?

Code

import java.util.*;

class Twitter {
    private static int timestamp = 0;
    private Map<Integer, Set<Integer>> userFollows;
    private Map<Integer, List<Tweet>> userTweets;

    private class Tweet {
        int id;
        int time;
        Tweet(int id) {
            this.id = id;
            this.time = Twitter.timestamp++;
        }
    }

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

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        userTweets.putIfAbsent(userId, new ArrayList<>());
        userFollows.putIfAbsent(userId, new HashSet<>());  // Ensure user exists in follows list even if they follow no one.
        userTweets.get(userId).add(new Tweet(tweetId));
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. */
    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);

        if (userTweets.containsKey(userId)) {
            pq.addAll(userTweets.get(userId));
        }

        if (userFollows.containsKey(userId)) {
            for (int followeeId : userFollows.get(userId)) {
                if (userTweets.containsKey(followeeId)) {
                    pq.addAll(userTweets.get(followeeId));
                }
            }
        }

        List<Integer> res = new ArrayList<>();
        int n = 0;
        while (!pq.isEmpty() && n < 10) {
            res.add(pq.poll().id);
            n++;
        }
        return res;
    }

    /** Follower follows a followee. */
    public void follow(int followerId, int followeeId) {
        userFollows.putIfAbsent(followerId, new HashSet<>());
        userFollows.get(followerId).add(followeeId);
    }

    /** Follower unfollows a followee. */
    public void unfollow(int followerId, int followeeId) {
        if (userFollows.containsKey(followerId) && followerId != followeeId) {
            userFollows.get(followerId).remove(followeeId);
        }
    }
}

Strategy

  1. Data Structures:
    • userFollows: A map where the key is userId and the value is a set of userIds that the user follows.
    • userTweets: A map where the key is userId and the value is a list of Tweet objects representing the tweets that the user has posted.
  2. Tweet Class:
    • Represents a tweet with an id and time-stamp.
  3. postTweet Method:
    • Adds the tweet to the user’s list of tweets and initializes lists/maps if the user doesn’t exist.
  4. getNewsFeed Method:
    • Use a max-heap to collect the 10 most recent tweets from the user and the users they follow.
  5. follow and unfollow Methods:
    • Adds/removes the follow relation in the userFollows map.

Time Complexity

  1. postTweet: (O(1))
  2. getNewsFeed: (O(N \log K)) where (N) is the total number of tweets from the user and their followees, and (K) is 10 (since we only need the top 10 tweets).
  3. follow: (O(1))
  4. unfollow: (O(1))

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI