A Google Interviewing Story
paultyma.blogspot.com
A Google Interviewing Story
1–10 of 122 posts
Re: A Google Interviewing Story
#2Angry 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.
Re: A Google Interviewing Story
#3I have been in a similar situation, where one interview's curveball ended up being asked in a subsequent interview.
I went through the same emotions as the author (including resisting the urge to grin from ear to ear). But like an idiot, I answered with the trick answer right away (though I was calm about it). I then told the interviewer that I had learnt it in a previous interview.
It turned out he was looking for the clever answer too; and he was disappointed that I knew it. Maybe he felt I wasn't sufficiently "excited" about the clever answer, but I never got the job. Which is not too bad, since that outfit wasn't my first choice anyways.
Re: A Google Interviewing Story
#4Angry 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.
Exactly. When your domain is restricted (characters or small ints), then why use a hashtable? Use an array. If initializing an array is a concern, use a smartarray.
Re: A Google Interviewing Story
#5Angry 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.
Re: A Google Interviewing Story
#6Multiplication and division are o(log n) operations.
Re: A Google Interviewing Story
#7The 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.
Re: A Google Interviewing Story
#8The 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.
Yeah, I don't get the interest in this answer. It's neat-but-useless.
Re: A Google Interviewing Story
#9The 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.
[deleted]
Re: A Google Interviewing Story
#10Angry 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.
Oh really? How much faster would that be?