資訊專欄INFORMATION COLUMN
摘要：首先建立按時(shí)間戳從大到小排列的，找到中的，出其中在中存在的，把每一個(gè)的推特鏈表放入，再?gòu)闹腥☆^十條推特的放入結(jié)果數(shù)組。
Design Twitter Note
建立兩個(gè)HashMap，一個(gè)存user，一個(gè)存tweets。以及整型的時(shí)間戳timestamp。
user的k-v pair是userId-follower_set，tweets的k-v pair是userId-tweets_linkedlist，tweets屬于Tweet類，包含time和id兩個(gè)參數(shù)。
postTweet(userId, tweetId):
首先，對(duì)于發(fā)推的主體，user，要存放在userMap中，而且user要follow自己，所以，userMap.get(userId).add(userId);
然后，在tweets中找到key值userId，將該用戶所有推特內(nèi)容放入值域的哈希表中。
getNewsFeed(userId):
首先建立按時(shí)間戳從大到小排列的PriorityQueue，找到userMap中的userId，filter出其中在tweet中存在的follower，把每一個(gè)follower的推特鏈表放入PriorityQueue，再?gòu)腜riorityQueue中取頭十條推特的id放入結(jié)果數(shù)組。
follow(followerId, followeeId):
將followeeId加入userMap中的followerId鍵值。
unfollow(followId, followeeId):
將followeeId從userMap中的followerId鍵值里刪除。
Solutionpublic class Twitter {
Map> userMap = new HashMap<>();
Map> tweets = new HashMap<>();
int timestamp = 0;
class Tweet {
int time;
int id;
Tweet(int time, int id) {
this.time = time;
this.id = id;
}
}
public void postTweet(int userId, int tweetId) {
if (!userMap.containsKey(userId)) userMap.put(userId, new HashSet<>());
userMap.get(userId).add(userId);
if (!tweets.containsKey(userId)) tweets.put(userId, new LinkedList<>());
tweets.get(userId).addFirst(new Tweet(timestamp++, tweetId));
}
public List getNewsFeed(int userId) {
if (!userMap.containsKey(userId)) return new LinkedList<>();
PriorityQueue feed = new PriorityQueue<>((t1, t2) -> t2.time-t1.time);
userMap.get(userId).stream().filter(f -> tweets.containsKey(f))
.forEach(f -> tweets.get(f).forEach(feed::add));
List res = new LinkedList<>();
while (feed.size() > 0 && res.size() < 10) res.add(feed.poll().id);
return res;
}
public void follow(int followerId, int followeeId) {
if (!userMap.containsKey(followerId)) userMap.put(followerId, new HashSet<>());
userMap.get(followerId).add(followeeId);
}
public void unfollow(int followerId, int followeeId) {
if (userMap.containsKey(followerId) && followeeId != followerId) userMap.get(followerId).remove(followeeId);
}
}
Mini Twitter
Problem
Implement a simple twitter. Support the following method:
postTweet(user_id, tweet_text). Post a tweet.
getTimeline(user_id). Get the given user"s most recently 10 tweets posted by himself, order by timestamp from most recent to least recent.
getNewsFeed(user_id). Get the given user"s most recently 10 tweets in his news feed (posted by his friends and himself). Order by timestamp from most recent to least recent.
follow(from_user_id, to_user_id). from_user_id followed to_user_id.
unfollow(from_user_id, to_user_id). from_user_id unfollowed to to_user_id.
postTweet(1, "LintCode is Good!!!") -->> 1 getNewsFeed(1) -->> [1] getTimeline(1) -->> [1] follow(2, 1) getNewsFeed(2) -->> [1] unfollow(2, 1) getNewsFeed(2) -->> []Note
設(shè)計(jì)一個(gè)mini Twitter，剛放出來的幾道系統(tǒng)設(shè)計(jì)題里，這道題才算是關(guān)于設(shè)計(jì)的題目。
要實(shí)現(xiàn)這么五個(gè)功能：
發(fā)推：需要用戶ID，推特內(nèi)容，該推特的時(shí)間戳； 時(shí)間線：需要用戶ID，該用戶的推特集，每條推特的時(shí)間戳，比較器； 新鮮事：需要用戶ID，好友ID集合，選定用戶群（用戶ID和所有好友ID）的推特集（選定用戶的推特集，時(shí)間戳），比較器； 關(guān)注：需要用戶ID，被關(guān)注用戶ID，好友ID集合； 取關(guān)：需要用戶ID，被關(guān)注用戶ID，好友ID集合；
以上，根據(jù)功能的要求，確定相關(guān)變量。然后選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu):
已經(jīng)給出的：Tweet(user_id, text, id, create())，
沒有給出但是需要的：時(shí)間戳order，帶時(shí)間戳的推特Node，推特集，所有推特集users_tweets，好友集friends，整個(gè)系統(tǒng)MiniTwitter，
然后，分析一下具體對(duì)象之間的邏輯關(guān)系：
Node: 包含Tweet和order，構(gòu)造Node類；
users_tweets: 包含user_id，和對(duì)應(yīng)id的推特集List
friends: 包含user_id，每個(gè)id對(duì)應(yīng)一個(gè)好友集Map
這樣就很清楚了，我們需要建立一個(gè)包含Tweet和Order的Node類，同時(shí)聲明兩個(gè)全局變量users_tweets和friends。
然后考慮要求實(shí)現(xiàn)的功能。
發(fā)推，要用給出的Tweet.create(user_id, tweet_text)函數(shù)，然后將集成Tweet和order的Node和對(duì)應(yīng)的user_id放入users_tweets；
時(shí)間線，需要從users_tweets中按照Order取出對(duì)應(yīng)user_id的后10個(gè)Node，再取出Node.tweet放入結(jié)果數(shù)組List
新鮮事，需要查看user_id的好友列表，將包括自己的每個(gè)人的后10個(gè)Node放入List
所以，order也要聲明為全局變量。
繼續(xù)，關(guān)注好友，添加或查找from_user_id作為friends中的key值，然后對(duì)這個(gè)key值對(duì)應(yīng)的value，也就是Map
取關(guān)好友，和關(guān)注好友相同的操作，先從friend中get的from_user_id的key值，再remove對(duì)應(yīng)Map中to_user_id的pair即可。
下面討論以上功能實(shí)現(xiàn)需要增加的細(xì)節(jié)。首先，取出前十個(gè)Node，取出后十個(gè)Node，需要建立兩個(gè)函數(shù)getFirstTen()和getLastTen()，對(duì)List
最后，在功能函數(shù)的前面，進(jìn)行MiniTweeter()的初始化。
結(jié)束~
public class MiniTwitter {
class Node {
public int order;
public Tweet tweet;
public Node(int order, Tweet tweet) {
this.order = order;
this.tweet = tweet;
}
}
class SortByOrder implements Comparator {
public int compare(Object obj1,Object obj2) {
Node node1 = (Node) obj1;
Node node2 = (Node) obj2;
if (node1.order < node2.order)
return 1;
else
return -1;
}
}
private Map> friends;
private Map> users_tweets;
private int order;
public List getLastTen(List temp) {
int last = 10;
if (temp.size() < 10)
last = temp.size();
return temp.subList(temp.size() - last, temp.size());
}
public List getFirstTen(List temp) {
int last = 10;
if (temp.size() < 10)
last = temp.size();
return temp.subList(0, last);
}
public MiniTwitter() {
// initialize your data structure here.
this.friends = new HashMap>();
this.users_tweets = new HashMap>();
this.order = 0;
}
// @param user_id an integer
// @param tweet a string
// return a tweet
public Tweet postTweet(int user_id, String text) {
Tweet tweet = Tweet.create(user_id, text);
if (!users_tweets.containsKey(user_id))
users_tweets.put(user_id, new ArrayList());
order += 1;
users_tweets.get(user_id).add(new Node(order, tweet));
return tweet;
}
// @param user_id an integer
// return a list of 10 new feeds recently
// and sort by timeline
public List getNewsFeed(int user_id) {
List temp = new ArrayList();
if (users_tweets.containsKey(user_id))
temp.addAll(getLastTen(users_tweets.get(user_id)));
if (friends.containsKey(user_id)) {
for (Map.Entry entry : friends.get(user_id).entrySet()) {
int user = entry.getKey();
if (users_tweets.containsKey(user))
temp.addAll(getLastTen(users_tweets.get(user)));
}
}
Collections.sort(temp, new SortByOrder());
List res = new ArrayList();
temp = getFirstTen(temp);
for (Node node : temp) {
res.add(node.tweet);
}
return res;
}
// @param user_id an integer
// return a list of 10 new posts recently
// and sort by timeline
public List getTimeline(int user_id) {
List temp = new ArrayList();
if (users_tweets.containsKey(user_id))
temp.addAll(getLastTen(users_tweets.get(user_id)));
Collections.sort(temp, new SortByOrder());
List res = new ArrayList();
temp = getFirstTen(temp);
for (Node node : temp)
res.add(node.tweet);
return res;
}
// @param from_user_id an integer
// @param to_user_id an integer
// from user_id follows to_user_id
public void follow(int from_user_id, int to_user_id) {
if (!friends.containsKey(from_user_id))
friends.put(from_user_id, new HashMap());
friends.get(from_user_id).put(to_user_id, true);
}
// @param from_user_id an integer
// @param to_user_id an integer
// from user_id unfollows to_user_id
public void unfollow(int from_user_id, int to_user_id) {
if (friends.containsKey(from_user_id))
friends.get(from_user_id).remove(to_user_id);
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65821.html
Problem For a web developer, it is very important to know how to design a web pages size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose l...
LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...
Problem Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) ...
Problem Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. Example Example:Given...
Problem Find the largest palindrome made from the product of two n-digit numbers. Since the result could be very large, you should return the largest palindrome mod 1337. Example Input: 2Output: 987Ex...
閱讀 3210·2021-11-24 10:30
閱讀 1324·2021-09-30 09:56
閱讀 2396·2021-09-07 10:20
閱讀 2609·2021-08-27 13:10
閱讀 712·2019-08-30 11:11
閱讀 2064·2019-08-29 12:13
閱讀 769·2019-08-26 12:24
閱讀 2911·2019-08-26 12:20
