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.

Sometime back in an interview, I was asked to write following program:


In a keypad of a mobile phone, there is a mapping between number and characters. e.g. 0 & 1 corresponds to nothing; 2 corresponds to 'a','b','c'; 3 corresponds to 'd','e','f'; ...; 9 corresponds to 'w','x','y','z'.

User should input any number (e.g. 23, 389423, 927348923747293) and I should store all the combinations of these character mapping into some data structure. For example, if user enters "23" then possible character combinations are:

ad, ae, af, bd, be, bf, cd, ce, cf

or if user enters, "4676972" then it can be,

gmpmwpa, gmpmwpb, ..., hnroxrc, ..., iosozrc


Interviewer told that people have written code for this within 20-30 mins!! Also he insisted I have to write on paper.

If I am writing a code then my tendency is as of I am writing production code, even though it may not be expected from me. So, I always try to think all the aspects like, optimization, readability, maintainability, extensible and so on. Considering all these, I felt that I should be writing on PC and it needs decent 2 hours.

Finally after 25 mins, I was able to come up with just the concept and some shattered pieces of code (not to mention of my rejection).

My question is not the answer for the above program. I want to know that is this a right way to judge the caliber of a person ? Am I wrong / too slow in the estimates ? Am I too idealistic ?

share|improve this question
13  
Took me 5 minutes to solve it on paper, so 30 minutes is more than enough. –  user281377 Sep 21 '11 at 9:36
18  
Took you 25 minutes to come up with a concept? Really? Looks like a very good way to me - they got exactly the information they wanted. –  littleadv Sep 21 '11 at 9:43
3  
@iammiling, I just wonder, where does this weird prejudice against recursion come from? –  SK-logic Sep 21 '11 at 10:12
6  
@SK-logic: In production code you have to watch recursion to make sure it does not blow your stack. While in academic situations recursion is usually considered OK. Sometimes it is easy to convert between the two in those cases you want to prefer the loop variant in an interview situation you want the candidate to spot this. In this situation this is nothing inherently wrong with recursion. –  Loki Astari Sep 21 '11 at 11:46
3  
@SK-logic: You asked why the prejudice against recursion. That is why. All the factors you mention are factors that will play into the decision. As I mentioned in this case there would seem to be nothing inherently wrong with it. Just when you use it you need to be aware of the danger. –  Loki Astari Sep 21 '11 at 11:56
show 10 more comments

14 Answers

up vote -2 down vote accepted

Do you know, why such tasks have to be done one paper? For the same reason, that UML is so popular for: Bubbles don't crash!

It seems that the average programmer needs much more than five minutes only to figure out the task. It definitely needs much more than 10 minutes to write a solution that works. (Even in a language you are experienced in.) And it definitely takes much much longer to write one, that is able to run on a small micro-controller with limited memory resources. In my experience, a company that asks such tasks in an interview is full of arrogant know-alls, that claim to be able to solve it within five minutes - but only on paper, because they are so intelligent, that they do not understand the task and the pitfalls of it. In real live they'd fail impressively, but because they are so brilliant, they do not need to proof it, of course, because the other brilliant ignorants in the company agree on the - wrong - solution.

Forget such companies!

Even the argument "See, how do you handle pressure" is stupid. The code presented in the answers here, is of absolutely no value. I can't see the algorithm and problem solving skills in them. Even if they would work, they are useless, because no body can follow them. To write code that is easy to understand on the spot, is essential in cases of time pressure. The statement "I am not so interested in the exact details of the code" proofs how ignorant and stupid interviewers are: it's the details that make the difference between a poor and an above average developer and nothing else. But because interviewers are managers in most cases (and brilliant ignorant developers in the other cases) they don't know and don't care.

Dear iammilind,
you are neither wrong or slow nor idealistic. Your are in the wrong company, if the interviewer asks such silly tasks. That's all about it.

share|improve this answer
    
