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?
