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.
In my life I never got interviewed, even if it is 15 years I work as a programmer. Now I work at VMware thanks to Redis, and VMware did not requested an interview, and my only previous not-self-employed position 10 years ago was likewise triggered by my work on hping.<p>But, I'm sure, I would suck so much at this kind of interviews. If you are anything like me you'll understand what I mean, in topics where I work day by day I've pretty much the control of what the good solution can be in a few minutes, but for many things to find the best solution requires, at least for me, days of thinking, sleeping, possibly waking up with the solution in mind, to find it's wrong and you need to reiterate the process.<p>My design abilities are all there, in this days. I'm sure that in the five minutes race I would say many times something of super stupid. Now my question is, are the five-minutes performances really linked to the three days thinking about your problem solution?<p>Isn't it possible that at least a subset of guys that will get the few-days answer well, will instead provide a poor answer in little time, and sometimes the other way around?<p>If this can be somewhat true, there is a huge industry selecting runners for 100 meters, in order to run, most of the times, a maraton.
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.
My last internship in college involved working on thermostat systems for Honeywell with a bunch of people who had been there their entire professional careers. I didn't have much interest in becoming a lifer and ended up interviewing with a couple other companies, including Microsoft.<p>I interviewed for a Program Management position in the Visual Studio group. My first interview was with the Design Manager for the VS product line. Her final question for me was about building an effective temperature control system for a new house. I launched into a 5 minute analysis of the advantages and disadvantages of a wide range of HVAC systems, obvious ramifications from open floor plans, and so on.<p>A month later, we sat down for lunch as co-employees for the first time, and I told her the whole story. She got a big laugh out of it. I guess she didn't realize that's what I'd spent the last few months working on.
Angry because neither the hash table or the prime multiplication would be as fast as a boolean array indexed by the char value. As an added bonus, the boolean array actually makes the most intuitive sense.
Stories like this and the comments that follow just reinforces my belief that I am no where near smart enough to work with most of you guys.<p>Plus I'll never wear leather pants. That can't be comfortable.
If you are ever asked an interview question which you've already answered in a previous interview, you should tell the interviewer immediately.<p>I know some coworkers who will intentionally ask a question they know you were asked in a previous interview to test your integrity. (Edit: Not that I would condone this practice either.)<p>These types of interview questions are about evaluating <i>how you think</i> far more than <i>what you know</i>. So, more importantly than the risk of getting caught, if you recite an answer from memory and pretend that you're deriving the solution on the fly, you're lying to your future coworker.
I feel like most engineers rarely have to try too hard to get a decent job, but I wonder if it's because of stories like this. I've been on the interview circuit a handful of times so far in my life, and aside from the first time when I was mostly clueless ("So where do you want to be in 5 years?"; "Man, I never think that far ahead."), I feel like interviews have become a very routine process of answering a similar subset of questions over and over again. Am I being hired because they've made a true evaluation of my technical skills, or was I just serendipitously lucky to have heard the answer to how those 5 pirates are going to split those 100 gold pieces?
I have been in a similar situation, where one interview's curveball ended up being asked in a subsequent interview.
I went through the same emotions as the author (including resisting the urge to grin from ear to ear). But like an idiot, I answered with the trick answer right away (though I was calm about it). I then told the interviewer that I had learnt it in a previous interview.
It turned out he was looking for the clever answer too; and he was disappointed that I knew it. Maybe he felt I wasn't sufficiently "excited" about the clever answer, but I never got the job. Which is not too bad, since that outfit wasn't my first choice anyways.
I was asked that exact same question over a phone interview.<p>One of the most interesting questions given to me was, write an algorithm such that given four colors and a rectangle, fill the rectangle with a gradient using a color in each corner. After the fact it wasn't very hard, but having never thought about such a problem, it was pretty difficult white boarding it out. It was a pretty good question because I think that most people aren't thinking or preparing for such a problem, instead opting to study arrays, linked lists, trees, sorting algorithms and running time. You really get to see how a person thinks with it.
I've had something similar happen to me at a Microsoft interview. The interviewer asked me a question I explicitly knew the answer to, and it too wasn't "my" answer to the problem but the one I've heard in another interview. So I just told him: "I know this one. Can you ask me something else?" He told me he appreciated my honesty, and didn't have any other questions.<p>I got the job.
Personally, I would be more inclined to hire a person picking the "throw it in a hash and look it up" solution over any more complex solution. My reasoning is that bad programmers tend to get lost in nuance, or don't understand a problem. Good programmers tend to reason through the proportionate value of a problem. I'm not saying nuance is always a bad thing, but it's probably not what your company is developing unless you work for a math department.
I hate such stupid tricks, frankly a hash table or an array for a restricted domain is way faster, since the whole data structure gets cached on the L1.<p>I can solve the same problem by using statistical thermodynamics, and show its only o(1), since each string is a configuration of the system and finding common alphabets is like finding degenerate states.
The point of the story is not the actual problem that author had to solve, which we have been discussing (but again, its _hacker_ news, after all :-)), but basically to tell how interviewing experience, even at which you fail, prepare you for better.
Hum, Guy's solution is really terrible, division, multiplication and modulo are very expensive operations, and completely unnecessary here. This is basically a case of "I'm clever and you must think like me to be in my team". Uh no thanks.
It is strange how every time someone interviews at Google they feel compelled to write "their" story and share it with the internet.<p>How many stories like this are out there now? Hundreds?
I paused a bit before reading about the possible solutions, and actually thought of the (prime number) solution the interviewer came up with.<p>I realise that this is a bit of redundant post .. but, as a person who isn't a brilliant coder I surprised myself. But then again, after reading the comments here - I think maybe I just have an obtuse way of thinking about things.
I'm guessing that the guy in the leather pants probably got the idea from reading about Godel numbering. If you're interested in this, you might like this book: <a href="http://www.amazon.com/Godels-Proof-Ernest-Nagel/dp/0814758169" rel="nofollow">http://www.amazon.com/Godels-Proof-Ernest-Nagel/dp/081475816...</a>
I kind of wish that he didn't emphasize the 'women engineer', would've kinda gotten the picture when he starts using she.<p>Maybe we'll get there someday...