Thursday, June 30, 2011

Studying to Pass the Coding Interview

As I noted previously, I don't think coding tests measure the quality of a developer well. I think they discriminate against experienced developers and the self-taught, and favor recent grads because they are like CS homework exercises. But that doesn't matter. Google, Amazon, and Microsoft, among many others, give various kinds of coding tests at in-house interviews. To the extent I want to work at these firms, I must do well at coding tests.

There is generally-useful advice for anyone expecting to encounter a coding test. Some of this advice has been repeated elsewhere. Google actually sends you an email with advice prior to your in-house interview. Some of this advice I developed myself while working through many coding interview questions that I've faced recently, or that I found on the 'net.
  • Before beginning the interview process, review your undergrad Algorithms & Data Structures book if it has been awhile since you were in school. How important is this advice? As I've begun my own review, I've been shocked at how many of the questions I struggled with came right out of a book.

    Actually, this is hardly news (though it was news to me). If you look at Algorithms & Data Structures books on Amazon.com, "people who bought this book also bought" displays books with names like Cracking the Coding Interview. I also discovered that the book I used in college many years ago was not very rigorous. Computer Science has actually advanced during the intervening time. Who knew?

    Before my next interview season, I plan to study extensively, so that next time I don't waste time interviewing with big companies, only to be blown out at the in-house by doing poorly on a coding test.
  • Practice, practice, practice. Work through some coding problems. Time yourself. Then review what you've written and think about how you'd do better. Coding tests reward new grads having recent experience solving this kind of artificial problem. If you're a senior developer or you're self-taught, it is very likely that you need practice before going into a coding interview.

    There aren't so many popular coding test questions that you cannot possibly practice them all. I wonder how many successful candidates got the job because they memorized the test. If you've recently solved a problem posed in a coding interview, don't be the schmuck who says, “I've seen that before.” Just write it on the board and look smart. Because you are smart. You showed dilligence by preparing for the interview. Employers appreciate this quality, even if they don't realize it.
  • There are common themes among coding test questions, and they are not like your daily practice.

    Re-familiarize yourself with the string handling and array slicing functions and operators of your programming language of choice. Many coding test problems involve searching 1- and 2-dimensional integer arrays whose elements share a global property, or transforming character strings. If your workaday practice is like mine, it rarely involves arrays of integers, and rarely looks for relationships among the characters in a string beyond searching for occurrance of characters or substrings. Review coding test questions on the web involving this kind of problem, because you will see a lot of it.

    Review the hash table and heap data structures, because interviewers seem to be fascinated by them. Understand their big-O behavior. Be sure you can code heap insert using an array to hold your heap. Review tree traversal algorithms in both recursive and iterative forms.
  • Find out what the interviewer wants to see, and don't waste time showing them more. For instance, if the interviewer asks you to implement atoi(),  and all they want is to find out if you know any C, you can provide the most straightforward implementation. It's worth mentioning out loud that your simple solution is susceptible to overflow, or does not correctly convert the string representation of negative maxint, but even the simplest implementation will prove you can code. If on the other hand, you try to be fancy and capture every corner case, you may bog down and look like you don't know what you're doing.
  • Before coding, make an explicit plan for your solution. Senior developers do much programming using "muscle memory". This doesn't work for coding tests. A coding test is like a CS homework assignment. It consists of a puzzle to solve on paper, and just a few lines of actual code.

    Determine what data structures the code must manipulate. For instance, I once encountered the coding test problem, "Reverse a singly linked list." I attacked this problem confidently, and without advance planning, thinking that I'd solved many similar problems before. This was a mistake. I soon got confused about what was pointing to which. The solution was to realize explicitly that in reversing a linked list, I was working with two list data structures; the partially reversed list, to the head of which I added nodes, and the remaining unreversed list, from the head of which I removed nodes. With that thought in mind, the solution fell out as fast as I could write it down.

    Focus your attention on any relationships among data items in the problem set. Is the data ordered in some way, or are you looking for some kind of sequence? If it's a sequence, can the solution be defined recursively?
  • Abstract, abstract, abstract. Write a function to do any complex bit of code, even if you wouldn't write such a function in your workaday life because it is only called once. There are two reasons. First, clarity of thought is at a premium in a coding test. You want to get the overall logic down, then sweat the details in isolation. Second, time constraints may free you from having to code these functions once the interviewer sees you understand the solution. When this happens, it is a huge win for you.
  • Always consider error checking, but don't obsess. Always check for null pointers. It's a sign of maturity. I like to begin all my functions with a statement like

    if (p == 0) throw "error"; // error checking

    I tell the interviewer, "This is a standin for the unspecified error checking needed in a real problem.

Tuesday, June 21, 2011

Other, Younger Old Hands

I just came across this on StackExchange. Another Old Hand, this one only 32, laying down her rules of life in case they proved valuable.

The Developer's <code>