Hacker News new | comments | ask | show | jobs | submit login

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.



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.


Yeah, seems like dividing ints would be a much more expensive operation than comparing them.


Yeah, I don't get the interest in this answer. It's neat-but-useless.


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.)


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,...}.


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.


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.


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.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: