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 failed an interview question in C years ago about converting hex to decimal by not exploiting the ASCII table if (inputDigitByte > 9) hex = inputDigitByte - 'a'. The rise of Unicode has made this question pretty silly, but the point was that the interviewer valued raw execution speed above readability and error handling.

They tell you to review algorithms textbooks to prepare for these interviews, yet these same textbooks tend to favor the implementation with the fewest lines of code, even if it has to rely on magic numbers (like "infinity") and a slower, more memory-intensive implementation (like a linked list instead of an array) to do that. I don't know what is right.

Coding an algorithm within the space of an interview has at least 3 constraints: time to code, elegance/readability, and efficiency of execution. What trade-offs are appropriate for interview code?

  • How much do you follow the textbook definition of an algorithm? Is it better to eliminate recursion, unroll loops, and use arrays for efficiency? Or is it better to use recursion and special values like "infinity" or Integer.MAX_VALUE to reduce the number of lines of code needed to write the algorithm?
  • Interface: Make a very self-contained, bullet-proof interface, or sloppy and fast? On the one extreme, the array to be sorted might be a public static variable. On the other extreme, it might need to be passed to each method, allowing methods to be called individually from different threads for different purposes.
  • Is it appropriate to use a linked-list data structure for items that are traversed in one direction vs. using arrays and doubling the size when the array is full? Implementing a singly-linked list during the interview is often much faster to code and easier remember for recursive algorithms like MergeSort.
  • Thread safety - just document that it's unsafe, or say so verbally? How much should the interviewee be looking for opportunities for parallel processing?
  • Is bit shifting appropriate? x / 2 or x >> 1
  • Polymorphism, type safety, and generics?
  • Comments?
  • Variable and method names: qs(a, p, q, r) vs: quickSort(theArray, minIdx, partIdx, maxIdx)
  • How much should you use existing APIs? Obviously you can't use a java.util.HashMap to implement a hash-table, but what about using a java.util.List to accumulate your sorted results?

Are there any guiding principals that would answer these and other questions, or is the guiding principal to ask the interviewer? Or maybe this should be the basis of a discussion while writing the code?

If an interviewer can't or won't answer one of these questions, are there any tips for coaxing the information out of them?

share|improve this question

3 Answers 3

up vote 9 down vote accepted

In a typical setting of whiteboard interview, lasting about 30-60 minutes, you won't have neither time nor space for elaborate, "real-world" implementation. So you need to make various trade-offs of different kinds.

In every case, though, the most important thing is always to communicate them properly to the interviewer. Examples include:

  • "I assume input data is correct. Normally I would add a check for $propertyX and $propertyY, but I'm omitting it here for brevity". (error checking and handling)

  • "This part is growing a bit complex, so normally I would extract it into separate function taking $arguments and returning $result." (refactoring)

  • "For now, I will use this $dataStructure and $helperAlgorithm but I think it's possible to use $moreEfficientApproach instead." (optimization; note that typically you'll be asked for implementing that better approach anyway, but doing the simple one first is often very helpful)

  • "I will use $functionThatDoesntExistYet in order to do that, which I will implement once I finish with the main algorithm." (abstraction)

  • "$madeUpNotation means $someSemanticConcept here, I'll use that for brevity." (language boilerplate, e.g. importing set/dict/lambda syntax from Python to Java)

I, for one, think that making such trade-offs consciously can actually score you more points than making everything "properly", especially if the latter involves writing big parts of code not directly relevant to the problem. The burden is on you, however, to demonstrate that you know what you are doing and are aware of the shortcuts you're taking - lest the interviewer might think you are forgetting the important details.

share|improve this answer
    
+1: Communication your assumptions is basically saying "I am aware of issue X and will handwave it for now, if you want me to go into details of that, just tell me". This tells them that you know of the topic and if they care about how much you know, they can easily ask here. –  Joachim Sauer Feb 20 '13 at 16:12

It really depends on the job you're applying for, and even for the same job, different interviewers will have different opinions. The best bet is to ask the interviewer. If they can't or won't give you an answer, then your best bet is to use your best judgment, defend your choice, and explain how you would do it given different criteria. "This is the simplest implementation, but if parallelization were a big concern, I would do it this way."

You might think ASCII is obsolete, for example, but there are a whole bunch of embedded C programmers who have never needed to use Unicode their entire career, for whom using the ASCII table in that manner is more readable and less error prone, not just a matter of "raw execution speed." Asking such a question is a good way to assess how familiar you are with that particular programming subculture. If you're not, that's not necessarily a deal breaker, especially if you defended your design decisions well, but you'd still need to show an ability to adapt to the coding style of the job you're applying for.

share|improve this answer

There is an awful lot in your question above so I am not positive I am going to hit on all of your points but let me at least give you some feedback.

First I am a Director of Software Development at a medium sized enterprise mobility company and we have grown quite a bit in the last few years. As a result I do a lot of programming interviews and although I am in management (queue typical useless manager joke) I still code and architect quite heavily and am very hands on. Because of this I also over see one of the main programming challenges during the interview. So here are the things I check for and I think are appropriate as well as some answers to your above question.

I have a small handful of challenges that take between 40 minutes to 2 hours to complete and I allow all of that time. I also allow myself to be a resource to the interviewee as if I was Google and I allow them to do some searches online if required. I do test algorithms but I do so in such a way as they are hidden in the use case and problem statement.

Here is where I think you are looking for answers. I do use a whiteboard currently and so I coach the interviewee to use whatever coding style they are comfortable with in the language I am checking for. I give them a few options of language to pick from based on the job reqs. I expect that whatever coding style they use they can back it up and are consistent in using it. I wouldn't fail an interviewee on coding style alone unless it was obvious they were looking up answers and using several different styles in putting the answer on the board.

I can usually tell how long someone has been programming and in what languages primarily based on coding style. However I don't dock someone for it. I may ask questions about why they did this or that. An example is if someone was coding a conditional and they did:

if (1 == A) {}

versus:

if (A == 1) {}

then I know they have been developing for a while in a C based language and they have been bit by the assignment bug more than once and used style to protect themselves. Right or wrong it tells a lot about a developer.

Now, as for your algorithm questions I look at it this way. I never test for textbook style algorithms or whether someone memorized one way to do it from a certain programming interview book. I always look for whether someone knows algorithms in general and can code a few ways to do one or notice when one is required in a solution. I never straight out ask for someone to tell me how to code a doubly linked lists or tell me what the most efficient sort is. Sometimes I will ask someone to give me what the BigO notation is for an algorithm they put on the board or to explain it in more depth.

If time allows and say the interviewee has solved the problem in less time than is required I love for them to go back and refactor, comment, explain, unit test and what not the answer. It shows more concern and a greater depth of understanding and some pride in what they do. This versus someone just trying to get through the development interview. Time willing or not a passionate developer will sit there and go over what they did and refine it almost always. I have rarely been burned hiring a passionate developer like that. Saying that, I do think basic comments are good to use always. If they are lacking I will sometimes start asking a lot of questions and normally they get the clue and start putting comments down so I stop bugging them :).

