Medium

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.

Examples

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]]

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 * 10^4 calls will be made in total.

Hash Maps and Max Heap

Approach

Use a global `timestamp` to order tweets. Use a hash map `followers` (userId -> set of followees). Use a hash map `tweets` (userId -> list of [timestamp, tweetId]). For `getNewsFeed`, get the list of users the given `userId` follows (including themselves). Collect the most recent tweet from each of these users and put them in a Max Heap (sorted by timestamp). Then, pop the most recent tweet, add it to the feed, and push the next most recent tweet from the same user into the heap. Repeat this up to 10 times to get the 10 most recent tweets overall.

Complexity Analysis

Time Complexity

O(k) for getNewsFeed

Space Complexity

O(N + T)

k is the number of users followed (max 10 items in heap). N is total users, T is total tweets. Note that using max heap algorithm avoids sorting all tweets which would be O(T log T).

Solution.java

1class Twitter {2    private int timestamp;3    private Map<Integer, Set<Integer>> followMap;4    private Map<Integer, List<int[]>> tweetMap; // [time, tweetId]5
6    public Twitter() {7        timestamp = 0;8        followMap = new HashMap<>();9        tweetMap = new HashMap<>();10    }11    12    public void postTweet(int userId, int tweetId) {13        if (!tweetMap.containsKey(userId)) {14            tweetMap.put(userId, new ArrayList<>());15        }16        tweetMap.get(userId).add(new int[]{timestamp++, tweetId});17    }18    19    public List<Integer> getNewsFeed(int userId) {20        List<Integer> res = new ArrayList<>();21        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]); // [time, tweetId, followeeId, tweetIndex]22        23        // Ensure user follows themself24        follow(userId, userId);25        26        Set<Integer> followees = followMap.get(userId);27        if (followees != null) {28            for (int followeeId : followees) {29                if (tweetMap.containsKey(followeeId)) {30                    List<int[]> tweets = tweetMap.get(followeeId);31                    int index = tweets.size() - 1;32                    int[] latestTweet = tweets.get(index);33                    maxHeap.offer(new int[]{latestTweet[0], latestTweet[1], followeeId, index});34                }35            }36        }37        38        while (!maxHeap.isEmpty() && res.size() < 10) {39            int[] current = maxHeap.poll();40            res.add(current[1]); // Add tweetId41            42            int followeeId = current[2];43            int index = current[3] - 1; // Previous tweet from same user44            45            if (index >= 0) {46                int[] nextTweet = tweetMap.get(followeeId).get(index);47                maxHeap.offer(new int[]{nextTweet[0], nextTweet[1], followeeId, index});48            }49        }50        return res;51    }52    53    public void follow(int followerId, int followeeId) {54        if (!followMap.containsKey(followerId)) {55            followMap.put(followerId, new HashSet<>());56        }57        followMap.get(followerId).add(followeeId);58    }59    60    public void unfollow(int followerId, int followeeId) {61        if (followMap.containsKey(followerId) && followerId != followeeId) {62            followMap.get(followerId).remove(followeeId);63        }64    }65}