How to Ace a Software Engineering Interview

Coffee. Change rooms. Handshakes. Panic. One of those four should not belong, and it’s not that delicious early morning Starbucks.

As I wrap up SWE internship interviews and start my usual midterm cramming, I ask myself: why did I do so much better than last year? Or why did they go so poorly last year? How have I changed my approach, and what could I have known last year to better prepare myself?

A year ago, I was in your shoes: a nervous, eager freshman studying Computer Science at the frostbitten University of Waterloo. Around now, I was interviewing with software companies for the first time in my life. Fun, right?

It was a terrible experience. In high-school, I won a few programming competitions and coded a lot because I didn’t go out much, so I was pretty sure of my abilities. Needless to say, I ended up not preparing much and got my butt whooped.

But why did I fail my interviews? At the time, I honestly had no idea, and to be fair, unless someone had straight up told me the honest truth, I don’t think any amount of preparation could have helped me.

Before I dive into the gritty details, let’s look at what people say about preparing for these interviews. A quick Google search for “software engineering interview tips” yields advice like: “learn to solve X-based problems”, where X is something like “data structures” or “recursion”, and “answer questions with passion”. I mean, they’re not necessarily bad advice, and you certainly need a solid grasp on CS fundamentals before working at Google. But this post isn’t about your CS 341 class; it’s about an in-depth strategy guide to handle technical interviews correctly.

The first tip will be more helpful to those who already have strong CS problem-solving experience. It is: for 99% of technical questions, there is only one correct answer – the one that the interviewer has in mind. It is your job to verbalize not just the solution, but the thought process that led to it. Let’s clarify this confusing sentence with an example:

Question: We all know that the Fibonacci sequence is defined as $f(n) = f(n-1) + f(n-2)$, for $f(1) = f(2) = 1$. Let’s define a neo-Fibonacci sequence as $g(n) = g(n-1) + g(n-2) + g(n-3)$, for $g(1) = g(2) = g(3) = 1$. How would you efficiently find $g(n)$ for any given $n$?

If you’re relatively new at these questions and you start off thinking of the recursive solution, then you’re on the right track to the “desired” solution, after a hint or two (which is perfectly fine). If you’re an experienced programming competitor (or really good at math), your first instinct might be to jump to the dynamic programming solution, or even better, the matrix multiplication solution straight away. You might even write the textbook-perfect implementation in a single take. Well, congratulations, pack up your bags, you just failed the interview.

You’re bewildered. You think, “I just wrote the asymptotically-optimal code that’s probably on par with the standard library implementation. Why did I fail that question?”. The reason you failed is not because you were technically wrong, but because you failed to grasp a crucial part of technical questions: to give you a chance to elaborate on your reasoning and explanation skills.

An interview is not your math or CS exam. It’s a chance to see if you have chemistry with the interviewer – if you can collaborate well with her. That’s why most of the time, if you’re stuck, she’ll be willing to provide a few hints to get you moving.

On the other hand, if you just quickly state the solution, which is something like “we keep a List/Vector/ArrayList storing the progressively bigger values of $g(x)$, for $x=4\ldots n$”, and write down the thirty-line implementation in three minutes, it literally tells the interviewer nothing about your communication or problem-solving skills. You might have seen the question before, or know the concept of DP beforehand. What would you if the question didn’t fit neatly into an existing concept?

The reason you failed is that for every question, the interviewer has a preconception of what the ideal candidate should think through. And it is not “state the final solution and write the code”. The actual promising candidate should say something along the lines of:

Hmm, this question reminds me of the Fibonacci sequence, which has a recursive solution, which means the runtime would scale something like $O(2^n)$, if we want to find the n-th number. I think if we apply the same logic for this sequence, the naïve solution would be $O(3^n)$. Hey, what if we store the solution as we go along? Then we can use $g(1)$, $g(2)$, and $g(3)$ to calculate $g(4)$, use $g(2)$, $g(3)$, $g(4)$ to calculate $g(5)$, and so on, until we reach $g(n)$. Then for each step from $4\ldots n$, we perform a constant-time calculation, this solution will be $O(n)$, which is a lot more efficient than $O(3^n)$, at a cost of $O(n)$ memory. Do you want me to code this solution?

Do you see the difference between the two approaches? I’m not saying “play dumb”, but more like “show your steps”. Remember, the question is designed not so you can prove that you’re a walking CLRS textbook, but rather to help you gain brownie points with the interviewer for the reasoning and communication skills you said you had on your resumé.

And don’t even bother with the $O(\log n)$ matrix multiplication solution. Chances are, unless you’re interviewing for Dropbox or something, the interviewer doesn’t know about that solution (not everyone nerds out about algorithms), and explaining that would be both time-consuming and pointless. (I’ve personally made a mistake like this before involving the “sweep-line” algorithm, and ended up confusing both myself and the interviewer in some edge cases.)

To sum things up: technical problems are for showing off your problem-solving skills, and more importantly, your ability to communicate your reasoning and thought process. Don’t be the robot who can only market himself as a walking algorithm encyclopedia. Be the colleague that the interviewer would be happy to work with in the future. That’s how you ace a technical interview.