Don't write on the whiteboard
I recently interviewed at a major technology company. I won't mention the name because, honestly, I can't remember whether I signed an NDA, much less how strong it was.
I did well. Mostly because of luck. I normally step over myself when I interview. I guess I've improved over the years. Here are a few tips to ace your own interview.
1. Don't write on the whiteboard
When I interviewed at Palantir around 5 years ago, I had a lot of trouble with this. Yes, I knew next to nothing about computer science then, but I should have been able to answer many of those questions. For example, Palantir asked me to write an API for a hash table, and I forgot set key and get key, the most basic operations. The alien situation of the whiteboard contributed to my nervousness. I didn't get an offer from Palantir.
Most people think you have to write on the whiteboard. Steve Yegge recommends that you practice writing code on a whiteboard and even buy and bring your own marker to the interview. That's pretty extreme and truly conveys the capriciousness of modern-day tech interviewing.
The interviewer started by asking me to code up a simple recursive calculation, using any language I wanted. "I dont like to write on whiteboards," I said. "It feels unnatural and distracting. I'd prefer to write on paper." "Okay," he shrugged.
The interviewers don't care. Use paper.
2. Bring your own paper and pen
So I asked for some paper and a pen. But there was no paper around, only some post-it notes. My mistake.
You should always have paper and pen anyway to write down ideas. On the subway, in line for movie tickets. Or you can keep a few sheets of paper with your resume and folder you brought to the interview (you did that, right?). Moleskines are excellent notebooks.
Some of the best programmers figure out the high-level overview on paper before they write a single line of new code.
3. Use Python
Even if you are a C++ systems guru. Even if you only know how to use Eclipse to program Java. Learn Python and use it during your interview. Python's philosophy is very simple and consistent. It's largely composed of a subset of the ideas in Java and C++. 80% of Python is based around the dictionary (HashMap). It will take you a few days to learn and not much longer to master.
You will waste a lot of time writing string manipulation code and initialization code that you can do in one line of Python. Get to the algorithm.
All I had was a post-it note, a tiny amount of space. So I wrote down the algorithm in Python line-by-line on the post-it note.
4. Write short algorithms, then make them half as long, then make them shorter, then ask an expert how they would make it even shorter
Five minutes later, I had my algorithm. It took up less than a few lines. He looked at it, yea, that looks correct. "Normally people write it in Java and it takes them a while and it takes up a lot more space on the whiteboard. They spend a lot of time manipulating the input string."
Since my first interview at Palantir, I had done a lot of practice problems.
The highest value problems I know of are on Project Euler. The site posts a sequence of problems of increasing difficulty which you have to solve with increasing efficiency. To become a great hacker, just do those problems in order (in Python!). Then take your solution and do it in half the lines. Now, read more of the Python docs (maybe read about generators and list comprehensions and decorators) and make it even shorter. Finally, look at the solutions posted on the Project Euler site. Stand in awe of the 1-line solutions. Weep in joy over the solutions of the guy who answered the problems using just pen and paper and his brain.
The highest value courses I took are algorithms and advanced algorithms courses. I was lucky enough to study under Robert Tarjan. But I also did every problem in CLRS, the standard (and very well-written) algorithms textbook.
If you do all that, you won't be nervous at your big interview. You'll be bored.
5. Write tests on your own code, sometimes
I say sometimes instead of always because, first, it is impossible to test every case. 100% test coverage is a myth. Any non-trivial program is going to have too many edge cases to check, computationally. You need to test the high-value parts. You need to test the parts that you keep breaking.
Finally, as you finish, the interviewer will look at your code and ask you to write tests for it. So, pre-empt him and describe the tests that you would write yourself. Write edge case tests. Run the tests in your mind. Does your algorithm work? Remember, the interviewer will ask you to do this anyway, so just do it yourself and you will be one step ahead and score well.
The highest value book I read which taught me practical programming techniques is Programming Pearls. It also teaches you the importance of tests and how to write them in a pain-free way. Read this book, it's very short.
He asked me to write tests for my code, find corner cases. He then asked me 3 other problems. They were Dan Tunkelang type problems. He ran out of problems and there were 15 minutes left. "Normally there's not enough time to ask more than 1 or 2", he said. So we just talked about VMs for 15 minutes. He taught me a lot about virtual machines. This brings up lesson 6:
6. Understand what you don't know, why you don't know it, have an interest in it
Read random Wikipedia articles. You don't have to understand it all, just know enough to be able to ask someone who is knowledgeable. Usually, they can teach you a lot from the seed of what you read. But you need that seed, that germ of interest.
This will make your questions good and your conversations interesting. People like to talk about themselves. Always carry some knowledge and some ignorance as fuel for them talk about themselves and teach you. The interviewer will leave with a positive impression of you.
Don't just read blogs. Read research papers published by successful company. Read Google's MapReduce, GFS, and BigTable papers. Read Yahoo's Hadoop and PNUTS papers. Read Amazon's Dynamo paper. Big companies have big systems, and they will expect at least some familiarity with how they work. These papers are hard. If you have no systems experience, it may take you a day to read through a single one. In the end, you will understand not just how these systems work, but how to think about these systems and design one yourself.
7. Use esoteric tricks you know, teach the interviewer
You're not supposed to use libraries in these coding exercises. But if you know something cool, just use it. In the worst case, the interviewer will tell you to rewrite it. In the best case, he will be interested and ask more questions about it. You will teach him.
I taught the next interviewer about the memoization decorator in Python. Memoization takes a complicated dynamic programming problem and makes it blazingly fast. He asked me to solve a problem. I wrote an O(N^2) algorithm, then made it O(N) with just one more line of code on my post-it note (still no paper).
I taught him about how I often write a file-backed cached version of @memoized that writes to a file so that I can persist the quick results between runs from the shell. He's a C++ guy, so I taught him about Python decorators as well.
8. Think how you think, go with it.
Studies on creativity have shown that if you tell people to be more creative, they end up less creative. If you split two painters up and tell them that the most creative person wins a prize, the paintings will be boring or the same. People forced into creativity think in the same way.
So, don't think outside the box. Just think how you think to the extreme. Go with it.
The third interviewer asked me to design a game API. He wanted a low-level design, but I misunderstood, so I started adding artificial intelligence features that would suggest moves for you to make. I wasn't sure what he was asking, and I kind of tried to clarify, but then I just went with it. My main interest is AI and machine learning. He was impressed by the originality, and I eventually answered his original questions too. You can usually tell when someone is being genuinely sincere by the manner in which they go out of their way to tell you, versus when they are just mouthing the words. He honestly implored, "it was really great talking to you."
9. Give reasons for your opinions, not just opinions
I asked the next interviewer how much he liked mobile development and he said he liked it. I was learning iPhone development. I played with Android too, but I told him I found the XML for UI distasteful. He asked, "Why?" I said you always want to put as much as you can into code because it gives you power. For example, you want to create and manage a repetitive UI element in code to avoid repetition. Avoiding repetition is the whole point of good coding.
He said that Android has a solution for the repetition in the form of XML templates or something. "Oh, I didn't know that," I said. I thought about it more. "Yea," I observed, "the solution to the problem of XML, in enterprise, is often more XML." He chortled.
At a previous interview, a CTO was looking for an employee #1. He was just leaving Google to start a new startup, and he asked me what my thoughts were about Amazon Web Services. I said, "they're good."
I didn't realize that he did not have much experience with them (having been at Google), and wanted some real constructive feedback. I didn't realize that he was testing to see my experience and familiarity with AWS. More importantly, he was testing my reasoning ability and judgment. I have been running an EC2 instance continuously to run this blog for the past 5 years. It scales well and is very simple. I've used nearly every single one of their technologies since they came out. I invest all of my savings in Amazon because I know this technology will net them billions of dollars. I should have said this. Instead, all I said was "they're good."
10. Interview the interviewer
The last interviewer asked me some simple questions that reminded me of a harder problem I had in one of the companies I started. So I asked him how he would solve my problem.
I was trying to find the phrases in a document that correspond to scientific terms in order to link them to Wikipedia automatically. The vocabulary is composed of words and sequences of words like "DNA", "p53ase", "phospholipid bilayer", and "congenital determined myoglasia peptide". Documents are research papers, which can be long. There are a lot of terms (a hundred thousand biological terms, and many more if we include other sciences). How would you find and label all of the phrases in a document efficiently and what is the big-O running time?
He got the O(vocabulary size * document size) algorithm pretty easily, but I told him that there is an O(document size) solution. Can you solve it? Try it out. It's a fun, practical problem.
I pushed him a little bit but he didn't get it. I interviewed the interviewer and stumped him (although I'm sure he would get it if he thought about it longer).
11. Mention your projects and passions first
After finishing up all of the problems in 40 minutes, I had 5 minutes left with the last interviewer. I started telling him about my minimalist python web framework and he said, "That's so interesting, that's what we should have been talking about instead of going over these questions."
I got the offer this time, but I would much rather do a PhD instead. I want to learn how to push the boundaries of knowledge, not just apply what I learned in these books.