Design Twitter

Examples:

Input: Twitter twitter = new Twitter(); twitter.postTweet(1, 5); twitter.postTweet(1, 2); twitter.follow(1, 2); twitter.postTweet(2, 6); twitter.postTweet(1, 1); twitter.getNewsFeed(1); twitter.unfollow(1, 2); twitter.getNewsFeed(1);

Output: [[1, 1], [2, 6], [1, 2], [1, 5]]

Explanation: The news feed for user 1 should return a list of the 10 most recent tweet ids in the order they were posted, including tweets from users they follow.

Solutions

Hash Map and Priority Queue

Time: O(1) for postTweet, follow, and unfollow, O(n log n) for getNewsFeedSpace: O(n)

The provided solution utilizes a hash map to store tweets and a separate hash map to store follow relationships. The postTweet method simply adds a new tweet to the tweets map. The getNewsFeed method iterates over all tweets, adding those from the user and their followees to the news feed, then sorts and returns the 10 most recent tweets. The follow and unfollow methods update the follow map accordingly.


public
class Twitter {
  
  private int time;
  
  private Map<Integer, Tweet> tweetsMap;
  
  private Map<Integer, Set<Integer>> followMap;
  
  public Twitter() {
    time = 0;
    tweetsMap = new HashMap<>();
    followMap = new HashMap<>();
  }
  
  public void postTweet(int userId, int tweetId) {
    tweetsMap.put(tweetId, new Tweet(userId, time++));
  }
  
  public List<Integer> getNewsFeed(int userId) {
    List<Integer> newsFeed = new ArrayList<>();
    for (Tweet tweet : tweetsMap.values()) {
      if (tweet.userId == userId || followMap.containsKey(userId) && followMap.get(userId).contains(tweet.userId)) {
        newsFeed.add(tweet.tweetId);
      }
    }
    newsFeed.sort((a, b) -> b.time - a.time);
    return newsFeed.subList(0, Math.min(10, newsFeed.size()));
  }
  
  public void follow(int followerId, int followeeId) {
    followMap.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
  }
  
  public void unfollow(int followerId, int followeeId) {
    if (followMap.containsKey(followerId)) {
      followMap.get(followerId).remove(followeeId);
    }
  }
  
  private
  class Tweet {
    int userId;
    int tweetId;
    int time;
    Tweet(int userId, int time) {
      this.userId = userId;
      this.tweetId = tweetId;
      this.time = time;
    }
  }
}

Constraints:

Examples:

Solutions

Hash Map and Priority Queue

Follow-up: