My code:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
public class Twitter {
private long timestamp = 0;
private HashMap<Integer, User> map;
private class Tweet {
int tweetId;
int userId;
long ts;
Tweet next;
Tweet (int tweetId, int userId) {
this.tweetId = tweetId;
this.userId = userId;
this.ts = timestamp;
timestamp++;
}
}
private class User {
Set<Integer> following;
int userId;
Tweet head;
User (int userId) {
this.userId = userId;
following = new HashSet<Integer>();
following.add(userId);
head = null;
}
void follow(int userId) {
following.add(userId);
}
void unfollow(int userId) {
if (this.userId == userId) {
return;
}
following.remove(userId);
}
void post(Tweet t) {
t.next = head;
head = t;
}
}
/** Initialize your data structure here. */
public Twitter() {
map = new HashMap<Integer, User>();
}
/** Compose a new tweet. */
public void postTweet(int userId, int tweetId) {
if (!map.containsKey(userId)) {
map.put(userId, new User(userId));
}
map.get(userId).post(new Tweet(tweetId, 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. */
public List<Integer> getNewsFeed(int userId) {
List<Integer> ret = new ArrayList<Integer>();
if (!map.containsKey(userId)) {
return ret;
}
PriorityQueue<Tweet> pq = new PriorityQueue<Tweet>(10, new Comparator<Tweet>() {
public int compare(Tweet t1, Tweet t2) {
return (int) (t2.ts - t1.ts);
}
});
for (Integer uId : map.get(userId).following) {
User user = map.get(uId);
if (user.head != null) {
pq.offer(user.head);
}
}
int n = 10;
while (!pq.isEmpty() && n > 0) {
Tweet t = pq.poll();
ret.add(t.tweetId);
if (t.next != null) {
pq.offer(t.next);
}
n--;
}
return ret;
}
/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
public void follow(int followerId, int followeeId) {
if (!map.containsKey(followerId)) {
map.put(followerId, new User(followerId));
}
if (!map.containsKey(followeeId)) {
map.put(followeeId, new User(followeeId));
}
map.get(followerId).follow(followeeId);
}
/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
public void unfollow(int followerId, int followeeId) {
if (!map.containsKey(followerId)) {
map.put(followerId, new User(followerId));
}
if (!map.containsKey(followeeId)) {
map.put(followeeId, new User(followeeId));
}
map.get(followerId).unfollow(followeeId);
}
}
/**
* Your Twitter object will be instantiated and called as such:
* Twitter obj = new Twitter();
* obj.postTweet(userId,tweetId);
* List<Integer> param_2 = obj.getNewsFeed(userId);
* obj.follow(followerId,followeeId);
* obj.unfollow(followerId,followeeId);
*/
reference：
https://discuss.leetcode.com/topic/48100/java-oo-design-with-most-efficient-function-getnewsfeed/3
这道题目还是很有意思的。可惜一开始想快点做，没好好设计。
结果后面越来越乱，只能看答案了。
我的最大的设计问题在于。
tweet 到底怎么存？怎么推送？
我的设计是，每个用户都一个一个列表，包含所有关注这个用户的其他用户（包括他自己）。 然后我每次发Tweet,就给这个列表里面所有的用户的 tweet 集合里，插入这个tweet，放在头部。
这样的话，我每次要读一个用户的 前十个tweet，就很快。
即使，用户A不关注用户B了，我们也可以在遍历的时候，判断tweet 的userId 是否还在该用户关注的用户ID中，如果不是，就跳过。
看似正常的逻辑，存在一个很大的漏洞。
就是，晚来的用户，关注用户A，无法读到用户A之前发的Tweet !!!!
所以， tweet 必须存在sender下。然后receiver 根据自己的关注列表，去把这些 tweet 读过来。
问题来了？我只需要前十个，那么我关注了那么多用户，如何选择前十个最新的tweet呢？
给 Tweet 加 timestamp.
那么，每个用户就拥有一个 List<Tweet>
假设我关注了 k 个用户。就有 k 个 List<Tweet>
然后，我可以按照 merge K sorted list 的思想，
拿出前十个。
具体思路就是这样。
答案设计的很好。
那么，在现实生活中，该如何设计一个 Twitter呢？
好好思考下。
Anyway, Good luck, Richardo! -- 09/22/2016
