11–20 of 122 posts
The prime multiplication is a pretty bad solution. It's actually O(n log n) rather than O(n), since you have to use some form of big integer, and multiplying a size-n number by a constant is O(log n). It is also needlessly complicated.
I interviewed for a Program Management position in the Visual Studio group. My first interview was with the Design Manager for the VS product line. Her final question for me was about building an effective temperature control system for a new house. I launched into a 5 minute analysis of the advantages and disadvantages of a wide range of HVAC systems, obvious ramifications from open floor plans, and so on.
A month later, we sat down for lunch as co-employees for the first time, and I told her the whole story. She got a big laugh out of it. I guess she didn't realize that's what I'd spent the last few months working on.
I know some coworkers who will intentionally ask a question they know you were asked in a previous interview to test your integrity. (Edit: Not that I would condone this practice either.)
These types of interview questions are about evaluating how you think far more than what you know. So, more importantly than the risk of getting caught, if you recite an answer from memory and pretend that you're deriving the solution on the fly, you're lying to your future coworker.
I can solve the same problem by using statistical thermodynamics, and show its only o(1), since each string is a configuration of the system and finding common alphabets is like finding degenerate states.
Angry because neither the hash table or the prime multiplication would be as fast as a boolean array indexed by the char value. As an added bonus, the boolean array actually makes the most intuitive sense.
Characters can repeat, so a boolean array doesn't work.
Plus, the story says I mumbled awhile that given the characters were limited to alphabetic (his original specification) that I could use an array instead of a hashtable for some constant time savings but that was about it.
Angry because neither the hash table or the prime multiplication would be as fast as a boolean array indexed by the char value. As an added bonus, the boolean array actually makes the most intuitive sense.
Angry because neither the hash table or the prime multiplication would be as fast as a boolean array indexed by the char value. As an added bonus, the boolean array actually makes the most intuitive sense.
Even faster is to fill a 32-bit mask with "seen" characters for each string. AND them together and compare result to the mask from the second string.
Standard counter-intuitive example (from the game development domain) is how to check if an array of integers has a zero in it. The answer, when all things are considered, is to scan through an entire array making a simple arithmetic for each item and one comparison at the end rather than compare each element.
The same may happen with your example. Filling up 32-bit mask might be more expensive than to flip an element in a boolean array. That's not even considering that the array option allows for early termination of the second loop.
Angry because neither the hash table or the prime multiplication would be as fast as a boolean array indexed by the char value. As an added bonus, the boolean array actually makes the most intuitive sense.
Angry because neither the hash table or the prime multiplication would be as fast as a boolean array indexed by the char value. As an added bonus, the boolean array actually makes the most intuitive sense.
Even faster is to fill a 32-bit mask with "seen" characters for each string. AND them together and compare result to the mask from the second string.