CareerCup

I didn't know what a blossom filter was. I just learnt a few things and I want to give it a try. Would this make sense?

Given that we are working with ASCII from 97 to 122, we can consider that the changing bits for each letters are the 5 least-significant (the ones to the right in a little-endian machine).

So we can use an array of 20 bits and just assign directly.

int table = 0;

// assume we check the word is 4 chars somewhere else
int hash(char * str) {
	int h = 0;
    h |= ((int)(char[0] & 0b11111)) << 15;
	h |= ((int)(char[1] & 0b11111)) << 10;
	h |= ((int)(char[2] & 0b11111)) << 5;
	h |= ((int)(char[3] & 0b11111)) << 0;
	return h;
}

// assume str is 4 char
void put(char * str) {
	table |= hash(str);
    putInSet(str);
}

int maybeInSet(char * str) {
	// if not 4 char return 0

	// else
	return (table & hash(str)) == table;
}

}

// Here's a Java implementation
	static int MAX_BYTE = 488;
	static int MIN_BYTE = 388;             // i.e., "aaaa"
	static int[] keys = new int[100];        // used because MAX_BYTE - MIN_BYTE
	static String[] words = {"able", "band", "bend", "card", "darn", "form", "grab", 
				"harm", "look", "make", "mate", "peer", "team"};

	public static void main(String[] args)
	{
		createBloom(words);
		

		System.out.println("may contain: " + "abbe" + mayContain("abbe"));
	}
	

	public static void createBloom(String[] values)
	{
		for(int i = 0; i < values.length; i++)
		{
			int key = getKey(values[i].getBytes());
			if(keys[key - MIN_BYTE] == 0)
			{
				keys[key - MIN_BYTE]++;
			}
		}
	}

	public static int getKey(byte[] bit)
	{
		int out = 0;
		for(int i = 0; i < bit.length; i++)
		{
			out += bit[i];
		}
		return out;
	}

	public static boolean mayContain(String query)
	{
		int keyCheck = getKey(query.getBytes());		// find query key
		return keys[keyCheck - MIN_BYTE] == 1;
	}

int hash[4][26];

void put_in_set(char *word)
{
    int i = 0;
    while(word && i<4)
    {
            hash[i][*word - 'a'] = 1;
            i++;   
    }
}

int am_in_set(char *word)
{
    int ret = 0;
    int i    = 0;
   
    while(word && i < 3)
    {
         if( hash[i][ *word - 'a'] == 0 )
              break;
    }
    if( i == 3 )
       ret = 1

    return ret;
}