The ability to solve problems like this one is not needed to move data between a website and a database. However there are a lot of teams where developers do need to devise algorithms for problems a lot more interesting than this one. For example: assign pallets of products to trucks so that the trucks aren't overweight, while minimizing the number of product-truck combinations (try to get all of one product on the same truck). –  kevin cline Nov 21 '11 at 2:10
    
+1 and accepting this answer. May be I wanted to hear this. You are correct about it's the details that make the difference. After this company, I got interviews from others, who were seriously interested in details (and they provided sufficient time and a PC to solve a problem) and I was able to crack the interview! Just to inform that those companies are better payer as well as offering good work. Time and Quality both are important. But I would give more weightage to quality, if I have to choose one of them. –  iammilind Nov 21 '11 at 2:34
1  
-1 for making unproven claims about other answerers' solutions being incorrect. (Prove what you claim and I remove the downvote.) –  Péter Török Nov 21 '11 at 8:43
    
@PéterTörök, you are correct about the incorrect claims for other answers. I have striked them off from the answer. –  iammilind Nov 25 '11 at 12:44
add comment

I don't think a reasonable interviewer would expect you to write fully correct, production quality (== documented, unit tested :-) code in such a short time on paper. They are probably more interested in where you are heading to and how far you get during this time, how your thought process works, rather than whether you are able to produce "the" perfect solution.

They may also be interested to see how you perform in such a stressful situation. If you block down totally in this interview, will you be able to solve a problem in a real crisis situation while the system is about to collapse, with angry users calling you constantly and your boss demanding the solution every five minutes?

If I am writing a code then my tendency is as of I am writing production code, even though it may not be expected from me.

There's the issue. This is surely not expected from you in an interview. So relax and just start thinking about the problem, and how you would solve it. You may think aloud, to let your interviewer hear your thought process. That will give them a great deal of info about your problem solving ability - that is what they are most interested in, not the code you write per se.

You may announce in advance that this is not going to be production quality code, only a sketch of a solution. This at least clarifies the expectations with the interviewer, and may help you relax.

Interviewer [...] insisted I have to write on paper. [...] is this a right way to judge the caliber of a person ?

Personally I wouldn't insist on that approach, as I try to get the candidate to relax, and let him/her provide answers the way (s)he prefers. In your case, they potentially missed a good candidate due to the rigidity of the interviewer. However, from your part, it is good to practice being flexible, and stretching your boundaries. So try to take such challenges as an opportunity to learn and expand your capabilities.

share|improve this answer
    
Appreciate your answer. However, I am still wondering if the specific problem mentioned can be solved within 30 mins !! :) If it can be then I am too slow. –  iammilind Sep 21 '11 at 9:19
2  
@iammilind, IMHO you should be able to work out the rough solution in your mind, and write some high level (pseudo)code to show your intent. That should be enough at that level - demanding more would be unrealistic. –  Péter Török Sep 21 '11 at 9:25
    
@iammilind: I agree with Péter saying that (...) I am writing production code, even though it may not be expected from me is the issue. It seems you spent too much time thinking about side issues (optimisation, readability...) instead of concentrating on the actual problem. –  Treb Sep 21 '11 at 14:31
1  
@Peter: I have asked questions like this one frequently, and I'm not trying to see how the applicant handles stress. I would expect a CS degree holder to have an approximate solution in 15 minutes, and wouldn't be surprised if someone was finished in under five minutes. The interviewer probably allowed half an hour in an attempt to reduce stress. –  kevin cline Nov 21 '11 at 1:58
add comment

There's code and there's code, they were probably looking for a pseudo-code example answer to show how you'd approach the problem more than how you'd code the solution.

I personally don't like the whole "do it on paper in 30 minutes", as an interviewee and interviewer I've been happier with the results from doing a verbal discussion of how to approach a problem, lets you know whether they can think of a clever solution or not.

share|improve this answer
    
I think a good approach is showing someone some code, having them correct problems in the code, and discussing, at least in the abstract, refactoring the code. –  Doug T. Sep 21 '11 at 14:56
add comment

I am always puzzled by people complaining that writing code on paper is not the same as on a computer. Of course it is not, but it is not the same for the other candidates too.

