A Google Interviewing Story

Post by Oxryly » Mon, Nov 22, 2010, 12:44 AM UTC

jamesaguilar wrote: post #71

Oxryly wrote: post #24

Earlier quoted context omitted.

I was assuming a 26 letter alphabet. At that point the shifting, anding and comparing would take place in registers.

True, although if there are lower case letters too it could become a problem. At any rate, I'm not sure that the register aspect would improve speed significantly because of the latency of getting the string from main memory. You're still going to get pipeline stalls as you reach portions of the string that are not in the cache.

Yeah, the registers will only be faster than manipulating some sort of bool array. Reading the original string (with associated cache stalls) will certainly be necessary.

Post by Oxryly » Mon, Nov 22, 2010, 12:46 AM UTC

TheNewAndy wrote: post #78

jamesaguilar wrote: post #20

Earlier quoted context omitted.

Maybe. You need 256 bits for all the possible chars, and this solution is perhaps a little less intuitive. Also, the shift + and + cmpz is not necessarily going to be significantly faster than an address lookup + cmpz because of the latency of getting the array from memory or cache. Though it will use less cache space compared to the size of modern caches that's not enough of a win to matter much I would guess.

Doing it this way will use the optimal amount of memory (in the worst case) (assuming an O(n+m) answer). There are exactly 26 bits of state that need to be tracked (where "bit" is used in the information theoretic sense of the word). If you choose to store this state as 26 actual bits, then you win. Multiplying together the first 26 primes requires that you can store a number up to 23286236435849736090006331688050736…

If you're marking used letters in a mask, why sort first?

Re: A Google Interviewing Story

Re: A Google Interviewing Story