362. Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301);

Follow up:
What if the number of hits per second could be very large? Does your design scale?

S1：queue

此题要根据hit和getHits出现的频率来设计，如果hit出现次数很多，queue会经常需要push和pop，效率不高。

class HitCounter {
public:
    /** Initialize your data structure here. */
    HitCounter() {
        count = 0;
    }

    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        if (q.empty() || q.back().first < timestamp) {
            q.push(make_pair(timestamp, 1)); 
        } else {
            q.back().second++;
        }
        count++;
        while (timestamp - q.front().first >= 300) {
            count -= q.front().second;
            q.pop();
        }
    }

    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        while (timestamp - q.front().first >= 300) {
            count -= q.front().second;
            q.pop();
        }
        return count;
    }

private:
    queue<pair<int, int>> q;
    int count;
};

S2： circle buffer

因为只需要300s内的数据，可以维护一个个300长度的buffer存储每秒的hit，另一个300长度的buffer存储对应的时间。

timestamp % 300即对应的index，若time[idx] != timestamp则说明过了至少一轮300s循环，重置hits[idx]为1

class HitCounter {
public:
    /** Initialize your data structure here. */
    HitCounter() {
        time.resize(300);
        hits.resize(300);
    }

    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        int idx = timestamp % 300;
        if (time[idx] == timestamp) {
            hits[idx]++;
        } else {  //reset
            time[idx] = timestamp;
            hits[idx] = 1;
        }
    }

    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        int count = 0;
        for (int i = 0; i < 300; ++i) {
            if (timestamp - time[i] < 300) {
                count += hits[i];
            }
        }
        return count;
    }

private:
    vector<int> time, hits;
};

359. Logger Rate Limiter

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

Example:

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true; 

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;

S1： circle buffer

只用存储10s内的string，节省空间

class Logger {
public:
    /** Initialize your data structure here. */
    Logger() {
        record.resize(10);
        time.resize(10);
    }

    /** Returns true if the message should be printed in the given timestamp, otherwise returns false.
        If this method returns false, the message will not be printed.
        The timestamp is in seconds granularity. */
    bool shouldPrintMessage(int timestamp, string message) {
        int idx = timestamp % 10;
        for (int i = 0; i < 10; ++i) {
            if (timestamp - time[i] < 10) {
                if (record[i].find(message) != record[i].end())
                    return false;            
            }
        }
        if (time[idx] == timestamp) {
            record[idx].insert(message);
        } else {
            record[idx] = unordered_set<string>{message};
            time[idx] = timestamp;
        }
        return true;
    }
    vector<unordered_set<string>> record;
    vector<int> time;
};

S2： hashmap

存储每个string最新的timestamp，O(1)查询更快

    bool shouldPrintMessage(int timestamp, string message) {
        if (record.find(message) == record.end() || timestamp - record[message] >= 10) {
            record[message] = timestamp;
            return true;
        } else {
            return false;
        }
    }  
    unordered_map<string, int> record;