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.

Is there any acceptable/effective way to deal with interviewers who ask you to implement an algorithm that you aren't familiar with?

I've been interviewing a lot lately and encountering this a lot. Interviewers asking me to implement data structures or algorithms that I have never implemented, and will never implement, throw me completely off guard. In my case, specifically, I'm primarily a system developer, so I spend most of my time dealing with parallelism issues and related, rather than reinventing algorithms, so these questions are very irrelevant to me.

As an example, I was asked to implement a function that takes a string and returns a container with all the permutations of that string (C++). I suggested that there were functions dealing with permutations in the standard library that may be usable, but I wasn't sure exactly what the standard library offered, because I had never used these functions before.

I can easily solve the problem by nesting multiple loops for a fixed length string, but in this case, the length of the string is dynamic. I couldn't give a solution. After the interview, I looked up the implementation of next_permutation in my standard library, and now I'm not surprised that I couldn't come up with this when put on the spot. I doubt many could have answered without knowing the algorithm before hand.

What are some ways to deal with questions like this? Is there any acceptable response or way around these questions?

share|improve this question
    
Just try your best and ask questions. Learn afterwards if you care daniweb.com/software-development/c/code/216770 If you do not like algorithms, then perhaps it is a good thing that they did not hire you? You might not like working there. –  Job Aug 6 '11 at 2:28
1  
"that i will never implement..." See my answer below, but I would never hire anyone who said this, particularly about the sorts of things that people ask in entry level interviews. How do you know you won't have to eventually do a bit of real programming? And why should I hire you if you prefer to remain ignorant since "I won't ever need that anyway." I expect that from 8th graders shirking their math homework. I expect better from programmers- not much better, but a bit. –  T Duncan Smith Aug 6 '11 at 4:34
1  
You misunderstood my 'that I will never implement' and I didn't say that 'I won't ever need that.' I won't ever implement it because I know for a fact that there's already a sufficient implementation. I'm not sure about you, but I prefer developers who know how to use freely available libraries and their language's standard library. I didn't say anything about remaining ignorant; in a real scenario, if I needed to implement something I'm unsure of, I would research it. In an interview, this is not possible. You're assuming too much. –  dauphic Aug 6 '11 at 6:59
1  
The whole point of these questions is to test whether you can come up with a solution for an unknown problem. Or simply put: how smart are you? But in this case.. well, permuting a string is a very basic algorithm and if you don't know how to do that it shows your general lack of interest in algorithms. –  yi_H Aug 6 '11 at 22:46
3  
If I ask someone to do something in an interview and they say "well, I'd use the standard library"- OK a point in their favor actually. But if I then ask them "What if the library weren't there?" I expect a real answer. I might be assuming too much if you say "I would never have to implement that," but who cares?. My job, when interviewing, is to disqualify people. Don't disqualify yourself. –  T Duncan Smith Aug 6 '11 at 23:56
add comment

7 Answers

If the algorithms are the ones commonly learned you should probably know them before you go in. There are books about algorithms.

That said, I've done a fair bit of hiring. I've hired for really senior positions where faltering on a simple algorithm would be enough to disqualify a candidate. But that's not the norm (maybe it should be, but it's not.)

When hiring I care more about whether or not the candidate is smart and able to adapt than about the algorithms they have memorized. I also care a lot about how much I like them ;). Maybe that shouldn't be a consideration, but it always is.

The thing I want to see if I pose you an algorithmic question you can't answer off the top of your head is how you react to that. That's probably unfair, but life isn't very fair.

I want to see you make a real attempt at it, and I want you to ask a lot of questions. I want to see that you are smart, that you ask for help when you are stuck, and that you don't give up. If the question is hard I don't care if you get it right, but I care about how you approach it. If it is easy I do care that you get it right, but if I like you enough I might hire you anyway if I see some promise in you.

So the thing you ought to do is to be a naif- just say "I know this is a solved problem, and I ought to know the solution, but I don't. I would normally just look this up, but let me take a stab at it... let's start from the beginning here, and see if I can work it out on my own."

