野的公司店面简报

上午新鲜面经，rate limit。因为早有准备，所以秒的快，用rotated array，然后测试代码，然后follow up 多线程的各种解决方案。

面试官我一开始以为是中国人，因为有我们国产的，每个音节都很咬的那种口音。
可是后来

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

on 模式传进去的，这样方便测试。小哥也赞了下
欧巴说英文我听不太懂，交流起来很卡，代码没写多久，主要在说话。还是有点小尴尬

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

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

奇怪了，怎么会用到hashmap呢？

rotated array很简单啊，就是比如1秒钟限制3个request
我维护一个long int array 长度为3，里面存着最近3个request的访问时间戳，一个指针指向这3个中第一个进来的request。
有新的请求，我就检查指针指向的request是不是已经是1秒以前的，如果是则请求成功，新请求的时间戳覆盖指针指向。然后指针+1再mod，就rotated了。

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;
        }
}

太幸福了面到rate limiter！pass稳稳的！

补充内容 (2017-4-8 08:06):
话说我只知道 hashmap + queue 的想法。你的 rotated array 实现起来是类似于 queue 吗？

翻滚吧豆子 发表于 2017-4-8 08:36
奇怪了，怎么会用到hashmap呢？

rotated array很简单啊，就是比如1秒钟限制3个request

数据结构就是java的ArrayDeque，一模一样，只是这里自己用array做反而简单一点。
我不理解为啥有hashmap

翻滚吧豆子 发表于 2017-4-8 08:41
数据结构就是java的ArrayDeque，一模一样，只是这里自己用array做反而简单一点。
我不理解为啥有hashmap

咦……那感觉题目描述是不一样的？我之前看到的版本，是访问多个 ip 多次，所以对应每个 ip 要存一个 queue 来做。ip 就是 hashmap 的 key

Booky 发表于 2017-4-8 08:52
咦……那感觉题目描述是不一样的？我之前看到的版本，是访问多个 ip 多次，所以对应每个 ip 要存一个 que ...

哦，这个哥子没要求ip哈
有ip就是用hashmap对的

这题用Token Bucket可否？！

newgod2500 发表于 2017-7-10 11:04
这题用Token Bucket可否？！

要求滚动窗口，token buckt就不行

翻滚吧豆子 发表于 2017-4-8 08:36
奇怪了，怎么会用到hashmap呢？

rotated array很简单啊，就是比如1秒钟限制3个request

用hash table记录每个对象上一次request的时间戳也可以吧？当然如果你有特别多的新对象进来，可能space效率会低一些

kqxqx 发表于 2017-10-6 03:10
用hash table记录每个对象上一次request的时间戳也可以吧？当然如果你有特别多的新对象进来，可能space效 ...

同学貌似你对这个题不熟，建议去搜一下rate limit。