Implement a standard bloom filter. Support the following method:
1.StandardBloomFilter(k),The constructor and you need to create k hash functions.
2.add(string). add a string into bloom filter.
3.contains(string). Check a string whether exists in bloom filter.

Have you met this question in a real interview?

Yes

Example

StandardBloomFilter(3)
add("lint")
add("code")
contains("lint") // return true
contains("world") // 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 StandardBloomFilter {
private:
    int k;
    vector<unique_ptr<HashFunction>> hashFunc;
    bitset<200000> bits;

public:
    StandardBloomFilter(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)));
    }

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

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