摘要:首先建立按时间戳从大到小排列的,找到中的,出其中在中存在的,把每一个的推特链表放入,再从中取头十条推特的放入结果数组。
Design Twitter Note
建立两个HashMap,一个存user,一个存tweets。以及整型的时间戳timestamp。
user的k-v pair是userId-follower_set,tweets的k-v pair是userId-tweets_linkedlist,tweets属于Tweet类,包含time和id两个参数。
postTweet(userId, tweetId):
首先,对于发推的主体,user,要存放在userMap中,而且user要follow自己,所以,userMap.get(userId).add(userId);
然后,在tweets中找到key值userId,将该用户所有推特内容放入值域的哈希表中。
getNewsFeed(userId):
首先建立按时间戳从大到小排列的PriorityQueue,找到userMap中的userId,filter出其中在tweet中存在的follower,把每一个follower的推特链表放入PriorityQueue,再从PriorityQueue中取头十条推特的id放入结果数组。
follow(followerId, followeeId):
将followeeId加入userMap中的followerId键值。
unfollow(followId, followeeId):
将followeeId从userMap中的followerId键值里删除。
Solutionpublic class Twitter { MapMini Twitter Problem> 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); } }
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
设计一个mini Twitter,刚放出来的几道系统设计题里,这道题才算是关于设计的题目。
要实现这么五个功能:
发推:需要用户ID,推特内容,该推特的时间戳; 时间线:需要用户ID,该用户的推特集,每条推特的时间戳,比较器; 新鲜事:需要用户ID,好友ID集合,选定用户群(用户ID和所有好友ID)的推特集(选定用户的推特集,时间戳),比较器; 关注:需要用户ID,被关注用户ID,好友ID集合; 取关:需要用户ID,被关注用户ID,好友ID集合;
以上,根据功能的要求,确定相关变量。然后选择适当的数据结构:
已经给出的:Tweet(user_id, text, id, create()),
没有给出但是需要的:时间戳order,带时间戳的推特Node,推特集,所有推特集users_tweets,好友集friends,整个系统MiniTwitter,
然后,分析一下具体对象之间的逻辑关系:
Node: 包含Tweet和order,构造Node类;
users_tweets: 包含user_id,和对应id的推特集List
friends: 包含user_id,每个id对应一个好友集Map
这样就很清楚了,我们需要建立一个包含Tweet和Order的Node类,同时声明两个全局变量users_tweets和friends。
然后考虑要求实现的功能。
发推,要用给出的Tweet.create(user_id, tweet_text)函数,然后将集成Tweet和order的Node和对应的user_id放入users_tweets;
时间线,需要从users_tweets中按照Order取出对应user_id的后10个Node,再取出Node.tweet放入结果数组List
新鲜事,需要查看user_id的好友列表,将包括自己的每个人的后10个Node放入List
所以,order也要声明为全局变量。
继续,关注好友,添加或查找from_user_id作为friends中的key值,然后对这个key值对应的value,也就是Map
取关好友,和关注好友相同的操作,先从friend中get的from_user_id的key值,再remove对应Map中to_user_id的pair即可。
下面讨论以上功能实现需要增加的细节。首先,取出前十个Node,取出后十个Node,需要建立两个函数getFirstTen()和getLastTen(),对List
最后,在功能函数的前面,进行MiniTweeter()的初始化。
结束~
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); } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.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...
阅读 3169·2021-11-24 10:30
阅读 1294·2021-09-30 09:56
阅读 2342·2021-09-07 10:20
阅读 2553·2021-08-27 13:10
阅读 676·2019-08-30 11:11
阅读 2034·2019-08-29 12:13
阅读 741·2019-08-26 12:24
阅读 2814·2019-08-26 12:20