jump to navigation

Using FizzBuzz to Find Developers who Grok Coding January 24, 2007

Posted by Imran Ghory in job interviews, Software development.

On occasion you meet a developer who seems like a solid programmer. They know their theory, they know their language. They can have a reasonable conversation about programming. But once it comes down to actually producing code they just don’t seem to be able to do it well.

You would probably think they’re a good developer if you’ld never seen them code. This is why you have to ask people to write code for you if you really want to see how good they are. It doesn’t matter if their CV looks great or they talk a great talk. If they can’t write code well you probably don’t want them on your team.

After a fair bit of trial and error I’ve come to discover that people who struggle to code don’t just struggle on big problems, or even smallish problems (i.e. write a implementation of a linked list). They struggle with tiny problems.

So I set out to develop questions that can identify this kind of developer and came up with a class of questions I call “FizzBuzz Questions” named after a game children often play (or are made to play) in schools in the UK.

In this game a group of children sit around in a group and say each number in sequence, except if the number is a multiple of three (in which case they say “Fizz”) or five (when they say “Buzz”). If a number is a multiple of both three and five they have to say “Fizz-Buzz”.

An example of a Fizz-Buzz question is the following:



Want to know something scary ? – the majority of comp sci graduates can’t. I’ve also seen self-proclaimed senior programmers take more than 10-15 minutes to write a solution.



Why logic puzzles make good interview questions January 10, 2007

Posted by Imran Ghory in job interviews, recruitment.

Logic puzzles in interviews seem to be one of those things that everyone either loves or hates, but speaking as an interviewer I find logic questions critically important in deciding between candidates – far more than “behavioural” or “situational” type questions that HR peeps seem to favour.

My aim in this post is to convince those of you that hate them, that they are actually useful questions to ask (and be asked) and give everyone else an insight why interviewers especially at big tech companies seem to love this type of question.

To begin with I feel I should draw a separating line between logic puzzles and brain teasers. Logic puzzles are of the type where there’s no “trick” but rather puzzles which have answers that can be logically deduced. Often these are puzzles where there are a number of different valid solutions but you’re asked to find the optimal solution, examples of this type of question include the Rope Bridge and The Orb.

Brain teasers however often have a “trick” – something unusual you have to guess often about the assumptions of the problem. While these can provide some insight into the candidate I think their value is limited, and that they’re far weaker than pure logic puzzles.

I’d like to show what an interviewer can find out about a candidate from a logic puzzle via an example, walking through an interviewer asking the question and showing how various canidates respond:

Interviewer: Imagine you have eight coins, seven of which weigh the same and one that doesn’t (it’s heavier). You need to use a pair of scales to find out what’s the odd one out.

If this seems familiar it probably is, this is apparently one of the most asked logic puzzles in the known universe. It’s used in interviews by Microsoft, Amazon, Google, and probably hundreds of other firms. It’s also in pretty much every book on the topic and on dozens of websites. Now for some example responses:

Candidate Alice: What’s a pair of scales ?

Candidate Bob: How much heavier is the other coin ?

Candidate Carol: Well you could weigh them one-by-one until you find the pair which is uneven, and then….

All of the above responses are good, both Alice and Bob recognized that they had been given a problem they didn’t fully understand so they took the step of asking relevant questions to clarify the problem in their own mind before trying to solve it.

This is a situation that occurs frequently in intellectually demanding jobs, people are frequently asked to solve problems for others. Everyone has different experience and background and will understand the problem differently. This a major advantage, in a team diversity will help you come up with new solutions to a problem. However it also means that everyone will interpret the problem differently, and asking question to clarify what the problem is can be a key part of ensuring everyone’s on the same page.

Carol’s right too, she’s come up with a valid solution right-off-the-bat, it’s not the optimal solution but it is a correct one. We can discuss it and see if she can improve it.

Now a bad response:

Candidate Dan: I don’t know.

If the only purpose of asking logic questions was to catch people who gave this answer, then they’d still be worth asking. This is a candidate you never want in your team. I have three hypothesis about Dan-esqe candidates,

  • They really can’t solve the problem at all
    • This indicates the candidate struggles with problems which intelligent 5 year-olds can solve, not a good sign.
  • They can’t be bothered to try
    • Not a good sign of motivation
  • They don’t want to answer it
    • If they can’t explain why the don’t want to answer the question then their communication skills are probably too weak. In most jobs refusing to do something without giving any reason is likely to be unconducive to a good working environment.

