[LintCode][System Design] Web Lo

Problem

More Discussions

Implement a web logger, which provide two methods:

1. hit(timestamp), record a hit at given timestamp.
2. get_hit_count_in_last_5_minutes(timestamp), get hit count in last 5 minutes.
   the two methods will be called with non-descending timestamp (in sec).

Example

hit(1);
hit(2);
get_hit_count_in_last_5_minutes(3);
>> 2
hit(300);
get_hit_count_in_last_5_minutes(300);
>> 3
get_hit_count_in_last_5_minutes(301);
>> 2

Solution

可以用一个hash存储timestamp对应的hit count，每次get hit时，只计算300秒内的，同时删除过期的key。

class WebLogger {
private:
    map<int, int> count;
public:
    WebLogger() {
        // initialize your data structure here.
    }

    /**
     * @param timestamp an integer
     * @return void
     */
    void hit(int timestamp) {
        // Write your code here
        count[timestamp]++;
    }

    /**
     * @param timestamp an integer
     * @return an integer
     */
    int get_hit_count_in_last_5_minutes(int timestamp) {
        int total = 0;
        vector<map<int, int>::iterator> iters;
        for(map<int, int>::iterator iter = count.begin(); iter != count.end(); iter++) {
            if (iter->first + 300 > timestamp) {
                total += iter->second;
            } else {
                iters.push_back(iter);
            }
        }
        for(int i = 0; i < iters.size(); i++) {
            count.erase(iters[i]);
        }
        return total;
    }
};

方法二：用一个双端队列保存hit的信息，每次检查末尾的元素是否timestamp == 当前timestamp，然后判断是更新还是插入新的元素。get hit的时候从队头判断当前的timestamp是否在300秒之内，如果在的话就退出查找循环，如果不在则出队，这样就保证了当前队列的元素都在300秒以内。

struct Node {
    int timestamp;
    int count;
    
    Node(int timestamp) {
        count = 1;
        this->timestamp = timestamp;
    }
};

class WebLogger {
private:
    deque<Node> dq;
    int totalCount;
    
public:
    WebLogger() {
        totalCount = 0;
    }

    /**
     * @param timestamp an integer
     * @return void
     */
    void hit(int timestamp) {
        totalCount++;
        if (dq.size() == 0 || dq.back().timestamp != timestamp) {
            Node node(timestamp);
            dq.push_back(node);
        } else {
            dq.back().count++;
        }
    }

    /**
     * @param timestamp an integer
     * @return an integer
     */
    int get_hit_count_in_last_5_minutes(int timestamp) {
        while(!dq.empty() && dq.front().timestamp + 300 <= timestamp) {
            totalCount -= dq.front().count;
            dq.pop_front();
        }
        return totalCount;
    }
};