1 题目描述

设计一个简单的推特版本。支持用户发推，支持用户关注或取消关注其他用户，且用户可以在动态里看到最近的10条推文。

您的设计应支持如下几个方法：

a）postTweet(userId, tweetId)：发表新推文；

b）getNewsFeed(userId)：在用户动态里展示最近的10条推文id，动态里的每条推文须是用户自己发的或是其关注者发的，推文须按时间由近及远排序；

c）follow(followerId, followeeId)：关注；

d）unfollow(followerId, followeeId)：取消关注。

例子：

题目出处：

2 解决思路

动态的实现一般使用“拉模式”或者“推模式”，即用户可以看到的动态可以采用查询的时候直接计算（拉）也可以在用户的关注者发推的时候直接“推”到用户的动态列表。

本文使用“推模式”实现，如下是用到的几个数据结构：

a）tweets用来存放用户发表的推文；

b）feeds用来存放每个用户可以看到的动态；

c）fans用来存放用户的粉丝（关注者）列表。

接下来看一下几个方法的实现逻辑：

PostTweet：当用户发送一条推文时，tweets存一下该推文的id与时间，feeds把该动态append到末尾；

GetNewsFeed：从末尾开始遍历feeds，返回最近的10条推文id；

Follow：有用户a关注用户b，则把a放入b的fans列表，且把b的tweets推文并入a的feeds，因合并的两部分均是按时间升序排列的数组，所以避免使用常规排序算法，使用自写的merge函数可以加速合并；

Unfollow：用用户a取消关注b，则将a从b的fans列表移除，还要从a的feeds中移除b的tweets。

3 Golang实现代码

原文链接：

本文作者：磊磊落落的博客，原创授权发布