Lintcode 555. Counting Bloom Filter

Description

中文English

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?  

Example

Example1

Input:
CountingBloomFilter(3)
add("lint")
add("code")
contains("lint") 
remove("lint")
contains("lint") 

Output: 
[true,false]

Example2

Input:
CountingBloomFilter(3)
add("lint")
add("lint")
contains("lint")
remove("lint")
contains("lint")

Output: 
[true,true]

Code (java):

class HashFunction {
    private int size;
    private int base;
    public HashFunction(int size, int base) {
        this.size = size;
        this.base = base;
    }

    public int hash(String str) {
        int hashCode = 0;
        for (int i = 0; i < str.length(); i++) {
            hashCode = (int)(((long)hashCode * base + Integer.valueOf(str.charAt(i))) % size);
        }

        return hashCode;
    }
}

public class CountingBloomFilter {
    private List<HashFunction> hashFunctions;
    private int[] bloomFilter;
    /*
    * @param k: An integer
    **/
    public CountingBloomFilter(int k) {
        // do intialization if necessary
        hashFunctions = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            HashFunction func = new HashFunction(100000, 2 * i + 3);
            hashFunctions.add(func);
            bloomFilter = new int[100000];
        }
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            bloomFilter[hashCode] += 1;
        }
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void remove(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            bloomFilter[hashCode] -= 1;
        }
    }

    /*
     * @param word: A string
     * @return: True if contains word
     */
    public boolean contains(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            if (bloomFilter[hashCode] <= 0) {
                return false;
            }
        }

        return true;
    }
}