资讯专栏INFORMATION COLUMN

[LeetCode/LintCode] Design Twitter/Mini Twitter

honmaple / 3305人阅读

摘要:首先建立按时间戳从大到小排列的,找到中的,出其中在中存在的,把每一个的推特链表放入,再从中取头十条推特的放入结果数组。

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键值里删除。

Solution
public 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.

Example
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: 包含Tweetorder,构造Node类;
users_tweets: 包含user_id,和对应id的推特集List,使用Map>的数据结构;
friends: 包含user_id,每个id对应一个好友集Map(即Map()),使用Map>的数据结构。

这样就很清楚了,我们需要建立一个包含TweetOrderNode同时声明两个全局变量users_tweetsfriends

然后考虑要求实现的功能。
发推,要用给出的Tweet.create(user_id, tweet_text)函数,然后将集成Tweet和orderNode和对应的user_id放入users_tweets
时间线,需要从users_tweets中按照Order取出对应user_id的后10Node,再取出Node.tweet放入结果数组List,注意tweet的大小写;
新鲜事,需要查看user_id的好友列表,将包括自己的每个人的后10Node放入List temp,再对temp中所有Node进行排序,取出前10Node。这里发现order不是对应于单个user_id的,而是对应users_tweets中的所有Node
所以,order也要声明为全局变量。
继续,关注好友,添加或查找from_user_id作为friends中的key值,然后对这个key值对应的value,也就是Map,添加to_user_idtrue的pair。
取关好友,和关注好友相同的操作,先从friendgetfrom_user_id的key值,再remove对应Map中to_user_id的pair即可。

下面讨论以上功能实现需要增加的细节。首先,取出前十个Node,取出后十个Node,需要建立两个函数getFirstTen()getLastTen(),对List temp进行操作。由于取出子数组的顺序依然相对不变,temp.subList(start, end)返回的十个Node需要被从大到小排序,以满足most recent的要求(order从大到小),我们需要构造新的Comparator SortByOrder,对Node类型的数组排序。注意在Comparator的实现上,return 1代表需要交换,return -1代表不需要交换。

最后,在功能函数的前面,进行MiniTweeter()的初始化。
结束~

Solution
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

相关文章

  • [LeetCode/LintCode] Construct the Rectangle

    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...

    sf_wangchong 评论0 收藏0
  • [LeetCode/LintCode] Top K Frequent Words

    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...

    0x584a 评论0 收藏0
  • [LeetCode/LintCode] Is Subsequence

    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) ...

    terasum 评论0 收藏0
  • [LeetCode/LintCode] Odd Even Linked List

    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...

    awokezhou 评论0 收藏0
  • [LeetCode/LintCode] Largest Palindrome Product

    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...

    Barry_Ng 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<