Is there an appropriate coding style for implementing an algorithm during an interview? [closed]

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.