野的公司店面简报

Booky 发表于 2017-4-8 07:36
太幸福了面到rate limiter！pass稳稳的！

补充内容 (2017-4-8 08:06):

想问问lz你说的方法是这样吗？我看了些面经 但是不知道理解的对不对
public class RateLimiter {
        class Request{
               
        }
        class RequestWrapper {
                Request rq;
                int timestamp;
                public RequestWrapper(Request rq, int timestamp) {
                        this.rq = rq;
                        this.timestamp = timestamp;
                }
        }
        int limited;
        Map<String, Queue<RequestWrapper>> map;
        public RateLimiter() {
                limited = 50;
                map = new HashMap<String, Queue<RequestWrapper>>();
        }
        //每次进queue之前，把队列里过期的request wrapper出队（根据时间是否离现在时间超过一秒），然后查看当前queu的size是否超过50，不是的话，就选择进队
        public boolean shouldPrintMessage(Request rq, int timestamp, String ip) {
                RequestWrapper newrw = new RequestWrapper(rq, timestamp);
                if(!map.containsKey(ip)) {
                        Queue q = new LinkedList<RequestWrapper>();
                        q.offer(newrw);
                        map.put(ip, q);
                } else {
                        Queue q = map.get(ip);
                        while(!q.isEmpty()) {
                                RequestWrapper rw = (RequestWrapper) q.peek();
                                if(rw.timestamp < timestamp) {
                                        q.poll();
                                }
                        }
                        if(q.size() >= limited) {
                                return false; // or throw exception
                               
                        }
                        q.offer(newrw);
                        map.put(ip, q);
                }
                return true;
        }
}

从构架上来说， 就是已个“ring buffer", 加俩指针。如果数据大而且频繁， ring buffer可以避免memory fragment。 你这么已说人家就觉得你牛了。

请问lz 是不是还得用一个count 计数

翻滚吧豆子 发表于 2017-7-12 12:38
要求滚动窗口，token buckt就不行

这是因为考虑到token bucket的burst rate 所以不能用token bucket么

sherlockzzq 发表于 2017-11-15 11:11
这是因为考虑到token bucket的burst rate 所以不能用token bucket么

token bucket 太简单了   一点都不好玩吧。。。
算法题在现实中本来就是写一辈子都遇不到的玩意儿

sherlockzzq 发表于 2017-11-15 10:30
请问lz 是不是还得用一个count 计数

不需要了啊

翻滚吧豆子 发表于 2017-11-17 13:11
不需要了啊

那请问如何判断新的请求是否到达最大的限度了啊

sherlockzzq 发表于 2017-11-18 00:57
那请问如何判断新的请求是否到达最大的限度了啊

看回帖  8个字  8个字 8个字

翻滚吧豆子 发表于 2017-11-18 13:33
看回帖  8个字  8个字 8个字

楼主请问这个 题目描述哪里能看到？ 谢谢！