You have no idea how depressing interviewing programmers is... it's not just that the candidates know nothing, but they get this sort of "deer in the headlights" look when you ask them to do really simple things. I'm willing to hire people who don't know as much as they should, given a BA in CS, since that is the norm. But I want to see you try, and I want you to ask for help when you are really stuck (and only then.) That means I can work with you.

So try to figure things out if you are asked a question you don't know the answer to. Ask for help if you get stuck. And, above all, be excited about solving the problem. Try to draw your interviewer in- make him a collaborator in solving the problem. Make him like you, and make him think that you will at least try. That won't get you into Google, but it might get you into a lot of other shops.

share|improve this answer
1  
Agreed. When asking a programming/algorithm question in an interview, I actually don't want the candidate doesn't 'know' the answer and simply recite it. I want to see how they think, approach the problem and what the code looks like in the end. –  g . Aug 6 '11 at 9:31
add comment

What are some ways to deal with questions like this?

The process of turning the description of an algorithm into code is called computer science, there are lots of books and a few university courses on it.

The point of asking the question is to see if you can approach how to do it - not that you can remember boost's implementation of a standard algorithm and write it from memeory

You said you could solve it for a static string, but not a variable length one. Why? What extra steps would you need, what extra factors would you have to consider?

share|improve this answer
    
I like the sass. –  Casey Patton Aug 5 '11 at 22:16
3  
-1 Unnecessary arrogance - "The process of turning the description of an algorithm into code is called computer science, there are lots of books and a few university courses on it." –  Darren Young Aug 5 '11 at 22:30
1  
+1 they expect you to try. They'll give you hints if you can't bang it out. They're hoping to find out if you're smart. In order to do that, they need to get you in a situation where you don't know the solution beforehand. –  Kevin Aug 5 '11 at 22:48
2  
Actually, the process of turning the description of an algorithm into code is called programming. Computer science is partly where they study the description. –  Steve314 Aug 5 '11 at 22:56
    
@Darren - different people word things different ways. Some people are wordier than others, some more formal than others etc. When someone is from an area where everyone speaks slowly, for that person to speak slowly to you doesn't mean s/he thinks your stupid, and it doesn't mean s/he is being patronising. This could easily be the same thing. –  Steve314 Aug 5 '11 at 23:03
show 3 more comments
  1. Either they expect you to know it off the top of your head (unlikely), in which case you are doomed because you don't,

or, 2. They want to see you think on your feet.

If it's 2, then your just talk out loud and sound confident. It's fine to say you would look it up in the standard library in reality - it probably helps. Showing them a solution for fixed length strings would probably help too.

If it's 1, then study algorithms and hope you get lucky.

share|improve this answer
add comment

Here's one possible working implementation of your example:

void getStringPermutations(string &prefix, string &input, vector<string> &output)
{
    if (input.empty())
    {
        output.push_back(prefix);
        return;
    }

    for (unsigned int i = 0; i < input.length(); ++i)
    {
        string newPrefix = prefix + input[i];
        string remainder(input);
        remainder.erase(i, 1);
        getStringPermutations(newPrefix, remainder, output);
    }
}

I include this code to illustrate a couple points. First, it's not an unreasonable length for a whiteboard. Second, the only "trick" employed is recursion, which is one of Joel Spolsky's criteria in his Guerrilla Guide to Interviewing. Recursion isn't the only way to solve it, nor the most efficient, but it's probably the simplest. Also, you don't have to memorize this algorithm. You already understood how to do it with nested for loops without memorizing that. Applying recursion is the best-known method of dealing with an unknown level of nesting.

Also, while you may never need to implement a string permutation algorithm, you can't avoid designing any complex code in your job, and the interesting and relevant problems are too involved to cover in the course of a job interview. When people act like CS 201 problems are somehow beneath them or outside their purview, it makes interviewers question their ability to handle real ones. Concert pianists can still play scales.

My biggest suggestion is to work through questions on Project Euler. That will help reinforce the fundamentals. Then, when you're in an interview, don't be afraid to think out loud, and pay a lot of attention to any hints the interviewer gives.

share|improve this answer
    
Yep, this answer, together with the "I could use nested loops for a fixed length", shows why this is in fact an excellent question. –  poolie Sep 8 '11 at 5:49
add comment

I've very rarely had an interview that didn't include a question about some B.S I haven't used since college, or some esoterica of the language.

The only thing you can do is step up and take a swing at it. There is certainly no shame in saying, "I believe there is a built-in method for this, but I'm blanking on it." and then trying to do it the hard way. If they expect you to know the entire language by heart, you probably don't want to work there anyway.

share|improve this answer
add comment

When I interviewed for my job out of college, one of the interviewers had me implement a particular function in C on a whiteboard. It was a design verification job, and the algorithm they had me implement was for a function that takes a C string of any length, return true if it's a palindrome and false if it isn't. I never had to implement such a function, and haven't really seen reason to since. What they were looking for wasn't that I knew the algorithm, but that I could quickly come up with a method of verifying something, code it, and then be able to defend why my implementation works (indicating that I wasn't simply hacking away in hopes that something would work).

The idea here is to test your skill in designing and implementing an algorithm when you need to. It may not be a major function, but in most programming fields, you will be creating your own algorithms. As a programmer, I don't memorize many algorithms. I use standard and available libraries, and when those don't fulfill the requirements, I create and build my own. This is a fundamental skill for a computer programmer. So if you are trying to build your skills through rote memorization of algorithms, you're going about it the wrong way. You should be able to design and implement your own algorithms. Skill comes when you design them well, and if you can design algorithms that increase in complexity, but one should be able to come up with their own.

I find that the most use I get out of studying other algorithms isn't because I'm going to implement them myself one day (likely I would never have to since they already exist, I could just grab a library or the code from somewhere and just use that). The real value is that it exposes me to different methods of doing things, and gives me more ideas that I can work with to make my own algorithms. For instance, I studied heap sort in high school, to the point where I could probably implement it now in a minute or two. But, the real value in that exercise was that it got me more familiar with the concept of recursion, to the point where I have been able to create my own recursive functions for other tasks that it would be suited for.

share|improve this answer
add comment

I Don't Know

The proper response is "I don't know that off the top of my head, I've never needed it. Would you like me to work it out from first principles, or google the standard algorithm for you?"

I think these kinds of interview questions show a complete lack of imagination on the part of the interviewer, except in the rare case that the algorithm is somehow fundamental to their operations (which seems unlikely).

Lazy interviewers looking for canned answers are likely to get textbook-regurgitating candidates (or "prepped" candidates), instead of skilled developers.

In other words - it's ok to say you don't know, as long as you know how to figure it out or research it. If the interviewer is too lazy to ask questions relevant to the job... you may not want to work there!

share|improve this answer
1  
I think it all depends on how the question is presented. If it is simply 'implement this algorithm' and the interviewer is looking for a regurgitated answer, then it is pointless. I prefer leading into the coding exercise after some general discussion of data structures and algorithms at which point I have a good idea of their knowledge and the candidate should have some idea of how to approach the problem from our discussion. I want to see how he can apply it, think through the problem and code it up. –  g . Aug 6 '11 at 9:35
    
@g: that's great, but that's not the situation of the OP (as I understood it from the question). On a closer re-reading of the OP's question, I think the example given is trivial and the fact that the string is not fixed-length doesn't matter for the solution, but still such interview questions are mindless mush. ;-) –  Steven A. Lowe Aug 7 '11 at 3:23
1  
If it was "Implement a B* tree" then it would be reasonable to want to Google it, or to at least to be reminded of the definition of it. But permuting a string has a pretty obvious definition, and I think this whole thread is showing it's actually a pretty good test of mid level programming skills. –  poolie Sep 8 '11 at 5:51
    
@poolie: if that is an adequate assessment for mid-level programming skills, we need a new definition for mid-level! –  Steven A. Lowe Sep 9 '11 at 5:34
1  
@poolie: OMG. You're right. The OP fails. –  Steven A. Lowe Sep 10 '11 at 15:41
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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