[dangoldin]

I forgot to mention that I do hear the disc based solution quite a bit and it's definitely a valid response given the problem description. But I would still say "let's say you don't have any disk space, how would you go about the problem?" while still acknowledging that the answer was valid.

[wccrawford]

So at all times, you continue to lead them to the answer you want by continuing to add restrictions until you get there. And if they don't understand your favorite new concept immediately, they aren't judged worthy?

This isn't good interview technique.

[dangoldin]

I'm being defensive now but I think that's a pretty extreme view. Every answer is part of the interview process and it's not about the final destination. The more answers that people have the bigger the conversation and the more I can understand how someone thinks which is what you want to get out of an interview.

The fact that someone does quickly grasp the concept is a plus - why do you think it's the wrong approach? I definitely adapt my approach as I do more interviews so any feedback helps.

[Xk]

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.

[dangoldin]

Fair points but I don't expect people to get to the Bloom filter on their own - I view as more of a process that both of us are driving towards. I also enjoy hearing new solutions - there's always room for discussion and I will try to dig deeper into answers if I sense something is wrong.

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.

[charrington]

How about just going with the disk-based line if the candidate goes there? On-disk data structures is a rich area for exploration. I think you're getting people a little riled up here because you seem to want to discuss Bloom filters no matter what. You seem to grok that this should be about thinking skills, data structures, and algorithms. That's great. Forcing the candidate to go where you have a particular interest is not so great.

[dangoldin]

Unfortunately I myself am not too familiar with on-disk data structures and wouldn't be too comfortable interviewing based on that. It probably is something I should brush up on but for the specific role I've been interviewing for it doesn't seem to be a big need.

[Stormbringer]

Good luck with your spell checkers for tightly RAM limited devices with no persistent storage and no external hard drives...

Frankly, I'm surprised and amazed that there is still a market for modding old Tamagotchis. Human ingenuity is amazing.

[hackinthebochs]

I think this is a great interview question, and I wouldn't have came up with the bloom filter answer. The point is the discussion triggered by the question, not any particular answer.

You're taking it like it's a knock on you that he wouldn't 'accept' your answer but lead you down the line of questioning he planned for. But this exactly what interviewers should do: be prepared for a certain line of discussion and nudge the candidate in that direction.

If someone was familiar enough with bloom filters to come up with that answer on their own, that should be an advantage to them. The chances of false negative seems minimal since it's uncommon and I don't think some hack would understand it well enough to use it so appropriately after a cursory glance at a wikipedia page.

On the other hand, the discussion is more important than the answer so the person spouts off bloom filter immediately is short circuiting the very process he's there for. So it balances out either way.

[Stormbringer]

I like many others thought that this was a terrible interview question.

On the other hand, I learned something today (probabilistic data structures?!? WTF?!?)

I think the fundamental problem with the question is that it is the wrong way round. It is designed so that the interviewer can show off his expertise, whereas traditionally the view would be that you need to get the person being interviewed to show off their expertise.

Of course, if what you are really interviewing for is people who will bask in your awesomeness, then it is ideal.

----

I had a really weird interview this week. I couldn't get a word in edgewise. Haven't heard back from them either. Bizarre. If you're not going to let me talk, what is the basis for rejecting me? :D

[hackinthebochs]

I don't get where this question shows he's trying to "show off his expertise". I can see that some people might be sensitive to the situation having been through the type of interview you describe. But I think its going too far assuming thats his motivation for this question.

I think the best types of questions are the ones where you don't know the answer ahead of time. This is where you really get to see how someone thinks. The bloom filter is rare enough that its likely people won't have any exposure to it at all. This gives you a very objective look at how quickly people can grasp new concepts and then apply them. This is exactly what an interview should hope to discover about a candidate.

What I see in the responses to this question are people who aren't very interested in the science side of computer science and thus immediately get suspicious when a question heads in that direction. Perhaps unfortunately, questions like these are going to be biased towards someone who does have a high interest in it.