|
|
|
|
|
|
by Xk
5635 days ago
|
|
|
First of all, let me say this is a significantly better question than many I've seen. However, It disturbs me when someone is interviewing me and they are looking for a particular answer and they consider everything else wrong. Even when I find more efficient answers, if it's not theirs, it's wrong. Think about it like those little kid riddles: "A man is found dead with a noose around his neck and a puddle of water at his feet. How is it he was killed?" Put on a stool and the stool was removed? Then add the restriction "There are no stools." He was lifted with the rope? "The rope was tied to a bar on the ceiling and couldn't be raised higher." Raised in the air by some strong people and then let hang? "No one raised him from the air." You can make guesses all day long and I can make up excuses about why you're wrong until you finally guess what I wanted you to guess -- that he was standing on a block of ice. More specific to your question: when I read it the first thing that came to mind was just to have an array of booleans and for each word in the table set H(word) to true and then when looking up a word check if H(word) is true. I don't know what bloom filters are, so I'm not saying this answer is better than them -- but after I suggest that instead of imposing some other restriction, ask me to think about what is wrong with my answer. Talk to me about the false-positives/false-negatives [or lack thereof]. Talk to me about what hash function I could use. Or about why I picked that way. Or what problems could happen if the hash function wasn't perfectly uniform. |
|
|
At the end I do like to get to the Bloom filter piece though in order to see what the response is as well as talk about something that is new to them.