Comment by akeefer | Hacker News Reader

Comment by akeefer | Hacker News Reader

I enjoy clever ways of approaching problems as much as the next guy, but I would never ding someone in an interview for not coming up with a clever-enough solution. Good software engineering is maybe 99.7% failure-avoidance and 0.3% cleverness. On very rare occasions you need a clever solution, but most of the time you need to solve the problem in a way that you're 100% sure will work, has no nasty failure conditions, and that other competent engineers will understand. If there's no other good solution, or if every bit/cycle matters, then you get to try to be clever, but that happens pretty rarely. I've seen way, way too many problems caused by people using clever solutions for problems that had straightforward-but-less-fun solutions. (And as has been pointed out plenty of times already here, the clever solution in this case is less optimal than a more straightforward one would be). If an interviewer seemed intent on proving they were more clever than me, or on trying to get me to throw out unnecessarily-clever solutions to straightforward problems, it would be a pretty big turnoff.

I doubt that the interviewer mentioned the prime number solution due to insufficient cleverness in the original solution. The answered O(n+m) solution actually contains flaws beyond its lack of cleverness. 1) there's no good reason to use a hash map, hashing is useful in maps for mapping an unevenly distributed set from a large an arbitrarily large space to an evenly distributed set from an arbitrarily small space. The space is only 26 characters so why hash? You can simply use a map (no hash needed), and in this case there's even a very natural way to get indices into an array (index(c) = c - 'a').

Now it's true, that these are both linear time solutions simply with different factors and we might simply say who cares. The thing about the prime solution is that it's actually really dumb itself and I think that's what Guy really wanted you to tell him. He was pointing out that you could leverage the smallness of your data and hoping the interviewee would come up with an even better way to leverage this fact.

The first thing we should notice is that asymptotic bounds are misplaced here if you consider how such a function might actually be used. The strings are basically being used as sets that is AA might as well be A as far as our answer is concerned. So assuming people aren't giving us stupid data (and in an interview you could mention a way to make this assumption true). The strings shouldn't ever have duplicates and thus shouldn't ever be bigger than 26 characters (otherwise they contain all of the characters and the answer is independent). So if a solution has runtime n + m + c, that c actually starts to matter.

The thing about the primes solution is that multiplication and modulo operations are actually very expensive and all you want to keep track of is whether you've seen a character (1 bit of information) so you should really use a bitmap for this. And since it so happens that 26 < 32 these will fit very nicely in a single int. It's even a pretty nice implementation: https://gist.github.com/707639

[edit: link to code]

With your solution, I might have not accepted you to do job because it is obvious you don't have experience with Unicode and localization.

that's outside the scope of the problem. (which is why I really dislike these kinds of tests, because you can't win - if you don't consider unicode the interviewer says "ahh, but what about unicode" and if you do the interviewer says "ahh, but that's outside the scope of the problem".)

The right way to approach this is to clarify the requirements. "Should I consider unicode?" will get you points with the interviewer, and will allow you to quickly clarify the scope of the question.

And I might have not accepted you for over-generalization that is one of the worst things ever you can do as a designer ;)

I don't think you read the post being discussed here.

> 15 seen &= mask(haystack);
Shouldn't it be

seen ^= mask(haystack);

And a personal change would be to define all as:

int all = ~(~0 << ('z' - 'a' + 1));

EDIT: For some reasons, asterisk doesn't appear before haystack.

Right you are, fixed now.

Yup, and you corrected my mistake as well. For some weird reasons, I typed ^ (xor) when I was actually thinking of | (or).

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

Okay, 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!

Powers 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'.

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

Yep, that's what I meant, thanks. Powers-of-two is just for getting the correct bits.

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

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

Ahh, sorry, good answer. Much simpler than finding an arbitrary number of primes.

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

Upvote ^10 if I could.

The dinging people for not-clever-enough solutions feels like hazing. It's less about competence than about ego. The most important thing in an interview is to make sure the person's level of skill is at least as big as their conception of their skill.

The most important thing in an interview is to make sure the person's level of skill is enough to be your coworker. Their conception of their skill doesn't matter. Programmers who know they're bad programmers are still bad programmers.

Sure but you at least have a chance at helping them out and moving them up. To some extent is culture and happenstance. Sometimes you get off on the wrong foot and you're on each other's nerves. But attitude and work ethic are like multipliers that can go negative.

Yeah, but a good programmer who thinks he's a great programmer will likely be a pain in the ass to work with.

There are two kinds of cleverness: cleverness that makes things simpler and easier to understand, and cleverness that makes things more complicated and harder to understand. Often the former is the more difficult of the two, and also the mark of a better programmer. Moreover, experienced-but-average programmers will often decry cleverness in general, having observed too many cases of the latter and not enough of the former kind, and then when the former kind comes along, they have the same reaction, and this is bad.

Reply on news.ycombinator.com