I don't mind a developer using an API that is part of the language set if it makes sense to do it. If I am trying to dig out whether they understand a certain algorithm I might say go ahead and use that API call, but do explain to me what it does and give me some detail. Understanding more than rote algorithm memorization is always expected.

In the end I am looking for problem solvers. Whether they are coding craftsmen, developers, rote development people that memorized the entirety of the Java API or whatever they have a job with me. They just need to be able to solve the problems we have with a decent velocity while working with a team.

Saying all of that I have been on more than one development interview where I had to do basic algorithms and I have even failed an interview because the person expected one version of the algorithm that was straight out of a book and failed to understand that what I did was the exact same algorithm. It happens. You don't want to work there anyway. So in the end it pays to know bit shifting, sorting, basic data structure, linked lists, Big O Notation, recursion, good programming style and all of the normal things expected of a developer even if you don't use them daily. However know and understand them fully and you will be better prepared. If you failed because someone didn't like your style, either it was so bad that maybe you should do some soul searching, or more likely it is a place you wouldn't want to work anyway.

share|improve this answer
3  
+1, just one thing: I'm certain there are people who use if(const == var) just because they've seen other people do it and repeat it mechanically, so I'd ask why they do it this way. –  K.Steff Nov 25 '12 at 20:24
1  
+1, with an additional note on the const/var example: The language I learned to program in used 2 rules for evaluation: Infix operators first, then functions. if length? foo = 1 would evaluate to if length? false and error, while if 1 = length? foo evaluates correctly. It's not a C-style language, but I do automatically carry it over to other languages as you suggested –  Izkata Nov 25 '12 at 20:51
    
K.Steff that may be true, but then those people might have picked up that style and it still serves them well. I have found though that more often than not it has been a conscious learning. It alone also is not a decision maker for me, but a signal for sure. Izkata, thank you for the insight. Is that something you learned over time? –  Akira71 Nov 25 '12 at 21:57
1  
@Akira71 I think I first saw it in example code that was explaining the evaluation rules, and after switching between it and if (length? foo) = 1, eventually figured "constant first" was just a lot cleaner. It just stuck with me after that. –  Izkata Nov 26 '12 at 13:37
    
@Izkata and that is the reason I place a bit of value when I see people use style likes this. For the very reason they are coding and have run into it and decided this actually made more sense. Again not a final deciding factor but one of those little things when I see people whiteboarding or coding and habitually do "constant first" I know they have some experience. even if they are faking it, they are faking it correctly IMHO. –  Akira71 Nov 26 '12 at 15:26

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.