Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've had an argument recently with a fellow programmer. He was interviewing for a new position and was asked this question:

Give a sequence of numbers starting at X and ending in Y but with one element missing so N is Y-X-1, find the missing element in O(N) or better.

Now, the answer is irrelevant here (but interesting). This started a discussion on whether this was even a good question to ask during an interview.

One side: Algorithms are an inherit part of programming and a candidates ability to answer this question supports that this candidate will be a good programmer and be able to solve larger problems and can handle most programming tasks which are ultimately easy to understand and answer.

Other side: Writing algorithms from scratch is rarely used in modern programming and therefore is irrelevant in the bigger question of whether the person will be a good programmer. A person could successfully answer this question yet still not be able to do more common programmings tasks.

Your thoughts? Good interview question or not?

share|improve this question

closed as primarily opinion-based by gnat, Bart van Ingen Schenau, MichaelT, World Engineer Jul 23 '13 at 14:14

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

    
I'm sorry, but I can't understand find the missing element in O(N) or better What does mean "or better" in this context? It seems the kind of thing that would be solved with a simple while loop, but anyway I don't understand - it's either solved or not solved, right? –  Camilo Martin Nov 22 '10 at 18:27
    
The "or better" refers to the performance - an O(ln(n)) solution would be better. –  Ethel Evans Feb 10 '11 at 18:44
    
Algorithm questions are in fact, one of the expected questions in a programming or technical job interview. Gayle Laakmaan McDowell has written a book called "Cracking the Coding Interview" which has a dedicated section on algorithms. –  hagubear Jul 23 '13 at 7:07
    
add comment

9 Answers

I agree with asking a algorithm question, but I disagree with insisting on a specific big-O quality level.

Asking this sort of question is interesting to see how the person approaches the problem and what pitfalls they consider in their attempt, but unless they are writing something insanely incorrect or inefficient the actual detail of what they write is not as telling as the fact that they get through the problem solving / design steps in a coherent manner.

I ask a similar question, but the people that I have had the best luck with after hire are the folks that gave flawed answers but had the correct idea in their approach.

share|improve this answer
add comment

I would disagree with the idea that the ability to write algorithms is irrelevant in the bigger question of whether the person will be a good programmer. Even if he never has to use it, (which is doubtful,) it still shows if he has the mental flexibility required to work out a logical solution to a problem that's more complicated than a simple set of requirements that's already written up and laid out in detail by the client.

I'd definitely not want to hire someone who doesn't know how to think and analyze. That's what makes the difference between a code monkey and a computer programmer.

share|improve this answer
add comment

I have several algorithm-like questions that I use on a regular basis, some of which are very difficult. I use them to see how they mentally attack a problem and to see if they grok certain concepts. (I've seen way too many developer candidates who just don't understand pointers.)

share|improve this answer
    
Pointers, like, the dog, right? :) –  JoshD Oct 26 '10 at 2:08
add comment

I agree that programmers must know algorithms very well, even with fancy new frameworks, but I'm not totally convinced about a brain teaser in an interview. My biggest concern would be that in a real environment, you write algorithms under very different conditions; aka, not under pressure with someone watching you every penstroke, with at least several minutes to think it over in silence. For those who advocate this evaluation method, how long do you generally give the person to solve it? I believe code is not so much about cranking out a solution in a feverish 3 minute terror, so convince me that this is actually a good way to see how someone will handle an everyday task.

share|improve this answer
add comment

The problem with that specific question is that it's almost a trick question. With one particular insight, you'll easily come up with O(n), otherwise you'll struggle to get better than O(n log n). It almost reduces to "Have you seen this one before?"

I'm not sure there are any good algorithmic questions. If you asked one based on graph theory, say, it would depend on how familiar the interviewee was with graph theory - and, if you hire him or her, he or she could be up to speed on graph theory fairly quickly. Again, we're back to "Have you been exposed to this before?"

There isn't time in a regular interview to do serious problem-solving, and I approach things differently when I can sit down, use Wikipedia, and generally take some time to figure things out. There probably isn't time for the interviewer to carefully discuss what the interviewee knows in detail and pick out a suitable algorithmic question.

share|improve this answer
1  
What is the particular insight to seeing it's O(n)? I see "searching a sorted list of N sequential values for one that's missing" as inherently a O(n) problem. How could you write it so that it was worse? (Honestly, I'm curious and don't see how the O(n) solution is non-obvious, and even the O(log n) one seems obvious to me.) –  dash-tom-bang Sep 30 '10 at 18:56
    
@dash-tom-bang: I wasn't thinking of the list as sorted (did I misapprehend something?) so the O(n log n) solution would be sort and scan, while the O(n) would be sum the numbers up. –  David Thornley Sep 30 '10 at 19:29
    
ah- ok that could be the case- I hadn't considered that the list would be unsorted. :) ("List starts at X and ends at Y.") –  dash-tom-bang Sep 30 '10 at 21:15
2  
A variant of quick-select also works here. Pivot on (top + bottom) / 2, and it's easy to see which half the missing entry is because you know how large each half should be. Repeat until you find the missing element. –  Anonymous Nov 6 '10 at 13:24
1  
I think that as the question refers to a sequence (rather than a set, etc) starting at X and ending at Y it implies that items are sorted. It does seem a rather trivial question. –  FinnNk Aug 5 '11 at 7:59
show 1 more comment

I like algorithm questions, because it's what we do. I like constraints, because it's what we use. Big-O is especially relevant in my industry.

I do not like requiring the answers to these sorts of questions to be "write the code on the whiteboard". The interviewee should be able to talk intelligently about the approach to the solution and engage in an ongoing discussion as the interviewers change the requirements while the discussion is underway.

