News for hackers. Stuff that matters.
Re:A Google Interviewing Story by nl on Friday November 19, 2010 @08:13PM (#1923486)
Your anger is misplaced.

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.

Re:A Google Interviewing Story by bfung on Friday November 19, 2010 @11:11PM (#1923823)
it doesn't matter if characters are repeated. Let's assume ascii characters, so 'A' = 65 in decimal. If you make an array, T[], where T[65] = 1 if 'A' exists and 0 if 'A' didn't exist in the first string, you can run through the 2nd string to check if T[65] was true (1) or false (0), telling you if the character in the 2nd string appeared in the first. Same thing as the hashtable. I think that's what was meant by boolean array.
Re:A Google Interviewing Story by nl on Friday November 19, 2010 @11:27PM (#1923848)
I guess it depends how the question is presented. Often it is known as the "Ranson Question" (A set of magazines, a given ransom message: can you make the message from the magazines).

In this case the question says find out if all the characters in the smaller string are in the larger string, so yes, I think you are right - the repeats don't matter here.

Re:A Google Interviewing Story by exit on Friday November 19, 2010 @08:32PM (#1923532)
sorry, i don't get how characters repeating affects things
Re:A Google Interviewing Story by tedunangst on Friday November 19, 2010 @10:23PM (#1923750)
If there are 3 As in the first string and 4 in the second, it fails. A boolean value can't count to 3.
Re:A Google Interviewing Story by jamesaguilar on Saturday November 20, 2010 @01:52AM (#1924031)
Maybe in a different problem it would fail, but this is merely a presence test, so booleans are fine. At any rate, an array of int32s instead of bools would defeat the objection for reasonably long strings.
Re:A Google Interviewing Story by tedunangst on Saturday November 20, 2010 @12:30PM (#1924843)
This is that different problem. The author's description is muddy, but you do need the counts.