Programming Challenges For Interview

When interviewing it does matter what their CV says, it does matter how good their references are, and it does matter how well and clearly they express themselves. It also matters how well they program for real.

It doesn't matter if they know the difference between varchar and varchar2 or if they know what JCA stands for. What's important is that they must be problem solvers.

In the spirit of "Hiring a Juggler", here is a small selection of the programming challenges that could be set for a potential recruit.

In language of choice, write a routine that reverses a string in place
- Now write a routine that reverses each word in a string
(words are characters separated by spaces)
- Now write a routine that reverses the order of words in a string
Write a program to solve the TelegramProblem
Write a program to solve the OddWordProblem
Write a binary search routine that returns the first occurrence of the key
- If it is recursive, convert it to non-recursive, or vice-versa.
- Now write another that returns where the key should be inserted if it is missing
Find the length of a linked list, or report that it has a loop
- Solve this with a fixed amount of additional storage
Sort the linked list in place.
Given a function f that takes a real and returns a real, find a value x such that f(x) is zero
Find the longest monotone subsequence from an array of numbers. A sub-sequence is any X[j[1]], X[j[2]] ... X[j[k]] where the initial array is X[n], k<=n, 0<=j[i]<n, for all i:0<=i<n and j[i]<j[i+1] for all i: 0<= i < n-1
Write a program that given the time of the day (hours, minutes) returns the angle between the hands on a clock.
- Be on the lookout for them asking if they should return just the smaller angle, and the "clever" solution that just outputs 0 because the hands are parallel.
- See AngleBetweenClockHands
Write a function that will solve the leader election in a ring. All processes must run this same function and one and only one of them must be elected leader.
Convert the "problem solving flowchart" into structured programming. (Google it if you don't know what that particular flowchart is.)
- If the candidate has to Google it, don't hire them.
Assume you have an array of miscellaneous integers, including negative numbers. If you are to sort with a command-line utility that can only sort text rows alphabetically (ASCII), what format would you output the array to a file to be used by this command-line sorting utility to get numerical order of the rows? (Let candidate have an ASCII chart for reference per collating.)

Once the code is written ask the potential recruit: Where is the bug?

Note that some of these are deliberately vague. We are checking not just the programming capability, but the analysis and communications skills. What clarifying questions are asked can be just as important as writing the code.

The above seem appropriate to ask someone fresh out of college interviewing for a junior position, but it won't tell you anything about whether a senior programmer has the qualities needed for a senior person. Unless they fail, of course, but why not set them a senior level problem to succeed or fail with? Otherwise you're wasting valuable interview time on something that gives very little information upon success.

[This is simply not true. Such an exercise gives you a lot of information for a relatively short amount of time. If the candidate can't solve (for some value of 'solve') it, they are just not senior programming material, and you are done. However, assuming they are, the process of discussing the problem will give you insight into how this person solves problems, and how they design (a good choice of toy problem will allow obvious generalizations, which this person should see). Certainly this isn't the *only* thing you should ask, but inside the time constraints of an interview it is only a simple problem that you can expect to see a detailed solution of. Other lines of questioning should probe design, portability, developer interaction, etc. issues - but you just won't have time to do everything that would be useful. The 'toy problem' question is just one tool, and a useful one at nearly every level.]

Once the code is written ask the potential recruit: Write the unit test for this code

Discussion please to follow. Please keep above the line in DocumentMode.

Write a binary search routine that returns the first occurrence of the key

I missed this at an interview. Hard to remember if you use libraries for this sort of stuff.

: (added later) I've never seen a library that implements this function. Note that it asks to return the first occurrence.
: (added still later) The C++ library very nearly implements this function. What it does implement is to return the lowest position at which a given value can be inserted into a sorted sequence without violating the ordering. This position is the position of the first element with the given value if such an element exists; otherwise it is either (one past) the end of the sequence or the position of the first element greater than the given value. So you can solve the problem by calling this function and then checking whether the returned value is off the end or refers to an element unequal to the given value.

Sorry, but I don't understand this. Are you saying that you never implement algorithms from descriptions?

The last time I implemented a binary search routine was in college. I've never had to do it on a real project because there are always libraries to do this sort of stuff. I couldn't just remember it from scratch. I am just not a man like you.

[Well, I guess you'll be fine, as long as your programming career never requires implementing algorithms. The point is not whether you can remember it, but whether, given a description, you can implement it. This sort of thing is pretty basic - you should be able to derive it without much trouble (in an interview, bug-free is probably a bit of a stretch).]

He may also need to settle for lower salary or he may lose to better candidates. Somebody who whines about having to write a binary search for the purpose of an interview should never ever get the title of senior software engineer. Unfortunately many do. So that's why Doug's claim that presenting the OddWordProblem is insulting is faulty: the "senior" title has been diluted beyond recognition to the point where we can't know on average if a "senior" is better than a [graduate] fresh out of a (good) college.

[You misunderstand. (A) I wouldn't criticize using binary search as an interview problem; as it says on ProofsCanBeSimple, "it took 14 years for the published literature to come up with a bug-free binary search". (B) I'm suggesting that harder problems be given for senior positions, not merely that easy problems should be avoided.]

[And yes, one should reconstruct binary search merely from the principle of divide and conquer, not try to memorize it! (But there's reason to think, as noted above, that most [attempts to write binary search] will have minor bugs in it, and that is just to be expected)]

Why would it be expected?

[Quoting from the uvic.ca URL below: Bentley said "Although the basic idea is simple, I have always found the details tricky - I once spent the better part of two days chasing down a bug hiding in a short partitioning loop."]

[For those who find this claim about binary search hard to believe, here's one handy reference online, if you don't own Bentley's book yourself (Bentley was quoting Knuth): http://www.cs.uvic.ca/~vanemden/teaching/sweng/webnotes/1.cleanroom.txt]

If you still don't believe it you can try BinarySearchCodingChallenge?.

If it is a more senior position, ask their opinions and justifications for HolyWar topics.

For example: "Do you feel that programming bugs are inevitable?" The important part of the answer isn't the "yes" or "no" part; it's the justification and support of the answer that is more interesting to me. For example, as an interviewer, I would probably give negative points for either "Yes, because no one's perfect." or "No, because if you have bugs in your code, it's because you're not trying hard enough." So far, the answer I would probably come up with is "Yes, but with a combination of individual discipline and practices, group discipline and practices, the bug rate in the released product can get asymptotically close to zero - if that's the overriding goal of the project." And if I were an interviewee and gave that response, and the interviewer didn't pump me for more details, I would probably give that company negative points. -- TimLesher

Good point, as long as you make it clear you're looking for more than a yes or no. It's important to make sure you ask exactly the question that you want answered, rather than expecting the candidate to know what you want. They doubtless have interviewed with both reasonable and unreasonable interviewers, and can't know exactly what sort of answer is wanted unless one is clear.

Find the length of a linked list, or report that it has a loop

Solve this with a fixed amount of additional storage

Is it possible to do this with a fixed amount of additional storage without mutating the data structure in some way?

Is that algorithm widely known enough to expect candidates to have run into it? I don't think it's obvious enough to expect someone to reinvent it if they hadn't heard of it. (You mean chasing the list simultaneously at half speed and full speed for cycle detection, right?)

Yes, it's that algorithm. No, I don't expect every candidate to invent it for themselves. Interviews are not examinations, they are dialogues. As an interviewer I am looking for information. These programming challenges form the subjects for the dialogues, the candidate's thoughts, ideas, discussion and responses gives me information about how they work and whether they'll be of value in my context.

One can always trade time for space even for silly interview problems with silly constraints.

The problem I have with the questions on this page is that they're all about inventing little algorithms. That's fun and well-covered in school, but I don't see it as having a lot of relevance in the real world. I'm much more interested in the candidate's ability to communicate, to design, to test, and to create code that embodies these three things... and to do them well under schedule pressure.

The questions above aren't like asking a juggler to juggle; they're like asking a juggler to make his own juggling balls. Interesting, and probably covered in juggling school, but only occasionally relevant to the job.

Unless of course the job is about inventing algorithms. In that case, you'll probably be hiring somebody with a hard-core math/CS background and you'll ask them questions that are a lot harder than the ones above.

-- JimShore

Interviewing is a difficult process; you are trying to learn a lot about people in a short time. One of the things programmers do is invent little algorithms, and the process of conceptualizing and solving such a toy program *is* relevant, even if the problem isn't. I certainly wouldn't hire someone on the basis of a test like this - on the other hand, I would certainly *not* hire anyone who couldn't do it (where 'do it' is somewhat flexible). Questions like this are just one tool in the interviewing tool box, and an effective on if used correctly.

The candidate's ability to communicate, design, test and create code is exactly being discovered in the act of working with them to solve a problem they haven't seen before. That's why you need an arsenal of these little challenges, to find one they haven't seen and work with them to solve it.

: Exactly.

I prefer a PairProgrammingTestDrive (working on actual production code). It's relevant and it exposes the candidate's ability to learn, think about big-picture design, absorb information quickly, engage in collective code ownership, work in a pair, engage in TestDrivenDevelopment, and write the kind of code we need.

I've encountered a lot of programmers that can crank out a good, readable algorithm. Programmers that can think in terms of objects, refactor a large system, and turn complex requirements into simple, maintainable code are a lot harder to find. Success at writing an algorithm doesn't tell me enough about the candidate.

-- JimShore

It seems there is a major missing piece in the above. How does one evaluate the results of these "challenges"?

They're not tests, you don't get a score. They are intended as an activity used for an interviewer to interact with the candidate. The assessment is then the interviewer's. The question is: "Will this person be able to perform the tasks I want them to perform?" and the answer depends on the job at stake. There is no right and wrong, there is no single answer, there is no single evaluation that can be applied.

If the results of the test are without meaning, why do them? Why waste everyone's time doing trivial tasks if the tasks do not aid in evaluation?

[The process used in solving the task is important; the task in and of itself isn't. In my experience, people who are highly resistant to this sort of thing tend to be insecure about their skills. How do you evaluate the challenge? You evaluate how the person addresses the task. Do they rush into a sloppy solution then try and fix it? Do they analyse the problem before hand? If so, how? How do they critically evaluate the solution they have arrived at and decide it is correct (or not). How do they communicate what they are doing /have done? Do they ask you questions? If so, are they insightful? All of these things are valuable clues as to the person's capabilities.]

7. Given a function f that takes a real and returns a real, find a value x such that f(x) is zero

Do you really ask job candidates to solve an equation?

Nope, I ask them to solve a problem. I watch how they go about dissecting a problem, breaking it down, looking at it from different angles, tasting different possible solutions, and choosing among them. I watch someone work.

If the results of the test are without meaning, why do them? Why waste everyone's time doing trivial tasks if the tasks do not aid in evaluation?

If you need a checklist or numerical score, I might use something like this:

Did the applicant (yes is good, +1 point)

look interested in the problem?
ask to clarify context?
ask to clarify requirements?
explain their assumptions?
explain their reasoning?
explain what they don't know?
explain where to look for what they don't know?
consider multiple alternatives?
write code that was visually clean?
write code with correct syntax?
write code that worked?
write more than one implementation?
walk through a specific case?
walk through boundary cases?
code a test case?
code more than one test case?
code the test case first?

Did the applicant (yes is bad, -1 point)

provide a single answer?
provide an instant answer?
provide an instant, wrong answer?
appear dismayed, angry, or offended?
fail to understand the problem?
refuse to work on the problem?
explain things in an unclear manner?
use lots of buzzwords?
insist on a specific interpretation?
argue about the requirements?

I can testify that in my informed opinion the above list is irremediably flawed. It is so defective and misguided that it is not worth a proper criticism, I'll just post my opinion about it. In any case, it was contributed anonymously and without justification (as if it ought to be recognized as self-evident). -- CostinCozianu

I agree with Costin. The judgement of such things as positives or negatives depends on context and must be interpreted in light of the justification for such criteria. For instance, it matters whether they answer instantly because they dislike thinking hard about new problems, or because they are already extremely familiar with the issues. Etc ad nauseum.

I also think that interviewers who use simplistic critera like that deserve some negative points of their own. Interviewing should include thinking and careful assessment on the side of the interviewer as well as that of the interviewee, not just kneejerk reactions based on unquestioned conditional reflexes/prejudices.

Also, if you ever meet a perfect candidate, who has no flaws whatsoever, the odds are that they are much better than the interviewer, who isn't always qualified to even recognize perfection if they hypothetically ran across it. It's much more often important to recognize positive qualities, than to be overly anxious to discover deal-breaker faults. -- DougMerritt

I don't think this point has been made so far. One of the reasons for asking questions in an interview (programming questions, design questions, questions about pointers to arrays of functions in C) is to verify that what is on an interviewee's CV is not a fabrication. I admit that this is a hard thing to do, but I think that finding out whether an interviewee is 'enhancing' his CV is a laudable goal. If they say they have 5 years C, and they fail most of the C tests, then you've got a potential problem. I'm not saying that you wouldn't hire them, but you may want to contemplate the wisdom of hiring someone who has 'lied' to you. -- MatthewFarwell

There is too much array and list diddling in the list. I'd prefer to also see some "big picture" problem solving, especially for non-beginner interviews. Perhaps some debugging problems would be more realistic, especially if the person they are replacing left behind mounds of dumbshit code.

Another kind of question to consider is select some HolyWar topics and ask the candidate for their opinion on such. It may reveal their thought process. Their response may not match your preference, but it's good to know if and how they decide between multiple design decisions.