Keep in mind that you are not passing a test like in school, and you are not graded with a number. You are compared to other candidates. No matter how hard the assignment, all you have to do is to do better than your competitors - the other candidates for the job.

Also, to be honest, the problem you are presenting is quite simple. I can write a simple iterative solution in 5-10 minutes on paper. In 20-30mins a good developer could even write the tests for it.

share|improve this answer
    
If you can write within 10 mins for this question, then seriously you are very bright. I was not capable to write pseudo code after 25 mins. –  iammilind Sep 21 '11 at 9:31
4  
Actually, I don't think it's just about doing better than your "competitors". I mean, certainly, that's the minimum -- but if nobody does very good (as judged by the interviewer) then nobody gets the job... But you're correct in that it's not really about "pass" or "fail" as in school. –  Dean Harding Sep 21 '11 at 11:19
add comment

When you are interviewing for a job, the company is also interviewing to be your employer. An inappropriate interview constitutes flunking that interview, in my opinion. If the employer insisted on a test that you object to, you should terminate the interview, thank the potential employer for their time, and move on. There is no sense in wasting your time and their time in doing something that won't effectively help either of you evaluate the other.

For what it's worth, on a computer and in their preferred development environment, I think any decent programmer should be able to write a program in some language to solve this problem in 15 minutes or so. How long it takes on paper depends on how good the person is at writing code on paper, which is not a skill I have any experience with or have ever measured.

share|improve this answer
    
Good one. I was about to do that gracefully; but turned it down as I felt it could be awkward. Also I was not sure, if my estimates of writing on PC for 1.5-2 hours were correct. Because, if others can write withing 30 mins, then I could have been wrong. –  iammilind Sep 21 '11 at 9:37
add comment

Firstly, I think trying to figure out how a candidate thinks is valuable during an interview, and that a verbal discussion is usually the best way to do this, sometimes you simply don't have your best developers available to talk to the many candidates that you are interviewing. In these cases, well thought out questions can help answer the above question, and also filter out many people. I've seen people with seemingly shining CVs not able to give an example of a for-loop (in any language of their choice), or not be able to write the most basic SQL query. I don't think that this is reasonable, and time should not be wasted interviewing them further.

In your specific case, I don't believe the question was very good. Specifically, if you happen to know how to generate combinations in code, you will be able to answer it in a few minutes (yes, literally - google it). If you don't, you won't (unless, as you say, you are really brilliant). It's not a particularly fair or good question, in my opinion, but perhaps the interviewer wanted people that had some formal algorithmic knowledge, and wanted to filter out those that didn't.

share|improve this answer
    
this sort of problem should be covered in any CS curriculum. –  kevin cline Nov 21 '11 at 2:01
add comment

I obviously can't speak for anyone else, but I'm helpless writing proper code outside of Visual Studio. It just doesn't invoke the same mindset, and it's very discouraging to know that I could be mis-spelling things all over the place with no backup. Even trying to use Notepad on the computer doesn't work for me, let alone pen on paper. Pseudo-code, maybe.

That being said, the problem you were posed is pretty trivial as far as I can see, and it took me about 30 seconds to see a solution. I'd expect to have working code done in five minutes in Visual Studio.

share|improve this answer
    
Can you really write a high level pseudocode in Visual Studio (yes, I'm aware of an add-in for drawing flowcharts, that's a bit different)? –  SK-logic Sep 21 '11 at 10:15
    
@SK-logic: Yes, you can write pseudocode even in Word. –  surfasb Sep 21 '11 at 10:56
1  
@surfasb, you can write it on paper as well. I just wonder why VS is mandatory, if it does not make any difference for pseudocode? –  SK-logic Sep 21 '11 at 11:13
add comment

If think the interviewer wanted to see if you come up with the obvious recursion that makes solving this problem relatively easy. The requirement of "storing the result in a data structure" works towards you, because that's exactly what you need for the recursive solution.

For completeness, here is a working Groovy script to show how short a solution can be:

String [] chars = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

