### 题目

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

1. postTweet(userId, tweetId): Compose a new tweet.
2. getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
3. follow(followerId, followeeId): Follower follows a followee.
4. unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).

// User 1's news feed should return a list with 1 tweet id -> [5].

// User 1 follows user 2.

// User 2 posts a new tweet (id = 6).

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.

// User 1 unfollows user 2.

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.


### 初步理解问题

1. 原创文章是每个作者的固定资产
2. 10篇最近提要是对其他作者原创文章的一种“引用”

### 主动推送流派

#### 代码

class Twitter {

time = 0;
users = new HashMap<Integer,User>();
}
public void postTweet(int userId, int tweetId) {
User u = confirmUser(userId);
Tweet t = new Tweet(userId,tweetId);
for (User follower : u.followers) { //更新粉丝摘要
}
}
public List<Integer> getNewsFeed(int userId) {
List<Integer> res = new ArrayList<>();
List<Tweet> removed = new ArrayList<>();
User u = confirmUser(userId);
for (int remain = MAX; !u.newsFeed.isEmpty() && remain > 0; remain--) {
Tweet t = u.newsFeed.poll();
}
for (Tweet t : removed) {
}
return res;
}
public void follow(int followerId, int followeeId) {
if (followerId == followeeId) { return; }
User follower = confirmUser(followerId);
User followee = confirmUser(followeeId);
if (!followee.followers.contains(follower)) {
for (Tweet t : followee.posts) { //更新摘要
}
}
}
public void unfollow(int followerId, int followeeId) {
if (followerId == followeeId) { return; }
User follower = confirmUser(followerId);
User followee = confirmUser(followeeId);
followee.followers.remove(follower);                 //更新粉丝列表
Iterator<Tweet> ite = follower.newsFeed.iterator();  //更新摘要
while (ite.hasNext()) {
Tweet t = ite.next();
if (t.userId == followee.userId) {
ite.remove();
}
}
}

/** ====================【私有成员】==================== */

//创建新用户
private User confirmUser(int userId) {
if (!users.containsKey(userId)) {
users.put(userId,new User(userId));
}
return users.get(userId);
}

private final int MAX = 10; //new feed的大小
private int time;
private Map<Integer,User> users;

private class User {
private int userId;
private PriorityQueue<Tweet> newsFeed;
private Set<User> followers;

private User(int userId) {
this.userId = userId;
newsFeed = new PriorityQueue<Tweet>();
followers = new HashSet<User>();
}
}
private class Tweet implements Comparable<Tweet> {
private int tweetId;
private int userId;
private int timeStamp;

private Tweet(int userId, int tweetId) {
this.userId = userId;
this.tweetId = tweetId;
this.timeStamp = ++time;
}
public int compareTo(Tweet t) {
return t.timeStamp - timeStamp; //时间戳越大，文章越新
}
}
}


### 懒惰的临时搜索流派

#### 代码

class Twitter {

time = 0;
users = new HashMap<Integer,User>();
}
public void postTweet(int userId, int tweetId) {
User u = confirmUser(userId);
Tweet t = new Tweet(userId,tweetId);
}
public List<Integer> getNewsFeed(int userId) {
User u = confirmUser(userId);
PriorityQueue<Tweet> candidates = new PriorityQueue<>();
Map<Integer,List<Tweet>> selected = new HashMap<>();
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer,PriorityQueue<Tweet>> idol : u.idols.entrySet()) { //先每个作者选一篇最新的
if (!idol.getValue().isEmpty()) {
}
}
for (int remain = MAX; remain > 0 && candidates.size() > 0; remain--) {
if (!u.idols.get(idolId).isEmpty()) {
}
selected.put(idolId,new ArrayList<Tweet>());
}
}
for (Map.Entry<Integer,List<Tweet>> selectedEntry : selected.entrySet()) { //把取出来的文章塞回作者的原创列表
int selectedIdol = selectedEntry.getKey();
for (Tweet t : selectedEntry.getValue()) {
}
}
for (Tweet candidate : candidates) { //把未入选的候选文章也还回去
}
return result;
}
//往粉丝的偶像列表里添加新偶像
public void follow(int followerId, int followeeId) {
User fans = confirmUser(followerId);
User idol = confirmUser(followeeId);
fans.idols.put(followeeId,idol.posts);
}
//从粉丝的偶像列表中删去某个偶像
public void unfollow(int followerId, int followeeId) {
if (followerId != followeeId) { //不能取关自己
User fans = confirmUser(followerId);
fans.idols.remove(followeeId);
}
}