The original question is asked, the interviewee says, "start at the beginning and march toward the end looking for the 'hole'". Interviewer says that's too slow, because N is gargantuan. Interviewee starts discussing binary search. Interviewer says that all of the sudden the data is no longer sorted. Interviewee says "sort then search". "Now it's too slow". Etc., etc.

share|improve this answer
add comment

Unless you are asking questions about algorithms/formulas the candidate needs to know for the job (fluid dynamics, for example, if the position requires that), I dont see their value. The candidate is already likely worrying about how they're dressed, how they're speaking, etc... whether they can answer a math question on the spot doesnt prove anything other than maybe how they might fare on a tv game show.

When I interview, I dont even ask 'programming' questions per se. I have the candidate describe their past projects, how their code achieved goals, what their approaches are, etc. From that I can tell pretty quickly whether the candidate knows what he's doing or if he's a poser.

share|improve this answer
add comment

You want a question that will give you insight into the candidate. An algorithm question may give a good response, or it may not. And I'm not referring to them being able to answer it or not. If they work through it, and you understand and follow their reasoning, that's a good indicator. If they just sit there, no real response, don't seem to even know where to start, that's a bad indicator (maybe). The problem would be that some people freeze up, and differentiating freezing up from not having problem solving skills may be difficult.

People will complain about asking just about anything in interviews, for various reasons. The applicant may freeze up, the applicant could have just looked that question up, the applicant may not know that particular piece of trivia/tech/whatever. All this is true, but an interview still needs to happen, and many of us in this profession hate that. We hate the idea of someone sitting in judgement of us. We immediately conjure up reasons why we could be judged unfairly, or how the test could be bogus or gamed. Bottom line is, it doesn't matter.

What you really want is an interviewer with the ability to determine skills that may or may not be presented during the interview. Questions are just the tools. To me, all hammers look the same. But to someone skilled enough with them, I'm sure there's difference.

share|improve this answer
add comment

I have to admit here, that I am one of those who like to ask algorithm questions in interviews, but I have to stress, that the actual answer to the question is absolutely irrelevant. I do not care the slightest if the interviewee knows the answer or not. Instead, for me, this question targets different aspects, like the following - in order of importance:

Requirements

Such questions are deliberately under-specified. In your example, there are no further details given about the sequence. If you have an interviewee who asks you whether these numbers are actually sorted, then that's a good sign. He has the correct mindset to ask customers on further details, that will help coming to a better solution in a shorter time. The candidate may also toy with the idea of using O(n) space to store an array of N numbers, but he should not do that without asking about more details on X and Y. Let's say that X and Y are between 1 and 1000, then sure, go ahead and fire up an array-based solution. But if I tell you the interval is 1 and 1 billion, then the problem becomes a totally different one. Let me stress again, that I don't care about the solution. I want to see if the candidate can find the distinction between these problems, which are immensely different.

Standard Techniques

I do not want to hire a programmer who doesn't even know what O(n) means. That's an absolute must-know if you had any decent education in that area. But it's also important to not just know what it means, but to actually apply that knowledge. In your example, I want a candidate to realize that he is not allowed to sort the data (without asking further questions targeting the option of a bucket sort or other O(n) sort approaches) due to sorting required O(n log n) in general.

Similarly, other algorithm questions target standard techniques like tree- or graph-traversal, or recursion. A candidate may slip at one of these techniques, which does not make a good impression. In such cases, however, I like to dig deeper to find out whether the candidate has any CS background at all. Of course, it depends on what the target position is, but usually a developer who doesn't know about runtime complexities, nor typical data structures and their traversals, is not going to be any help.

Problem-Dealing Mindset

After asking the question, you monitor the candidate closely. How does s/he react? You get the best results here from candidates who have absolutely no clue on how to solve the problem at first. In that respect, the question checks what might happen if a similar situation occurs at the workplace later. You may happen across such a problem during your development, and it is good to know how your candidate deals with these problems, even if s/he is not able to solve it all by themselves.

Example: You do not want your candidate to go into silent mode for the next half hour! Check if he can come up with intelligent questions (see Requirements), check if he starts thinking out of the box once he realizes he cannot do it. Even a "fun" counter-question like a "May I use the phone-a-co-worker option?" is a good sign.

How to answer

In general, the best answers you can give for these kind of questions are counter-questions! Telling an answer right-away basically fails the whole thing, and is in fact not a good answer at all, because all of these question hint at trade-offs, which your answer implies, without you having the required information yet to intelligently make that trade-off. Of course, the quality of the counter-questions varies between candidates.

As a general note on interview questions: Counter-questions are seldomly a bad thing. In one of my own interviews I was for example asked something like the following: "If you would have to implement X, would you choose C++ or Java for that, and why?" - I simply countered with "Am I limited to these two?". Guess for yourself, what kind of reaction you get from an interviewer for such a counter-question - and how easy it makes it for you to actually show the interviewer what you're capable of.

share|improve this answer
    
Why is "May I use the phone-a-co-worker option?" a good sign? Doesn't this show that the interviewee does not know how to tackle problems and always asks for help? –  Uooo Jul 23 '13 at 7:39
    
There will always be a question that the interviewee simply cannot answer. In that case it's a good sign, but of course, the interviewee should not repeat that behavior for several questions. The hard task is to find out, if you just hit that one sweet spot, where the candidate has no knowledge (which is acceptable), or if he is trying to wiggle out of hard problems in general (which is not). –  Frank Jul 23 '13 at 8:11
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.