def getCombis
getCombis = { nums ->
   char c = nums.charAt(0)
   int i=c-50;
   List rest = [""]
   if (nums.length()>1) {
     rest = getCombis(nums.substring(1))
   }
   List result = []
   chars[i].toCharArray().each { cc ->
     rest.each { r ->
       result.add(""+cc+r)
     }
   }

   result
}

getCombis("234")

Result: [adg, adh, adi, aeg, aeh, aei, afg, afh, afi, bdg, bdh, bdi, beg, beh, bei, bfg, bfh, bfi, cdg, cdh, cdi, ceg, ceh, cei, cfg, cfh, cfi]

share|improve this answer
3  
Nice answer. Though I had to write this thing in c/c++, I understand that it should easy too. Accepting, that I need to sharpen my skills more. –  iammilind Sep 21 '11 at 10:30
5  
But this is not a short solution. In Haskell it's just mappings = ["", "", "abc", {-...-}, "wxyz"] combinations "" = [""] combinations (s:sw) = [ c:cmb | c <- mappings !! (read [s]), cmb <- combinations sw ]. –  leftaroundabout Sep 21 '11 at 13:01
    
@leftaroundabout, That's an interesting solution. –  Robert S. Sep 21 '11 at 13:44
4  
@Robert: just for fun, I golfed it down to 94 characters: o(l:m:n)=drop 1[l..m]:(o$m:n) o _=[] c""=[""] c(s:w)=[d:e|d<-(o"```cfilosvz")!!read[s],e<-c w] –  leftaroundabout Sep 21 '11 at 14:00
3  
@leftaroundabout, Its starting to look like base64. :D –  Peter Lawrey Sep 21 '11 at 15:48
show 1 more comment

First of all, it's not really a complex program. This is something that can be roughly done by an average programmer in 5 minutes, good clean version in 10-15 minutes.

Secondly, no one expects you to write compilable code on paper. I ought to be however logically correct. Pseudo-code is acceptable.

Finally, it's not unique criteria to judge, it's just a starting point for a discussion on why such a solution, what can be improved, etc.

This type of the question is designed to sort candidates into 3 categories:

  • discarded ones, who couldn't do it;
  • average ones, who made recursive solution;
  • good ones, who either unrolled recursion iterative solution, or can explain how tail-recursion optimization does that automatically.
share|improve this answer
add comment

