"Swapping two variables without a temp" is a bad question, because it depends on knowing the trick.

"Find the 2nd-highest element of this list" is a basic question, and I can change it up it a zillion ways such that anyone trying to just learn all possible permutations will end up doing way more work than someone who can just figure it out on the fly.

From there you can say that works fine with pen and paper but why might it go wrong in a program? So how do you avoid integer overflow? If the signs are the same then use subtract first else use addition first. After we have done that. After this step assume I have returned to the main flow. How do I check if I should use addition or subtraction? If a is bigger than b I must have added so use subtraction. Writing the algorithm this way is trickier than xor. The problems to be solved are to do with understanding concepts

Next you have the xor solution but more important than getting the answer to that might be to see if they can see that the two functions are like encrypt and decrypt where a is the message and b is a key and a + b is the ciphertext c - so that f(m,k) is encrypt and g(c,k) gives the message and g(c,m) gives the key. If they have had any exposure to cryptography then xor should present itself.

If they give xor straight off then you can work backwards.

Those tricks might be valuable in your workplace, and may make excellent interview questions for you, but they are a very very different type of question than fizzbuzz, at least in purpose, even though they may look superficially similar. In a fizzbuzz type question, you are not looking for brilliance, you are looking to just weed out the people who can't.

The fact that they're involved enough in the industry to know about fizzbuzz is still a strong signal. It will only come up if participate in some sort of developer community, which, I suspect, is something that the completely incompetent don't do, as a rule.

Once again, it's not designed to find the top talent. It's merely a high pass filter that removes the hopeless from the set of people to consider.

But even if fizzbuzz is something that the hopeless start learning by rote, switching it out for any other trivial problem will still work. "Count the number of 'a's that come after 'g's in a string", "print the lyrics to 99 bottles of beer", or hundreds of other problems like that are just fine for the task.

I'm sure it is useful in some situations, particularly in big companies with a broken hiring process. I imagine 37Signals don't find it useful as they have a more effective screening process, and people coming to interview simply couldn't possibly be that bad as they're referred or they've seen some code they wrote.

If you are really faced with candidates who are incompetent (i.e. HR has filtered candidates for you based on CVs or similar), I think I'd try to automate some kind of online quiz they can go and take before they're even allowed to apply (which can include fizzbuzz or whatever little puzzles you want, checks for cheating etc) - then you can spend the phone screen or interview actually talking about interesting stuff which is in the problem domain they'll actually be tackling and finding out what they'd do with it. I just suspect these questions can be gamed and are not necessarily weeding out all the undesirables, just those who haven't done any homework on your hiring process.

I've seen people hired who talked a good game and could have passed these trivial tests without giving away that they'd just read up on likely ones, but were lacking in all the skills necessary to bring projects in on time and competently - that sort of mediocre candidate who lies about experience and knows the basics is far harder to stop.

It's interesting how different people react to IQ tests or little programming tests though - some people hate the implication of jumping through hoops, and that ability/knowledge can be reduced to such simple set of tests, and resent being subjected to them. Others really don't care and find them interesting or at worst trivial. I'd find it kind of weird trying to guess in an interview if someone who asks for say 'select the second highest number in this list' just wants a quick solution like list.sort[list.count-2] (which in the real world would be the first choice until or unless you are likely to hit major performance issues), or if they want you to write a trivial sorting algorithm for them and explain that you're familiar with the content of an undergraduate CS course.

It's also interesting seeing the range of different interview questions posted here as examples - some are trivial filters as you say, some are more involved, and some require knowledge of basic undergrad stuff, so I'm not completely sure that all of these puzzles are intended as completely trivial, there's always the temptation to elaborate them into some kind of exam (like those posted on HN a while back with maths questions) for esoteric knowledge which is frankly useless in most people's job.

"Sort and take the second highest" is a fine first answer. I'd expect most good candidates to start with that. I'd also expect them to say "but I think I can do better" on their own.

Presumably you mean better given infinite memory to store all the records and a very large number of records? Because for most small collections of say a few thousand, a sort then select would be better than an iteration IMHO as it is simpler and the intent is clear if performance is acceptable. Perhaps I have misunderstood the intent of the question though, I'd be interested to hear what you feel is the ideal answer.

I have patience for candidates, but not an infinite amount. If they keep on trying to come with reasons why they don't need to improve their answer, or try to drown me in a sea of bullshit, that's a no-hire. I'm screening out assholes and prima donnas as much as I'm screening out people who can't code.

Upon being told that "sort and take the second element" isn't good enough, I'd expect the candidate to come up with a linear walk through the code, keeping track of the two top elements.

I'd then ask the candidate to generalize it to "the #n element" instead of "the #2 element," which will probably require a new data element. Keeping those n elements in a sorted list is a fine way to start. A really great candidate would ask if they could re-order the elements as they find them (doing a partial version of a quick sort) or use some variation of a heap-sort with limited space.

If sort first was too slow and it had to be done in memory, I would have iterated once and kept the results in an ordered list but not sorted the records during iteration as you have suggested, didn't think of that. Thanks for clarifying.

And this is why looking at actual code someone wrote is a good idea - because there are things one cannot check during the interview, like how well the candidate structures the code, how well he writes comments, how does he manage the complexity of a growing codebase, how quickly he can learn a new library or tool and so on.

