Design Twitter

This is a straightforward approach where we simulate the process directly. For getNewsFeed, we gather all tweets from the user and the users they follow into a single list, sort this list by time, and then take the 10 most recent ones.

• Maintain a map userFollows for follow/unfollow relationships (Map<Integer, Set<Integer>>).
• Maintain a map userTweets to store a list of Tweet objects for each user (Map<Integer, List<Tweet>>). A Tweet object contains its ID and a timestamp.
• Use a global, static, incrementing timestamp for each new tweet to ensure chronological order.
• For getNewsFeed(userId):
  1. Create an empty list candidateTweets.
  2. Add all of userId's own tweets to candidateTweets.
  3. For each followeeId that userId follows, add all of their tweets to candidateTweets.
  4. Sort candidateTweets based on timestamp in descending order.
  5. Return the IDs of the first 10 tweets in the sorted list.

We use a Map to store follow relationships (userId -> Set<followeeId>) and another Map to store each user's tweets (userId -> List<Tweet>). A global timestamp is used to record the post time of each tweet, ensuring chronological order. postTweet adds a new tweet with the current timestamp to the user's tweet list. follow and unfollow simply update the follow-relationship map. The main logic is in getNewsFeed. It first identifies all relevant users (the user themselves and their followees). It then iterates through these users, collecting all their tweets into a temporary list. This list is then sorted in descending order based on the tweet's timestamp. Finally, the IDs of the first 10 tweets from the sorted list are returned.

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;
        public Tweet(int id, int time) {
            this.id = id;
            this.time = time;
        }
    }

    public Twitter() {
        userFollows = new HashMap<>();
        userTweets = new HashMap<>();
    }
    
    public void postTweet(int userId, int tweetId) {
        userTweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new Tweet(tweetId, timestamp++));
    }
    
    public List<Integer> getNewsFeed(int userId) {
        List<Tweet> allTweets = new ArrayList<>();
        
        // Add user's own tweets
        if (userTweets.containsKey(userId)) {
            allTweets.addAll(userTweets.get(userId));
        }
        
        // Add followees' tweets
        Set<Integer> followees = userFollows.get(userId);
        if (followees != null) {
            for (int followeeId : followees) {
                if (userTweets.containsKey(followeeId)) {
                    allTweets.addAll(userTweets.get(followeeId));
                }
            }
        }
        
        // Sort all collected tweets by time descending
        allTweets.sort((a, b) -> b.time - a.time);
        
        List<Integer> newsFeed = new ArrayList<>();
        for (int i = 0; i < Math.min(10, allTweets.size()); i++) {
            newsFeed.add(allTweets.get(i).id);
        }
        
        return newsFeed;
    }
    
    public void follow(int followerId, int followeeId) {
        userFollows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }
    
    public void unfollow(int followerId, int followeeId) {
        if (userFollows.containsKey(followerId) && followerId != followeeId) {
            userFollows.get(followerId).remove(followeeId);
        }
    }
}