I hate writing on paper. Basically because I had to do it as tests in study, other story... (and no, pseudo code wasn't enough, you have to remember everything, order of parameters and so on...)

The only real valid reason for writing code on paper for judgement is that paper doesn't forget. That means you should be able to see the "program first, think later" guys by all the corrections he did. Typically the small written code injected between two other code lines. And you can see the other type "think first, program later" (and I think the OP is one of this group). The result should be clean code on the paper because he doesn't change it while writing it.

The exception might be the very experience programmer, who find this task too easy to "waste" time on thinking about a solution.

Whats not checked with the text is the ability to read documentation and to use what you have just read and learned. In my opinion that's a very important skill for beginners.

(Private note: As I was hired as a totally beginner with no experience in the new language (application as PHP dev, hired as Java dev), judged just by a normal interview with no test, I would do this too, if I ever have the resonsibility to hire a new dev. If you think he has the talent to be a great programmer, take him! Experience can be gained, skill can be learned but talent is a gift...)

share|improve this answer
add comment

Previous answers mostly seem to be assuming they just wanted to see how you think and approach the problem and/or that they only wanted pseudocode, but that's not necessarily the case. A few years back, I applied for a position with a company whose pre-interview screening was "Call us at such-and-such a time and we'll email you a set of three problems. You will then have two hours to write programs solving them in [the company's primary programming language] and email it back to us without using any tools other than a basic, non-syntax-highlighting, text editor." The code wasn't expected to be 100% valid and runnable, since you couldn't use any tools to check for typos, but it needed to at least be reasonably close. This is essentially the same as having you do it on paper. (They saved the "see how you think" coding tests for the full-day on-site interview that came after this screening was passed.)

Is this a reasonable thing to ask for? Well, it is a bit unrealistic compared to normal working conditions, but it's also a good way to see how well you know the language on your own, without relying on Google/autocomplete/etc.

Is it fair? I don't see any reason why not, provided that it's applied equally to all candidates. Sure, some people may choke and perform unusually poorly under these conditions, but that's true of any evaluation that may be performed during an interview (and of interviewing itself).

Are you too slow or too idealistic? I'd prefer to suggest "inexperienced"; when I read the description, I immediately knew how to solve it and doubt that it would take me more than about 10 minutes to write in my language of choice - but, then, I've been programming for over 30 years and using my currently-favored language for about 10. I don't need to be a genius to knock out a solution to that in no time flat because I know my tools like the back of my hand.

I do see one major issue in your comment on the question, though: Premature optimization. If recursion is the right tool for the job, then use it. Don't worry about function call overhead (in terms of either processing time or stack space) until and unless you have functioning code which has demonstrable issues and you've done sufficient testing (benchmarking, profiling, etc.) to isolate recursion as the cause.

share|improve this answer
add comment

I don't like to take or give such tests myself in interviews because they can create undue stress. Many people, particularly those with personality types common to programmers, don't handle this kind of test well and will tend to underperform unless the topic in question is fresh in their minds.

Of course, stress might be part of the working environment at that company and, in that case, testing for the stress handling ability may be important to them. The real question is if this kind of work environment is a good fit for you.

share|improve this answer
    
Indeed a nice analysis. –  iammilind Sep 21 '11 at 14:19
add comment

The important thing to remember is that the interviewer will not expect you to code on paper if you get the job. They want to know how you think and how you work under pressure. By taking you out of your comfort zone, you are more likely to make mistakes (in other ways) and they want to see how you handle that.

The interviewer should be asking you progressively harder questions until you can't answer it (because you can never know the answer to everything) so what do you do in that situation. I tend to be disappointed if they don't ask me more than a few reasonable questions I cannot easily answer.

In other words, expect the unexpected.


I tend to go for the less obvious solution and can lead to a more interesting discussion after the test.

  static final String[] PHONE_CHARS = ",,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz".split(",");

  static Set<String> getCombis(String digits) {
    int combinationCount = 1;
    for (char ch : digits.toCharArray())
      combinationCount *= PHONE_CHARS[ch - '0'].length();

    Set<String> combis = new LinkedHashSet<String>(combinationCount * 4 / 3);
    StringBuilder sb = new StringBuilder(digits);
    for (int i = 0; i < combinationCount; i++) {
      int n = i;
      for (int j = 0; j < digits.length(); j++) {
        String chars = PHONE_CHARS[digits.charAt(j) - '0'];
        sb.setCharAt(j, chars.charAt(n % chars.length()));
        n /= chars.length();
      }
      combis.add(sb.toString());
    }
    return combis;
  }

  public static void main(String... args) {
    System.out.println(getCombis("234"));
  }

This doesn't use recursion but it does build a Set rather than a List.

share|improve this answer
2  
Interviewers use paper or a whiteboard just because it's simple, not to take candidates "out of their comfort zone." Good programmers are comfortable talking about code in any medium. –  kevin cline Nov 21 '11 at 2:03
1  
True, but being comfortable about writing code on paper takes some practice. I don't remember ever having a problem with it, but many developers seem to find it unfamiliar in the interviews I have done. (usually developers with around 10 years experience) –  Peter Lawrey Nov 21 '11 at 7:47
add comment

Absolutely, although not the only right way. I often ask similar questions in an interview. I am not so interested in the exact details of the code and I certainly don't expect your sheet of paper to compile. But I am interviewing you to be a developer and I want to see how you approach a task like this for several reasons:

  1. Algorithm and problem solving skills
  2. Handling pressure, because we all will face it
  3. Handling less than optimal conditions, we all run into situations where the requirements or environment are less than ideal, I want to see you handle it

In the end I am not hiring you to crank out code, I am hiring you to solve problems with code and these indicators give a good read on how well you might succeed.

share|improve this answer
add comment

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.