Details matter. Getting details wrong and being careless during interviews leads to a lot of failed interviews (that probably should have been passes). In the real world, completely incorrect code can be better than code with subtle bugs. If your code is completely broken, you’ll notice with test cases and fix it. If you have subtle errors, the code will likely get through code review and lead to a long and difficult debugging session.
We all make mistakes, but why do some programmers seem to make fewer than others? Are there any tricks you’re missing that could help you get the details right?
Here’s a classic whiteboard interview gone bad:
Interviewer: “Could you please code (some simple algorithm, binary search, bfs, etc)”
Candidate (after writing some code): “Ok, that should do it.”
Interviewer: (squinting at the code): “Hmm well what about this test case?”
Candidate: *Traces what the code would do for the test case and realizes a bug.* “Oh… well let me just fix that.”
A small piece of code is scribbled out and changed. The test case now passes…
Interviewer (squinting again): “Hmm well what about this other test case?”
Candidate: *Does some more erasing. Adds another scribble* “Here, now that test case will pass too!”
This ‘test case and scribble’ pattern continues a few more times until the candidate’s code looks nothing like originally intended. The interviewer records the code as written and eventually forwards it to a hiring committee. The hiring committee has only this code as evidence to judge the candidate’s ability and assumes the candidate codes spaghetti.
The candidate is rejected.
How can you avoid falling into this trap?
Here are a few techniques that can help you get your code correct the first time:
Technique 1: Draw a diagram
Let’s look at a problem from leetcode:
Leetcode Problem 54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
There are many ways to do this problem, but let’s assume we want to do it recursively using this strategy:
Push the outermost layer into the output in spiral order
Make a recursive call to push the rest of the matrix.
Using this idea, we can probably start coding; but, it’s easy to make a mistake and it’s also possible the interviewer will get confused by our code. Let’s start by drawing a diagram.
Now that we’ve drawn this diagram, the interviewer has a lot of information about how we plan to write our code. This diagram could be slightly simplified (e.g. note only the names of the corners) or have even more information (e.g. note which variable varies for each arrow or label the indices to be used for the recursive calls) but should have enough information to help you and to convey what you’re planning to do to the interviewer.
Once we have a diagram, we should be able to get our code correct or close to correct on the first try, and if we make small mistakes, the interviewer may even point them out as we go.
A full solution to this problem can be seen in the appendix at the end of this post, but here let’s show the code for the recursive case (in c++ with out as the vector that we are returning our results in):
// recursive case (print the outside layer in 4 loops as per diagram)
for (int j = startj; j <= endj; ++j) {
out.push_back(matrix[starti][j]);
}
for (int i = starti + 1; i <= endi; ++i) {
out.push_back(matrix[i][endj]);
}
for (int j = endj - 1; j >= startj; --j) {
out.push_back(matrix[endi][j]);
}
for (int i = endi - 1; i > starti; --i) {
out.push_back(matrix[i][startj]);
}
This code is full of opportunities to make mistakes but, using our diagram, we get it right.
Technique 2: The Loop invariant
A loop invariant is something that most people wouldn’t think to use during an interview but it can help you get your code correct and give you an advantage.
What’s a loop invariant?
The concept of a loop invariant comes from formal program verification (rigorously proving that a program is correct).
A loop invariant is a predicate (i.e. true/false statement) that is true immediately before and immediately after a loop (it can be false during the loop).
What’s an example?
In binary search, we typically maintain a left and right boundary. In our main loop we will keep the invariant that, “left <= right and the number we are searching for is either in the range, [left, right] or it is not in the array”. (More on this here and here (highly recommended article)).
How does this help us?
By choosing a good loop invariant and checking that it does in fact hold, we can show that our programs are correct. When we write a loop in our code and keep its purpose in mind, we can double check to make sure that we in fact fulfilled the purpose correctly.
Imagine we want to write an iterative, rather than recursive, solution to the spiral matrix problem above. How could the loop invariant help us get the code correct?
Let’s take a look at an iterative solution to the spiral matrix problem:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> out;
if (matrix.size() == 0) return out;
if (endi < starti) return;
if (endj < startj) return;
while (starti <= endi) {
for (int j = startj; j <= endj; ++j) {
out.push_back(matrix[starti][j]);
}
for (int i = starti + 1; i <= endi; ++i) {
out.push_back(matrix[i][endj]);
}
if (endi != starti) {
for (int j = endj - 1; j >= startj; --j) {
out.push_back(matrix[endi][j]);
}
}
if (endj != startj) {
for (int i = endi - 1; i > starti; --i) {
out.push_back(matrix[i][startj]);
}
}
}
}
The while loop could have the loop invariant that, “the numbers outside of the sub-matrix with top left hand corner = starti, startj and bottom right corner = endi,endj will be correctly spiral printed into ‘out’.” This loop invariant might seem simple, or useless, but if you think start to try coming up with loop invariants when you write code, it forces you to think about the purpose of your loop and gives you something to check to help get your code correct.
Technique 3: Testing
Hand testing your code during an interview will probably feel awkward. Just do it. If you’re the one pointing out your errors, rather than the interviewer, they will be much more likely to give you a pass.
When you practice interview questions on a site like leetcode, or hackerrank, you will be tempted to just write your code and submit it. If you do that, you’ll be missing out on a crucial step. Assuming that you are incorrect, and then convincing yourself that your code works is a crucial skill.
When you’re practising, try thinking of submitting as saying, “okay that looks good”. Try tracing through your code by hand and making sure it’s actually correct before you submit. Once you practice testing your code, you get so used to hand testing that you might start to ‘test as you go’ and even consider the potentially problematic test cases before you write the code.
FAQ
Where can I learn more about diagrams?
One book that will teach you about diagrams as well as algorithms is Grokking algorithms. This book should give you an appreciation for how much easier it is to explain things when there are a lot of pictures included as well as help you learn more about algorithms basics.
Where can I learn more about loop invariants?
The second chapter of ‘Introduction to Algorithms’ has a good section on correctness proofs using the loop invariant. This book, could also be of interest.
These lecture notes could also teach you more:
http://www.cs.miami.edu/home/burt/learning/Math120.1/Notes/LoopInvar.html
http://www.cs.cornell.edu/courses/cs2112/2015fa/lectures/lec_loopinv/index.html
Appendix
Recursive solution (in c++) to Leetcode Problem 54. Spiral Matrix
void spiralOrderRecursive(vector<vector<int>>& matrix, int starti, int startj, int endi, int endj, vector<int>& out) {
// base cases (either just 1 or no more rows or columns, we know numRows is 1 only if starti == endi)
if (endi < starti) return;
if (starti == endi) {
for (int j = startj; j <= endj; ++j) {
out.push_back(matrix[starti][j]);
}
return;
}
if (endj < startj) return;
if (startj == endj) {
for (int i = starti; i <= endi; ++i) {
out.push_back(matrix[i][startj]);
}
return;
}
// recursive case (print the outside layer in 4 loops as per diagram)
for (int j = startj; j <= endj; ++j) {
out.push_back(matrix[starti][j]);
}
for (int i = starti + 1; i <= endi; ++i) {
out.push_back(matrix[i][endj]);
}
for (int j = endj - 1; j >= startj; --j) {
out.push_back(matrix[endi][j]);
}
for (int i = endi - 1; i > starti; --i) {
out.push_back(matrix[i][startj]);
}
spiralOrderRecursive(matrix, starti + 1, startj + 1, endi - 1, endj - 1, out);
}
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> out;
if (matrix.size() == 0) return out;
spiralOrderRecursive(matrix, 0, 0, matrix.size() - 1, (int)(matrix[0].size()) - 1, out);
return out;
}