Luckily all three are grounds for rejecting a candidate so interviewers don’t have to think too hard about which the candidate falls into.

So lets look at the next stage of this response, where the candidate has understood the problem and has come up with the trivial solution that Carol has above.

Interviewer: Yes that would work, how many times would you have to use the scale to find the solution using that method in the average and worst case ?

Candidate Carol: Four and eight respectively

Interviewer: Are you sure about that ?

Candidate Carol: hmm, four and ten ?

Carol’s initial response is both a good and bad answer, Carol managed to correctly estimate the average and worst times, showing an understanding of how the speed of the solution depends quite a lot on luck. However her answers aren’t the exact correct values, and worse still when she’s challenged she come’s back with a worse answer indicating that maybe she just guessed.

At this point the interviewer might start to push her on how she got those numbers, if it turns out she starts wildly guessing answers while under pressure, she might not be suitable for a work environment which is pressure heavy and detail-critical.

But now lets move on:

Interviewer: So can you think of a better solution to this problem which lets you use the balance fewer times ?

Candidate Errol: You can split the coins in half. weigh them against each other, throw away the lighter ones, and repeat until you only have one left.

This is a good answer, I’d expect anyone coming from a Comp Sci or Maths background to get this far without any help. People from other backgrounds I might nudge in the right way and see if they can find the solution.

However if you’re from the first group and don’t get this solution I’d be a little worried, it wouldn’t be an instant reject but it’d definitely be a question-mark. Maths/Comp Sci people should have seen similar methods of tackling problems as part of their studies, and should be able to reason about this problem from their previous experiences.

If the candidate came straight to this solution skipping the obvious solution then I’d ask them about the average/worst times for this solution instead. But otherwise back to improving:

Interviewer: Do you think this is the best solution ?

Candidate Fred: I think it is

Interviewer: (smiling) I’ll give you a clue, it isn’t.

Interviewer: You’ve come up with solutions balancing one-against-one and four-against-four, what else can you do ?

Candidate Fred: Three-and-Three ?

Interviewer: What do you learn if you do that ?

Candidate Fred: Which three is heaviest

Interviewer: What if the scale is balanced ?

Candidate Fred: The heavy coin must be one of the other two — you can split the coins three ways every time.

Interviewer: Yep, that’s the optimal solution, do you know for N coins how long it’ll take ?

Candidate Fred: About Log N

Interviewer: What base ?

Candidate Fred: Base 3

That’s typically how the best solution is arrived at by a good candidate. How much help I give the candidate depends how much they’re struggling, some candidates just click about going through the other combinations and come up with the answer. Some like Fred manage to come through with a little help, some candidates just get stuck. I think you can guess which order I want to hire those candidates.

And for bonus points:

Interviewer; Can you prove it’s the optimal solution ?

Candidate Goyle: No I’m not sure how, but I’m fairly sure it is.

Candidate Hermione: Each weighing gives you three pieces of information (if the left side is heavier, if it’s balanced, if the right side is heavier), that is one trit (trinary bit) of information. As the heavy coin can be anyone of the N you need at least enough trits to give N outcomes. Which means you need at least log3 of N goes, which happens to be how many our solution takes. So there can’t be a solution better than the one we discussed.

I don’t really expect a candidate to be able to answer this, but it’s a good sign if a candidate can. People who are solid on the practical side but can excel on the theoretical side as well are rare indeed and it’s well worth identifying them.

So hopefully that’s shown you that there’s a lot of information about the candidate that an interviewer can get by asking a logic question. The interviewer doesn’t just want the candidate to show off their intellect by coming up with the correct answer. They want to see the process by which the candidate got to that answer, as that process is likely to be one that the successful candidate will have to go through frequently during their job.

If you’re interested in learning more about this sort of logic puzzle I’d recommend Moving Mount Fuji (the book; not the task) which gives a good history of how logic puzzles became a part of corporate interviewing. If you’re an (ex)student looking for your first job in the tech sector I’d recommend Programming Interviews Exposed which gives lots of logic and programming questions which are typical in technical interviews.

Unit Testing: The Final Frontier – Legacy Code January 4, 2007

Posted by Imran Ghory in Software development, Software Testing.

