Practice/Google/Design Twitter

Design Twitter

Object Oriented DesignMust

Problem

Design and implement a simplified social media feed system that supports core functionality similar to platforms like Twitter. Your system should allow users to create posts, establish follow relationships with other users, and retrieve a personalized feed showing the most recent posts from themselves and the people they follow.

The system needs to efficiently handle the creation of posts, management of follower relationships, and generation of personalized feeds that display content in reverse chronological order (newest first).

Requirements

1. Implement a post_message(user_id, message) method that creates a new post for a given user
2. Implement a follow(follower_id, followee_id) method that establishes a following relationship
3. Implement an unfollow(follower_id, followee_id) method that removes a following relationship
4. Implement a get_feed(user_id, count) method that returns the most recent posts visible to a user
5. A user's feed should include their own posts as well as posts from all users they follow
6. Posts should be returned in reverse chronological order (most recent first)
7. The feed should support limiting the number of posts returned
8. Each post should be uniquely identifiable and timestamped
9. A user cannot follow themselves (this should be handled gracefully)
10. Unfollowing someone who isn't followed should not cause an error

Constraints

• User IDs are positive integers
• Messages are non-empty strings with maximum length of 280 characters
• The system should efficiently handle up to 100,000 users
• Each user may follow up to 5,000 other users
• The system should support retrieving feeds with up to 100 posts efficiently
• Time complexity for posting should be O(1)
• Time complexity for follow/unfollow should be O(1)
• Time complexity for getting a feed should be O(N log N) where N is the total posts from followed users

Examples

Example 1: Basic posting and feed retrieval

` SocialFeed system = new SocialFeed() system.post_message(1, "Hello, world!") system.post_message(1, "Having a great day!") system.get_feed(1, 10)

Output: ["Having a great day!", "Hello, world!"] Explanation: User 1's feed contains their own posts in reverse chronological order `

Example 2: Following another user

` SocialFeed system = new SocialFeed() system.post_message(1, "User 1 post") system.post_message(2, "User 2 post") system.follow(1, 2) system.get_feed(1, 10)

Output: ["User 2 post", "User 1 post"] Explanation: User 1 follows User 2, so their feed includes posts from both users `

Example 3: Unfollowing and feed updates

` SocialFeed system = new SocialFeed() system.follow(1, 2) system.post_message(2, "Before unfollow") system.unfollow(1, 2) system.post_message(2, "After unfollow") system.get_feed(1, 10)

Output: ["Before unfollow"] Explanation: Posts created before unfollowing remain, but new posts after unfollowing don't appear `

Example 4: Feed with multiple follows

` SocialFeed system = new SocialFeed() system.post_message(1, "Post A") system.post_message(2, "Post B") system.post_message(3, "Post C") system.follow(1, 2) system.follow(1, 3) system.get_feed(1, 10)

Output: ["Post C", "Post B", "Post A"] Explanation: Feed aggregates posts from user 1, 2, and 3 in chronological order `