Design Twitter

Design Twitter

What is this problem about?

The Design Twitter interview question asks you to build a simplified version of a social media platform. You need to implement core features: posting a tweet, following or unfollowing other users, and retrieving a user's news feed. The news feed should consist of the 10 most recent tweets from the user and the people they follow, sorted from newest to oldest.

Why is this asked in interviews?

This is one of the most popular design questions at companies like Apple, Uber, and Meta. It tests your ability to handle complex relational data and perform efficient "Top K" merging. It evaluations your proficiency with the heap interview pattern for merging multiple sorted streams and the hash table design pattern for managing user relationships and tweet history. It’s a perfect bridge between basic data structures and high-level system design.

Algorithmic pattern used

This problem uses Hash Tables and a Max-Heap (Priority Queue).

1. Storage: Use a Map<Integer, Set<Integer>> to track followers and a Map<Integer, List<Tweet>> to store tweets for each user.
2. News Feed: To get the top 10 tweets, retrieve the tweet lists of the user and everyone they follow. Use a Priority Queue to perform a $K$-way merge of these sorted lists (by timestamp), similar to merging $K$ sorted linked lists.

Example explanation

1. postTweet(User 1, Tweet 101): User 1's list now has Tweet 101.
2. follow(User 1, User 2): User 1 now follows User 2.
3. postTweet(User 2, Tweet 102): User 2's list has Tweet 102.
4. getNewsFeed(User 1): The system looks at User 1 and User 2's tweets. Tweet 102 was posted later than 101. Result: [102, 101].

Common mistakes candidates make

• Slow Sorting: Fetching all tweets from all followed users and sorting the entire combined list ($O(N \log N)$) instead of using a Heap ($O(K \log F)$, where $F$ is followers).
• Concurrency: Not considering how to handle very large follower counts (the "Celebrity Problem"), though this is usually for the "System Design" discussion rather than the coding part.
• Timestamping: Forgetting to assign a global, incrementing ID or timestamp to each tweet to maintain a consistent chronological order.

Interview preparation tip

Practice the "$K$-way Merge" pattern using a Heap. It's the standard solution for merging multiple sorted arrays or lists into a single sorted output, which is the heart of the news feed logic.