5 ms·

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 solut

by akeefer 16y ago

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.

baguasquirrel 16y ago
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.
- jemfinch 16y ago
  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.
  - baguasquirrel 16y ago
    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.
  - kelnos 16y ago
    Yeah, but a good programmer who thinks he's a great programmer will likely be a pain in the ass to work with.
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 ago
  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!
  - tene 16y ago
    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'.
    - gojomo 16y ago
      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.
jdoliner 16y ago
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 https://gist.github.com/707639 [edit: link to code]
- tomerico 16y ago
  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.
  - deleted 16y ago
    [deleted]
  - 16y ago
ecuzzillo 16y ago
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.

by akeefer 16y ago

baguasquirrel 16y ago

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.

jemfinch 16y ago
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.
- baguasquirrel 16y ago
  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.
- kelnos 16y ago
  Yeah, but a good programmer who thinks he's a great programmer will likely be a pain in the ass to work with.

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 ago
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!
- tene 16y ago
  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'.
  - gojomo 16y ago
    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.

jdoliner 16y ago

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 https://gist.github.com/707639 [edit: link to code]

tomerico 16y ago
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.
- deleted 16y ago
  [deleted]
- 16y ago

ecuzzillo 16y ago

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.