/** ====================【私有成员】==================== */

//创建新用户
private User confirmUser(int userId) {
if (!users.containsKey(userId)) {
users.put(userId,new User(userId));
}
return users.get(userId);
}

private final int MAX = 10; //new feed的大小
private int time;
private Map<Integer,User> users;

private class User {
private int userId;
private PriorityQueue<Tweet> posts;
private Map<Integer,PriorityQueue<Tweet>> idols;

private User(int userId) {
this.userId = userId;
posts = new PriorityQueue<Tweet>();
idols = new HashMap<Integer,PriorityQueue<Tweet>>();
idols.put(this.userId,this.posts); //每个人首先都订阅自己的原创文章
}
}
private class Tweet implements Comparable<Tweet> {
private int tweetId;
private int userId;
private int timeStamp;

private Tweet(int userId, int tweetId) {
this.userId = userId;
this.tweetId = tweetId;
this.timeStamp = ++time;
}
public int compareTo(Tweet t) {
return t.timeStamp - timeStamp; //时间戳越大，文章越新
}
}

}


### 不用OO设计，也可以把问题抽象成模拟关系型数据库

#### 代码

class Twitter {
/**
* 构造函数
*/
userFollowersTable = new HashMap<Integer,Set<Integer>>();
userFollowingTable = new HashMap<Integer,Set<Integer>>();
}
/**
* 用户每发布一篇新文章，系统要做3件事，
*      1. 更新自己的原创文章列表
*      2. 更新自己的最近提要列表
*      3. 更新所有粉丝的最近提要列表
*
* 假设系统使用的userId和tweetId不会重复，我不做这方面的检查
*/
public void postTweet(int userId, int tweetId) {
Tweet tweet = new Tweet(tweetId);
//更新原创文章
updatePostsList(userId,tweet);
//更新最近提要
updateNewsFeedList(userId,tweet);
//更新所有粉丝的最近提要
if (userFollowersTable.containsKey(userId)) {
for (Integer follower : userFollowersTable.get(userId)) {
updateNewsFeedList(follower,tweet);
}
}
}
/**
* 返回news feed视图
*/
public List<Integer> getNewsFeed(int userId) {
List<Integer> res = new ArrayList<Integer>();
if (userNewsFeedTable.containsKey(userId)) {
for (Tweet tweet : userNewsFeedTable.get(userId)) {
}
}
return res;
}
/**
* 粉丝关注一个偶像，系统会尝试将这个偶像的文章推送到粉丝的最近提要列表
*/
public void follow(int followerId, int followeeId) {
boolean newFollowee = false;
//给粉丝更新偶像列表
if (!userFollowingTable.containsKey(followerId)) {
userFollowingTable.put(followerId,new HashSet<Integer>());
}
//给偶像更新粉丝列表
if (!userFollowersTable.containsKey(followeeId)) {
userFollowersTable.put(followeeId,new HashSet<Integer>());
}
//更新粉丝最近提要（重复关注已有偶像不更新）
if (newFollowee && userPostsTable.containsKey(followeeId)) {
for (Tweet tweet : userPostsTable.get(followeeId)) {
updateNewsFeedList(followerId, tweet);
}
}
}

