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.