Design Twitter

Design Twitter is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the K-way Merge subpattern.

Problem statement

Implement a Twitter class that stores users' tweets and follow relationships. The constructor takes no arguments and initializes an empty service. A tweet is identified by its unique tweetId; tweets are ordered by the time their postTweet calls occur, with later calls being more recent.

postTweet(userId, tweetId) records a tweet for userId and returns nothing. follow(followerId, followeeId) makes followerId follow followeeId, while unfollow(followerId, followeeId) removes that relationship if it exists; both methods return nothing.

getNewsFeed(userId) returns a list containing up to the 10 most recent tweet IDs posted by userId or by any user currently followed by userId, ordered from newest to oldest. If no eligible tweets exist, return an empty list. The method does not change the stored state.

Example 1:

Input:

["Twitter", "postTweet", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[],[7,501],[7,502],[7],[7,12],[12,880],[7],[7,12],[7]]

Output:

[null,null,null,[502,501],null,null,[880,502,501],null,[502,501]]

Explanation: User 7 initially sees their two tweets. After following user 12, user 7 also sees tweet 880; unfollowing user 12 removes it from the feed.

Example 2:

Input:

["Twitter", "follow", "postTweet", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed", "unfollow", "getNewsFeed"] [[],[4,9],[9,31],[4,44],[4],[4,9],[4],[4,9],[22]]

Output:

[null,null,null,null,[44,31],null,[44],null,[]]

Explanation: A relationship created before either tweet is posted still allows user 4 to see user 9's tweet. The second unfollow is a no-op, and user 22 has no eligible tweets.

Example 3:

Input:

["Twitter", "postTweet", "follow", "postTweet", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[],[15,700],[3,15],[3,701],[3,15],[15,702],[3],[3,15],[3]]

Output:

[null,null,null,null,null,null,[702,701,700],null,[701]]

Explanation: User 3 follows user 15, and the repeated follow does not change the relationship. The first feed contains the three tweets in reverse posting order; after the unfollow, only user 3's tweet remains visible.

Constraints:

- The first operation is Twitter, and its argument list is empty. - 1 <= operations.length <= 10^5. - Every operation after the constructor is one of postTweet, getNewsFeed, follow, or unfollow. - userId, followerId, and followeeId are JSON integers. - tweetId is a JSON integer, and every tweetId is unique across all postTweet calls. - followerId != followeeId for every follow and unfollow call. - unfollow may name a relationship that does not currently exist; such a call is valid and has no effect.

Topics and companies

Topics: Design, Heap (Priority Queue), Hash Table, Data Stream.

How to practise Design Twitter on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in For a feed with F followed users and K <= 10 returned tweets: O(F + K log F). Posting and follow/unfollow operations are O(1) average. time and O(P + R + F), where P is the number of tweets, R is the number of follow relationships, and F is the number of users considered by one feed query. space.

Open Design Twitter in the code editor, or read the Design Twitter editorial for a worked solution with its approach and complexity analysis.

Where Design Twitter sits in the DSA pattern sheet

Problems related to Design Twitter

Other problems that use the same K-way Merge and Heap (Priority Queue) Patterns techniques:

Preparing this workspace.