/**
* 粉丝取关一个偶像，他的最近提要列表也会被更新
*/
public void unfollow(int followerId, int followeeId) {
boolean unfollowed = false;
//给粉丝更新偶像列表
if (userFollowingTable.containsKey(followerId)) {
unfollowed = userFollowingTable.get(followerId).remove(followeeId);
}
//给偶像更新粉丝列表
if (userFollowersTable.containsKey(followeeId)) {
userFollowersTable.get(followeeId).remove(followerId);
}
if (unfollowed) {
//先清空所有最近提要
//重新添加粉丝自己的原创文章
if (userPostsTable.containsKey(followerId)) {
for (Tweet tweet : userPostsTable.get(followerId)) {
updateNewsFeedList(followerId,tweet);
}
}
//重新添加所有偶像的文章
if (userFollowingTable.containsKey(followerId)) {
for (Integer followee : userFollowingTable.get(followerId)) {
if (userPostsTable.containsKey(followee)) {
for (Tweet tweet : userPostsTable.get(followee)) {
updateNewsFeedList(followerId,tweet);
}
}
}
}
}
}

/*==================== 【私有成员】 =======================*/

private final int MAX = 10;                                     //最近提要最大文章数

//模拟关系型数据库的映射表
private Map<Integer,Set<Integer>> userFollowersTable;           //用户粉丝列表的集合（去重）
private Map<Integer,Set<Integer>> userFollowingTable;           //用户关注对象集合（去重）

//更新不按时间戳排序的原创文章列表
private void updatePostsList(int userId, Tweet tweet) {
if (userPostsTable.containsKey(userId) && !userPostsTable.get(userId).contains(tweet)) { //不重复发布同一篇文章
} else {
}
}
//更新按时间戳排序的最近提要列表
private void updateNewsFeedList(int userId, Tweet tweet) {
if (userNewsFeedTable.containsKey(userId)) {
if (!newsFeed.contains(tweet)) {    //已经有的文章不重新添加
boolean updated = false;
for (int i = 0; i < newsFeed.size(); i++) {
if (newsFeed.get(i).compareTo(tweet) < 0) { newsFeed.add(i,tweet); updated = true; break; } // 时间戳大的在前
}
if (newsFeed.size() > MAX) { newsFeed.removeLast(); }
}
} else {
}
}
/**
* 带时间戳的文章对象
*/
private class Tweet implements Comparable<Tweet> {
private int tweetId;
private long timeStamp; //每篇文章都有个时间戳

private Tweet(int tweetId) {
this.tweetId = tweetId;
timeStamp = System.nanoTime();
}
//假设tweetId具有唯一性。区分不同的Tweet个体不依赖时间戳。时间戳仅用来按时间排序。
public boolean equals(Object another) {
return this.tweetId == ((Tweet)another).tweetId;
}
private int hash = -1;
public int hashCode() {
if (hash < 0) { //惰性初始化
hash = tweetId;
}
return hash;
}
//以时间戳降序排序，时间戳相同以id升序排序（时间戳越大，文章越新）
public int compareTo(Tweet another) {
if (this.timeStamp != another.timeStamp) {
return (int) (this.timeStamp - another.timeStamp);
} else {
return this.tweetId - another.tweetId;
}
}
public String toString() {
return "ID = " + tweetId + ",  Time Stamp = " + timeStamp;
}
}

/** ====================【单元测试专用函数】====================

//查看某个用户所有的原创文章
private List<Integer> getPosts(int userId) {
List<Integer> res = new ArrayList<>();
if (userPostsTable.containsKey(userId)) {
for (Tweet tweet : userPostsTable.get(userId)) {
}
}
return res;
}
//打印整个数据库
private void printDataBase() {
//原创文章表
System.out.println("\n>>> User-Posts Table: ");
System.out.println(userPostsTable);
//新闻提要表
System.out.println("\n>>> User-News Feed Table: ");
System.out.println(userNewsFeedTable);
//关注表
System.out.println("\n>>> User-Following Table: ");
System.out.println(userFollowingTable);
//被关注表
System.out.println("\n>>> User-Followers Table: ");
System.out.println(userFollowersTable);
}
===========================================================*/
}

/**