4 ms·
Agreed. The prime-number-division thing is a great answer... FOR SPOCK. Who wants to read code that does that kind of stuff... converting strings in to prime
by unoti 16y ago
Agreed. The prime-number-division thing is a great answer... FOR SPOCK. Who wants to read code that does that kind of stuff... converting strings in to prime numbers? How about: code it in a reasonable, readable way, and come back and optimize it if and when it needs optimizations. People that code things in the cleverest way, even when it's not needed, drive me batty.
I'd far rather see a developer cross 10 items off the to-do list instead of cross 1/2 of an item off a to-do list, and get lots of style points.
It's good to see that a candidate has creativity to come up with solutions like this. But I'd want to temper that by also seeing if they have the good judgement to know when to use such things (almost never).
- StavrosK 16y agoOkay, how was it a great answer? Unless I'm miscounting from all the jet lag, it's still O(n+m), only much more convoluted (not to mention slower, since you have a constant factor from all the multiplications/divisions). And seriously, primes? Why not powers of two? Gah, so much fail in that answer, but the worst thing is that the guy proposed it as a better alternative, and the interviewee admired it!
- tene 16y agoPowers of two wouldn't actually work there. Using primes lets you use division as a test for presence in the original set. The task is 'detect presence in the set', and integers are uniquely identified by their prime factorization. Powers of two would just give you another power of two. That wouldn't actually preserve the information you're looking for. Consider an original string 'bb', and a test string 'c'. With powers of two, you'd have 2*2, and your test would be a division by 4, which would be successful by having no remainder, indicating that 'c' is a subset of 'bb'.
- gojomo 16y agoIf using powers-of-two, you'd bitwise-OR rather than multiply the values-per-character. Simpler op, and your accumulated value per string never rises (in the 26-letter case) above 2^26.
- StavrosK 16y agoYep, that's what I meant, thanks. Powers-of-two is just for getting the correct bits.
- ericd 16y agoPowers of two wouldn't work. If A = 2^1, B = 2^2 AA, B would evaluate to true. But you're right, the running times aren't any better, except that the constant factors of dealing purely in arithmetic might make it faster in real terms if dealing with a lot of this type of thing than creating hash maps. If response time matters for the application (high frequency trading, etc), it might make a difference.
- StavrosK 16y agoSorry, by "powers of two" I meant bitmasks, not actually dividing with powers of two. Let A = 2^1, Z=2^26, and then OR with 2^1 when you encounter an A, etc. If the integer is non-zero when you're done, you've exhausted all the characters in the original string.
- ericd 16y agoAhh, sorry, good answer. Much simpler than finding an arbitrary number of primes.
- astrodust 16y agoThis is exactly what I was thinking and I have no idea why it didn't come up. Given an "alphabet" of 26 characters, that neatly fits inside a long int, and that's just crying out for a bitmask.
- jerhewet 16y agoUpvote ^10 if I could.