These days unit testing seems to be synonymous with extreme programming and test driven development, however unit testing can be much more than just a programmatic way to specify and enforce a spec.

Consider the case where you have some confusing legacy code which you need to change to make a bugfix, the fix itself is trivial but you’re afraid that you’ll break something. If the bugfix is important, you might just have to make the change and hope that if it has negative side-effects they’ll be major enough for QA testing to notice, otherwise you might just avoid fixing the bug instead. If this code was unit-tested you could make the change with much more confidence.

Although the Pareto principle (aka the 80:20 rule) is heavily over-used in software, it does actually seem to apply to bugs in legacy code in a measurable manner. Have a look at your own source code repository and see which functions/classes have had the most bugfix checkins applied, 80% of bugfixes tend to be made to about 20% of the code. There’s sound logic behind this – often that 20% of the code is poorly written with dozens or hundreds of “special case” hacks.

Whether this bad code arose out of evolutionary effect or just poor coding practices the end result is the same: Unreliable code which takes far more effort to maintain then it would be just to rewrite or refactor.

However developers are often so afraid of the consequences of making a mistake they suffer the consequences of “refactoring paralyisis” that they’d rather perpetuate the bad code by adding hacks rather then trying to improve the code.

Hopefully I’ve convinced you of the practical usefulness of having unit tests for legacy code and now have you asking the question: “How can I unit test code if I don’t understand what it does ?”

The answer is surprisingly trivial, but if you come from a TDD background you may well have overlooked it. When unit testing legacy code you don’t need to understand what the code should do, you only need to be able to observe what the code currently does.

You don’t break legacy code by making it’s behaviour incorrect, you break legacy code by make it’s behaviour different. Given the code is currently behaving correctly (in a general sense anyway) you can use the current behaviour to establish correctness for your new code.

The best part of this type of testing is that in most languages you can automate the generation of this sort of regression unit test. I’m not aware of any mainstream packages which automate the process, but for most languages it is fairly straightforward to automate this process yourself.

For example while I was working on some legacy C code I wrote a perl script which did the following:

  1. Read in the header files I gave it.
  2. Extracted the function prototypes.
  3. Gave me the list of functions it found and let me pick which ones I wanted to create unit tests for.
  4. It then created a dbx (Solaris debugger) script which would break-point every time the selected function was called, save the variables that were passed to it and then continue until the function returned at which point it would save the return value.
  5. Run the executable under the dbx script, and which point I proceeded to use the application as normal, and just ran through lots of use cases which I thought would go through the code in question and especially cases where I thought it would hit edge cases in the functions I want to create unit tests for.
  6. The perl script then took all of the example runs, stripped out duplicates, and then autogenerated a C file containing unit tests for each of the examples (i.e pass in the input data and verify the return value is the same as in the example run)
  7. Compiled/Linked/Ran the unit tests and threw away ones which failed (i.e. get rid of inputs which cause the function to behave non-deterministically)

Although the above looks fairly complex, it was only about 200 lines of hacked together perl. The resulting tool let me rapidly create regression unit tests.

Obviously it has problems with some situations (functions accessing external resources, global variables, structs containing pointers) but none of these are insurmountable and could be worked around by writing a more sophisticated script without a vast amount of effort being required. Even this very primitive approach resulted in a set of unit tests that have proven themselves by spotting mistakes that I accidently introduced while working on legacy code.

If you’re working with a more modern language in which most classes/types are serializable and in which you don’t have pointers then you may well be able to avoid many of the problems the simplistic approach above has.

One common question I’ve had about this approach is of how to test functions which access external resources, one simple method is just to record the input/output from a live run and just create a dummy function which acts as a black box mapping a fixed set of inputs to outputs and then have that called instead of the real function.

With most languages you can do this fairly straightforwardly without having to change the code you want to test. How to do it is fairly language specific (for example in C you could link in your alternative functions or use the pre-processor to replace the calls to the real function with calls to your replacement) but your local language lawyer can probably help.

Hopefully in the future tools which can generate these sort of tests will become available commercially or in open-source development toolkits and eventually end up as common as debugging and profiling tools, but in the mean time you’ll just have to roll your own.

It can be a pain and require a lot of language expertise to write a program/script which automatically generates this type of test for yourself, but from my experience it is well worth it.