设计Twitter的时间线功能

题目描述
设计一个类似Twitter的时间线功能，支持用户发布推文、关注/取消关注其他用户，以及获取用户首页的时间线（返回该用户和其关注者最近发布的10条推文，按时间逆序排列）。要求推文的发布、关注/取消关注操作高效，且获取时间线时能快速返回结果。

解题思路

1. 核心需求分析

   • 发布推文：用户可发布一条推文（包含内容和时间戳）。
   • 关注/取消关注：用户可动态关注或取消关注其他用户（无需互关）。
   • 获取时间线：返回用户及其关注者最近的10条推文，按时间从新到旧排列。

2. 关键挑战

   • 时间线需聚合多用户推文，并排序取前10条。若用户关注数巨大（如1000人），每次获取时间线时实时合并排序所有推文会非常慢。
   • 需平衡推文发布效率和时间线查询效率。

3. 设计思路

   • 推文存储：每个用户的推文用链表存储（按时间戳降序），新推文插入链表头部。
   • 关注关系：用哈希表维护用户的关注列表。
   • 时间线生成：
     • 方案1（实时合并）：获取时间线时，从用户及其所有关注者的推文链表中合并最新的10条（类似多路归并）。
     • 方案2（预聚合）：为每个用户维护一个时间线缓存（如优先队列），发布推文时主动推送至关注者的缓存。但取消关注或大量关注者时缓存更新复杂。
   • 权衡：Twitter早期采用实时合并（因关注者数较少），后期改用预聚合+缓存策略。本题聚焦实时合并方案。

详细实现步骤

1. 数据结构设计

   class Tweet:
       def __init__(self, tweet_id, timestamp):
           self.tweet_id = tweet_id
           self.timestamp = timestamp  # 全局递增时间戳
           self.next = None  # 链表指向下一条推文
   
   class User:
       def __init__(self, user_id):
           self.user_id = user_id
           self.followees = set()  # 关注的人（包括自己）
           self.tweet_head = None  # 推文链表头节点
   
           # 初始时关注自己，以便时间线包含自己的推文
           self.followees.add(user_id)
   
       def post_tweet(self, tweet_id, timestamp):
           """发布推文：插入链表头部"""
           new_tweet = Tweet(tweet_id, timestamp)
           new_tweet.next = self.tweet_head
           self.tweet_head = new_tweet
   
       def follow(self, followee_id):
           self.followees.add(followee_id)
   
       def unfollow(self, followee_id):
           if followee_id != self.user_id:  # 不允许取消关注自己
               self.followees.discard(followee_id)
   

2. 系统核心类

   class Twitter:
       def __init__(self):
           self.timestamp = 0  # 全局时间戳
           self.user_map = {}  # user_id -> User对象
   
       def _get_user(self, user_id):
           """获取用户，不存在时创建"""
           if user_id not in self.user_map:
               self.user_map[user_id] = User(user_id)
           return self.user_map[user_id]
   
       def postTweet(self, user_id, tweet_id):
           """发布推文"""
           user = self._get_user(user_id)
           self.timestamp += 1
           user.post_tweet(tweet_id, self.timestamp)
   
       def getNewsFeed(self, user_id):
           """获取时间线：合并用户及其关注者的最新推文"""
           if user_id not in self.user_map:
               return []
   
           user = self.user_map[user_id]
           # 用最大堆（优先队列）按时间戳合并推文
           heap = []
           for followee_id in user.followees:
               followee = self._get_user(followee_id)
               if followee.tweet_head:
                   # 堆中存储(-timestamp, tweet)实现最大堆
                   heapq.heappush(heap, (-followee.tweet_head.timestamp, followee.tweet_head))
   
           result = []
           while heap and len(result) < 10:
               _, tweet = heapq.heappop(heap)
               result.append(tweet.tweet_id)
               # 将该用户的下一条推文加入堆
               if tweet.next:
                   heapq.heappush(heap, (-tweet.next.timestamp, tweet.next))
           return result
   
       def follow(self, follower_id, followee_id):
           """关注操作"""
           follower = self._get_user(follower_id)
           follower.follow(followee_id)
   
       def unfollow(self, follower_id, followee_id):
           """取消关注"""
           if follower_id in self.user_map:
               self.user_map[follower_id].unfollow(followee_id)
   

3. 关键优化点

   • 推文链表：每个用户的推文按时间降序存储，避免获取时反转。
   • 多路归并：使用最大堆（优先队列）合并K个有序链表，每次取最晚的推文，保证时间复杂度为O(10 * logK)（K为关注者数）。
   • 关注自己：用户初始关注自己，简化时间线逻辑。

复杂度分析

• 发布推文：O(1)，链表头部插入。
• 关注/取消关注：O(1)，哈希表操作。
• 获取时间线：O(10 * logK)，其中K为关注者数。堆最多存储K条推文，每次取10条。

实际应用扩展

• 当用户关注量极大时，可引入推文分片、缓存预生成（如每5分钟更新一次时间线）等策略。
• 工业级系统还会考虑数据分库、读写分离、消息队列异步处理等架构优化。