From:A Google Interviewing Story\
Q:\
Say you have one string of alphabetic characters, and say you have
another, guaranteed smaller string of alphabetic characters.
Algorithmically speaking, what's the fastest way to find out if all the
characters in the smaller string are in the larger string?
\
For example, if the two strings were:
\
\
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
\
\
You'd get true as every character in string2 is in string1. If the two
strings were:
\
\
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
\
A:\
Finally, I told him the best method would simply be O(n+m). That is,
iterate through the first string and put each character in a
**hashtable**
(cost of O(n) or 16). Then iterate
the 2nd string and query the hashtable for each character you find. If
its not found, you don't have a match. That would cost 8 operations - so
both operations together is a total of 24 operations. Not bad and way
better than the other solutions.\
\
\
**He stepped up to the whiteboard, "What if - given that we have a
limited range of possible characters - I assigned each character of the
alphabet to a prime number starting with 2 and going up from there. So A
would be 2, and B would be 3, and C would be 5, etc. And then I went
through the first string and 'multiplied' each character's prime number
together. You'd end up with some big number right? And then - what if I
iterated through the 2nd string and 'divided' by every character in
there**. If any division gave a remainder - you knew you didn't have a
match. If there was no remainders through the whole process, you knew
you had a subset. Would that work?"
\
Every once in awhile - someone thinks so fantastically far out of your
box you really need a minute to catch up. And now that he was standing,
his leather pants weren't helping with this.
\
Now mind you - Guy's solution (and of course, needless to say I doubt
Guy was the first to ever think of this) was algorithmically speaking no
better than mine. Even practically, you'd still probably use mine as it
was more general and didn't make you deal with messy **big integers**. But on the
"clever scale", Guy's was way, way, (way) more fun.
\
\
you'd get false as Z isn't in
the first string.