News for hackers. Stuff that matters.
Re:A Google Interviewing Story by lacker on Friday November 19, 2010 @07:43PM (#1923422)
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.
Re:A Google Interviewing Story by 124816 on Friday November 19, 2010 @09:27PM (#1923641)
Especially since they're using the primes to encode N = 26 independent variables within a single number. On any modern CPU, you already have 32 (or more) independent variables in each number, they just happen to be called bits. And you can test them and set them in much simpler and faster ways than integer multiplication and mod.
Re:A Google Interviewing Story by psadauskas on Friday November 19, 2010 @08:00PM (#1923454)
Yeah, seems like dividing ints would be a much more expensive operation than comparing them.
Re:A Google Interviewing Story by Oxryly on Friday November 19, 2010 @07:45PM (#1923427)
Yeah, I don't get the interest in this answer. It's neat-but-useless.
Re:A Google Interviewing Story by firebones on Friday November 19, 2010 @08:38PM (#1923546)
It's just one anecdote, but it also seems like the kind of thing that happens in companies that grow fast and have trouble maintaining quality in their hiring process. Instead of hiring true cleverness, they hire for someone who feigns the trappings of cleverness (smart enough to regurgitate a "clever" solution that turns out not to be practical in the real world.)
Re:A Google Interviewing Story by jules on Friday November 19, 2010 @09:10PM (#1923605)
Can you explain what representation you use to get multiplication by a constant in O(log n)? Wouldn't it be at least O(n) for the standard bignum representations, making the algorithm O(n^2).

Multiplying n primes together creates an O(n) digit number. Multiplying an O(n) digit number by a constant is an O(n) operation. So essentially we're doing an O(n) operation n times, hence O(n^2).

The smartest representation that I can think of for the numbers would be to store the prime factor exponents in an array, which would essentially transform the algorithm into the array based version. For example 120 = 2^3x3x5 would be represented as {3,1,1,0,0,...}.

Re:A Google Interviewing Story by nostrademons on Friday November 19, 2010 @09:44PM (#1923664)
It's O(n) in the number of bits. The number of bits is O(log n) in the value of the number. Multiplying n primes together, where the primes are taken from a restricted set of numbers, creates a number whose value is O(n) (it has n factors, but each factor is bounded by a constant).

BTW, I would've used a bitvector. For lowercase letters only, you could fit it into a 32-bit value (add mixed-case and numbers and you can fit it into 64 bits), then it's just an OR to set a bit and an AND to read if a bit has been set, both fast machine-level operations.

Edit: Didn't see the footnote on the problem. A bitvector doesn't work if counts must be kept, but you can still do this pretty simply with the table solution.

Re:A Google Interviewing Story by jules on Saturday November 20, 2010 @06:53AM (#1924376)
So, the resulting algorithm would be O(n^2) not O(n) where n is the length of the string. The table based solution is exactly like keeping the exponents in an array.
Re:A Google Interviewing Story by gtdminh on Saturday November 20, 2010 @12:32AM (#1923942)
i think it is a joke, you guys here already mentioned multiplication/division are expensive operations, so a simple hash just works well. and who care the complicated way if the simple way just makes the job done nicely. programming is an art.