LintCode-505: Web Logger (System Design题)

数据结构采用deque，参考了网上的答案。

注意

1） get_hit_count_in_last_5_minute()里面必须用<=。

2） 同一个timestamp可能hit多次，所以都必须加起来。

3）deque.front()是最老的entry，所以将其与当前timestamp比较，若不在当前5分钟内，则其count不算，再pop_front()，继续与当前timestamp比较。

class Node {
public:
    Node(int t, int c) : timestamp(t), count(c) {}
    int32_t getTimestamp() {return timestamp;}
    void incCount() {count++;}
    uint32_t getCount() {return count;}
private:
    int32_t timestamp;
    uint32_t count;
};

class WebLogger {
public:
    WebLogger() : count() {}

    /*
     * @param timestamp: An integer
     * @return: nothing
     */
    void hit(int timestamp) {
        if (!dq.empty() && (dq.front().getTimestamp() == timestamp)) {
            dq.front().incCount();
        } else {
            dq.push_back(Node(timestamp, ));
        }
        count++;
    }

    /*
     * @param timestamp: An integer
     * @return: An integer
     */
    int get_hit_count_in_last_5_minutes(int timestamp) {
        while(!dq.empty() && ((dq.front().getTimestamp() + ) <= timestamp)) {
            count -= dq.front().getCount();
            dq.pop_front();
        }
        return count;
    }

private:
    uint32_t count;
    deque<Node> dq;
};