interview test

event_list.cpp

#include <random>
#include <unordered_map>
#include <vector>

class EventList {
public:
    void insert(std::pair<size_t, size_t> event_with_ts) {
        if(event_idx.find(event_with_ts.first)==event_idx.end()) {
            events.push_back(event_with_ts);
            event_idx[event_with_ts.first]=events.size()-1;
        }
    }
    
    std::vector<std::pair<size_t, size_t>> lookup(size_t event_id, size_t before, size_t after) {
        std::vector<std::pair<size_t, size_t>> ret;
        auto i=event_idx.find(event_id);
        if(i!=event_idx.end()) {
            fill_result(i->second, before, after, ret);
        }
        return ret;
    }
    
private:
    void fill_result(size_t pos, size_t before, size_t after, std::vector<std::pair<size_t, size_t>> &result) {
        size_t begin=0;
        size_t end=events.size();
        if(pos>=before)
            begin=pos-before;
        if(pos+after+1<=events.size()) {
            end=pos+after+1;
        }
        result.insert(result.begin(), events.begin()+begin, events.begin()+end);
    }
    
    std::vector<std::pair<size_t, size_t>> events;
    std::unordered_map<size_t, size_t> event_idx;
};

#include <iostream>

int main(int argc, const char * argv[]) {
    std::random_device rd;
    std::uniform_int_distribution<int> dist(0, 1000000);
    EventList el;
    std::vector<size_t> to_be_tested;
    for (int n = 0; n < 20000; ++n) {
        size_t id=dist(rd);
        el.insert({id, n});
        if(n%1000==0) {
            to_be_tested.push_back(id);
        }
    }
    std::uniform_int_distribution<int> dist1(1, 10);
    for(auto id: to_be_tested) {
        size_t before=dist1(rd);
        size_t after=dist1(rd);
        std::cout<<"===========================\n";
        std::cout << "lookup(" << id << ", " << before << ", " << after << ")\n";
        std::cout<<"---------------------------\n";
        std::vector<std::pair<size_t, size_t>> ret=el.lookup(id, before, after);
        for(auto ev: ret) {
            std::cout << ev.first << ", " << ev.second << std::endl;
        }
    }
    return 0;
}