Implement a rate limiter, provide one method:is_ratelimited(timestamp, event, rate, increment).

• timestamp : The current timestamp, which is an integer and in second unit.
• event : The string to distinct different event. for example, "login" or "signup".
• rate : The rate of the limit. 1/s (1 time per second), 2/m (2 times per minute), 10/h (10 times per hour), 100/d (100 times per day). The format is [integer]/[s/m/h/d].
• increment : Whether we should increase the counter. (or take this call as a hit of the given event)

The method should return true or false to indicate the event is limited or not.

Have you met this question in a real interview?

Yes

Example

is_ratelimited(1, "login", "3/m", true), return false.
is_ratelimited(11, "login", "3/m", true), return false.
is_ratelimited(21, "login", "3/m", true), return false.
is_ratelimited(30, "login", "3/m", true), return true.
is_ratelimited(65, "login", "3/m", true), return false.
is_ratelimited(300, "login", "3/m", true), return false.

class RateLimiter {
public:
    /**
     * @param timestamp the current timestamp
     * @param event the string to distinct different event
     * @param rate the format is [integer]/[s/m/h/d]
     * @param increment whether we should increase the counter
     * @return true or false to indicate the event is limited or not
     */
    bool isRatelimited(int timestamp, string& event, string& rate, bool increment) {
        // Write your code here
        bool res = false;

        if (mp.find(event) == mp.end())
            mp[event] = map<int, int>();

        int delimiter = rate.find('/');
        int times_limit = stoi(rate.substr(0, delimiter));
        string type = rate.substr(delimiter + 1);
        int time = 1;
        if (type == "m")
            time *= 60;
        else if (type == "h")
            time = time*60*60;
        else if (type == "d")
            time = time*60*60*24;

        int start =  timestamp - time + 1;
        res = findEventsInRange(mp[event], start, timestamp) >= times_limit;

        if (increment && !res)
            mp[event][timestamp]++;

        return res;
    }

private:
    map<string, map<int, int>> mp;

    int findEventsInRange(map<int, int>& events, int start, int end) {
        int times =  0;
        auto it = events.lower_bound(start);
        for (; it != events.end(); ++it) {
            if (it->first > end)
                break;
            times += it->second;
        }
        return times;
    }
};