LeetCode Design Twitter

原题链接在这里：https://leetcode.com/problems/design-twitter/description/

题目：

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:

postTweet(userId, tweetId): Compose a new tweet.
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.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

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

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 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.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

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

题解：

采用pull 模型.

这里从OO Design的角度去考虑, 需要建立 Tweet class和 User class.

Tweet class包含 id, 为了建立时间关系还有time 和根据时间出现的next.

User class 包含id, follow其他user的set, 以及自身的最新Tweet. 生成新的user时先follow自己. User class有follow, unfollow 和 post method.

在Twitter class中利用map来建立userId 和 user的mapping.

getNewsFeed时先把所有的following user的最新tweet放入maxHeap中. 提取最大时间的tweet, 再把这条tweet的next放入maxHeap中直到提取了10条tweet.

Time Complexity: postTweet, O(1). getNewsFeed, O(xlogx), x是followed 的数目. Heapify 用时x, 提取10条tweet 用时10*log(x).

follow, O(1). unfollow, O(1).

Space: O(n), n 时所有users数目, map大小.

AC Java:

  1 class Twitter {
  2     private Map<Integer, User> userMap;
  3 
  4     /** Initialize your data structure here. */
  5     public Twitter() {
  6         userMap = new HashMap<Integer, User>();
  7     }
  8     
  9     /** Compose a new tweet. */
 10     public void postTweet(int userId, int tweetId) {
 11         if(!userMap.containsKey(userId)){
 12             userMap.put(userId, new User(userId));
 13         }
 14         userMap.get(userId).post(tweetId);
 15     }
 16     
 17     /** 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. */
 18     public List<Integer> getNewsFeed(int userId) {
 19         List<Integer> res = new ArrayList<Integer>();
 20         if(!userMap.containsKey(userId)){
 21             return res;
 22         }
 23         
 24         Set<Integer> followed = userMap.get(userId).followed;
 25         PriorityQueue<Tweet> maxHeap = new PriorityQueue<Tweet>((a,b) -> (b.time - a.time));
 26         for(int Id : followed){
 27             Tweet tweetHead = userMap.get(Id).tweetHead;
 28             if(tweetHead != null){
 29                 maxHeap.add(tweetHead);
 30             }
 31         }
 32         
 33         int i = 0;
 34         while(!maxHeap.isEmpty() && i<10){
 35             Tweet t = maxHeap.poll();
 36             res.add(t.id);
 37             if(t.next != null){
 38                 maxHeap.add(t.next);
 39             }
 40             i++;
 41         }
 42         
 43         return res;
 44     }
 45     
 46     /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
 47     public void follow(int followerId, int followeeId) {
 48         if(!userMap.containsKey(followerId)){
 49             User u = new User(followerId);
 50             userMap.put(followerId, u);
 51         }
 52         if(!userMap.containsKey(followeeId)){
 53             User u = new User(followeeId);
 54             userMap.put(followeeId, u);
 55         }
 56         
 57         userMap.get(followerId).follow(followeeId);
 58     }
 59     
 60     /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
 61     public void unfollow(int followerId, int followeeId) {
 62         if(!userMap.containsKey(followerId) || followerId==followeeId){
 63             return;
 64         }
 65         userMap.get(followerId).unfollow(followeeId);
 66     }
 67 }
 68 
 69 // OO design for Tweet
 70 class Tweet{
 71     private static int timeStamp=0;
 72     
 73     public int id;
 74     public int time;
 75     public Tweet next;
 76 
 77     public Tweet(int id){
 78         this.id = id;
 79         time = timeStamp++;
 80         next = null;
 81     }
 82 }
 83 
 84 // OO design for User
 85 class User{
 86     public int id;
 87     public Set<Integer> followed;
 88     public Tweet tweetHead;
 89 
 90     public User(int id){
 91         this.id = id;
 92         followed = new HashSet<Integer>();
 93         followed.add(id);   //先follow自己
 94         tweetHead = null;
 95     }
 96 
 97     public void follow(int id){
 98         followed.add(id);
 99     }
100 
101     public void unfollow(int id){
102         followed.remove(id);
103     }
104 
105     public void post(int id){
106         Tweet tweet = new Tweet(id);
107         tweet.next = tweetHead;
108         tweetHead = tweet;
109     }
110 }
111 
112 /**
113  * Your Twitter object will be instantiated and called as such:
114  * Twitter obj = new Twitter();
115  * obj.postTweet(userId,tweetId);
116  * List<Integer> param_2 = obj.getNewsFeed(userId);
117  * obj.follow(followerId,followeeId);
118  * obj.unfollow(followerId,followeeId);
119  */