Implement a counting bloom filter. Support the following method:
1.add(string). Add a string into bloom filter.
2.contains(string). Check a string whether exists in bloom filter.
3.remove(string). Remove a string from bloom filter.

Have you met this question in a real interview?

Yes

Example

CountingBloomFilter(3) 
add("lint")
add("code")
contains("lint") // return true
remove("lint")
contains("lint") // return false

#include <bitset>
#include <memory>

using namespace std;


class HashFunction {
private:
    int cap, seed;
public:
    HashFunction(int cap, int seed) {
        this->cap = cap;
        this->seed = seed;
    }

    int hash(string& value) {
        int ret = 0;
        int n = value.size();
        for (int i = 0; i < n; ++i) {
            ret += seed * ret + value[i];
            ret %= cap;
        }
        return ret;
    }
};

class CountingBloomFilter {
private:
    int k;
    vector<unique_ptr<HashFunction>> hashFunc;
    vector<int> bits;
public:
    CountingBloomFilter(int k) {
        // initialize your data structure here
        this->k = k;
        for (int i = 0; i < k; ++i)
            hashFunc.push_back(unique_ptr<HashFunction>(new HashFunction(100000 + i, 2 * i + 3)));
        bits.resize(100000 + k, 0);
    }

    void add(string& word) {
        // Write your code here
        for (int i = 0; i < k; ++i) {
            int pos = hashFunc[i]->hash(word);
            bits[pos] += 1;
        }
    }

    void remove(string& word) {
        // Write your code here
        for (int i = 0; i < k; ++i) {
            int pos = hashFunc[i]->hash(word);
            bits[pos] -= 1;
        }
    }
    bool contains(string& word) {
        // Write your code here
        for (int i = 0; i < k; i++) {
            int pos = hashFunc[i]->hash(word);
            if (bits[pos] <= 0)
                return false;
        }
        return true;
    }
};