In this particular case I'd probably know that "doing better" means algorithmic complexity, but I would never come up with "but I can do better" remark myself. It's also possible that, when asked to "do better", the first thing I'd try to do would be to write unit tests and docstrings. Is this unacceptable? Would I be seen as an asshole or prima donna?

Also, there's an issue of me being able to come up with a "correct", "better", faster in terms of Big-Oh algorithm. I am not a genius, I know this. I am not and I can not hope to become Dijkstra. I'm also not a computer scientist. I worked hard to be able to read and understand and then code algorithms presented in papers, but I'm damn sure I couldn't come up with even the simplest of them. For example just last week I had to implement a scheduling algorithm called "highest response ratio next". I was able to look it up in the sources, understand it and implement it in a product, but I am sure as hell that I would not invent it during an interview. Does it mean that I'm not qualified for a job? Would I be seen as dumb?

Posts like danielweber wrote above make me nervous. It's probably not what he had in mind, but it seems to me like he would not hire me - and I work in "the industry" for almost ten years now and I have been programming for twenty. I can brush this off as irrelevant - I have a job that I'm proud of and happy with, but what a young, aspiring programmer has to feel when he gets told that he's no good, no hire, because he can't invent algorithms on the spot?

So I don't mind answering questions during the interview process. The candidate might be nervous and I should be clear about my expectations. I don't like mind games like picking a fight and making sure the candidate responds the "right" way.[1] I would hold no points against them for asking on clarification for what "better" means, as long as I didn't they they were trying to be difficult and accepted that faster was better.

I'm sorry if you don't think I would hire you. Maybe I wouldn't, but that doesn't mean you aren't a good coder. But I also think you shouldn't be intimidated by "algorithm invention." You probably do this a bunch already. In the order you write your code you are probably already doing implicit algorithm invention. I think you can write the code to figure out the biggest number in a list if you sit down to do it, and once you do that finding the second biggest just involves keeping track of one more thing and doing one more test on each pass through.

Often the question is figuring out what data structure you should be using.

Oh, I don't actually expect anyone to give me the perfect answer of how to find the nth-biggest element in the list. In fact, if a candidate did give the perfect answer, I would say "this person is more qualified than me, please hire." I'm not capable myself of giving the perfect answer even though I've thought about it a few times and it's essentially a question I've practiced.

[1] See question 7 at http://www.joelonsoftware.com/articles/fog0000000073.html

Ok, I thought it was being written as a code, even if just on paper or a board.

"accepted that faster was better"

The point we - grey-area and I - are trying to make is that it's not always the case, or rather that the "betterness" of faster implementation is, in practice, dependent in large parts on other characteristics of the code. If someone deleted slower implementation along with tests and docs and replaced it with faster, but undocumented, untested implementation I would not consider it a change for the better.

And I think you would agree with this in general (of course there are situations when a change like this is necessary!), and I think this is just a misunderstanding on my part - I was thinking about actual code, an implementation, all along while you were talking about description of the algorithm with words. In this case - with one additional assumption that memory complexity is irrelevant or not changed, but that's nitpicking - of course faster is better! :)

"I think you can write the code to figure out the biggest number in a list"

Yes, of course: (foldl max (first lst) (rest lst))

And I can even explain what foldl is and how it works.

"you shouldn't be intimidated by "algorithm invention.""

I am not "intimidated". I know my limits. I wouldn't be able to invent quicksort during the interview and I wouldn' be able to invent this: http://www.jstor.org/discover/10.2307/2346806 even if my life depended on this and I was given all the time of universe to do this (but I still coded it).

This also depends on what we mean by "inventing". Does using some previously learned technique or adjusting other already known algorithm count as an invention?

But from what you say I gather that you wouldn't want me to invent quicksort on the spot - and then it's ok, it seems like I still have a chance of getting a job! ;)

A great thing a small company can do to find people is sponsor a users group of some sort. If your company does Java start a JUG, Ruby start a RUG, etc... For the price of some pizza you can informally meet people that by the nature of showing up give a strong signal as people you may want to talk to when looking for your next employee.

It's certainly possible that some of the people who completed FizzBuzz are not good programmers, but it seems pretty clear that the one person who failed it cannot possibly be a good programmer.

Having people go through FizzBuzz (which generally took 5-10 minutes per person) saved us the trouble of a longer interview with more people for at least one clearly unacceptable candidate.

a = a + b

requires the (invisible) presence of a register where a + b (or xor or whatever) is placed right before being written back to a. But then you might as well use this register directly for the swap instead of dabbling around with one-to-one functions.

    $ irb
    irb(main):001:0> a = 1
    => 1
    irb(main):002:0> b = 2
    => 2
    irb(main):003:0> b, a = a, b
    => [1, 2]
    irb(main):004:0> puts "#{a} #{b}"
    2 1
    => nil

  a ^= b
  b ^= a
  a ^= b

($a, $b) = ($b, $a)

That isn't a "puzzler", in any way, shape or form. It is quite literally "write the most basic, simple, trivial program possible". There is no trick to it, no gotcha, no special information that makes it suddenly go from hard to easy. It is always easy, and is a practical test of actual programming knowledge.