When I interviewed at Instructure in 2013, I used this exact story. I got a very similar question: you had a string coming across the network and you were supposed to keep track of how many times you saw each character. I ended up going through it the same way the author did, where you maintained a hash and incremented the count as you read each letter. Then at the end I did a "by the way I saw this blog where someone was discussing this problem and they had a crazy idea..."

The prime number thing is obviously bad for this problem, since the giant number would grow arbitrarily large and you'd have to do a bunch of expensive division operations. But it's out of the standard box enough to suggest to the interviewer you are a curious sort who likes to think about novel data structures. At any rate, I got the job.

Kind of a strange story. That prime number approach is just awful. You'll (obviously) need a bignum library. You need a prime number generator that can get you the Nth prime. The division operation is going to be very slow. It's interesting to consider how it works, but it would never occur to me to mention it since it's so clearly not actually a good idea.

If you want to take advantage of having a limited range of possible characters, just use a bit vector. If you're limited to ASCII then you only need 16 bytes to track them all. Less if you're limited to printable characters.

It would be fun to discuss the prime number version in a sort of "how would this work and why would it be terrible?" way, but if I had an interviewer present it as a way to "do better" I'd have to seriously reconsider if I'd actually want the job.

> Deja-Guy

Hehe. Very funny!