What frustrates me about most advice with respect to interviewing practice is that it’s generally obvious and the target audience is people who are inexperienced. Examples of this advice are things like “make sure your interviewer knows what you’re thinking” or “don’t jump immediately into coding”. There’s no good source of advice for people who are intermediate level or above. One example is the subject of this article. It’s one of the lowest-hanging fruit for issues I see at the intermediate level for the software engineering interviewee.
Before I explain this, I want to provide an example. In calculus everyone learns the concept of a derivative. Conceptually it’s the rate of change at some point. You might be shown that the derivative if x^2 is 2x^1. The formula for the derivative of x^n is n * x^(n-1). You will get so used to these questions that it becomes muscle memory. And then in a homework assignment or a test you need to find the derivative of 2^x. Suddenly you realize your mental model is broken. If the polynomial rule for a derivative doesn’t work here, then what’s the real equation for a derivative?
The problem here is a selection bias on the examples you practiced on. You practiced on easy questions because the textbook author or instructor didn’t want to distract you with the real complexity involved. The easy questions, or maybe just repetitive questions, tend to have a shortcut. You apply the shortcut and now associate the shortcut with the generalized solution. Teaching you how to apply this concept to slightly more complicated examples was “someone else’s job” or “something for you to figure out on your own”. You are left half trained and might not even know it.
This problem was the subject of my favorite book, Mathematical Methods in the Physical Sciences by Mary Boas. In the introduction, she outlined how physics departments don’t have the time to teach students the physics and the math, so they teach the physics and expect the math department to teach the math. But the math department doesn’t do this for various reasons. Her book was to teach applied mathematics at the level of rigor required in the physical sciences. It is essentially a book about more rigorous applied math education for STEM fields.
This problem also exists in a lot of other domains, such as practicing for the software engineer interview. It’s a general flaw of teaching, where repetitive and simplified examples give a distorted view to the underlying structure of the solution. In the spirit of this, I’ll provide you with real, non-trivial examples.
Let’s say you’re given an array of integers are you’re asked to find the k-smallest items. You master that question on Leetcode and you interview. Now you’re asked to find the k closest 2D points to a 2D target point. They are the same question. For each question, you are given some input set of elements, and you are to find the top k of them according to some special distance function. That’s it, but one has a much lower pass rate than the other.
Let’s consider another example. You want to find the square root of a 64-bit double, or something really close to the square root. You might recognize that a binary search could work. You might be surprised by the number of smart, experienced people who end up suggesting a heirarchical binary search (do a binary search to find integer bounds [n, n+1] around the real square root, then a second one over doubles using those bounds), make implementation mistakes as if this binary search was over an integer array (e.g. high = mid – 1 and low = mid + 1 do not make sense in this context for adjusting bounds), or have significant implementation difficulty.
Here’s all you ever needed to know about generalized binary search: if position(x) < position(y) implies f(x) < f(y), then you can use a single binary search to get to your answer regardless of of what position() and f() mean. For a “simple” binary search over an array, position(x) is just the index of x. So this becomes i < j implies array[i] < array[j]. But for computing the square root, it becomes position(x) < position(y) implies x^2 < y^2, which is true. And the generalized code looks like this:
while (left < right):
mid = ComputeMid(left, right)
if CanReturnEarly(mid):
return mid
if GoLeft(mid):
high = mid – offset
else:
low = mid + offset
By overpracticing on simplified examples, some interviewees assume that offset must be 1 (which causes incorrect behavior for my question). They may not realize that offset can be zero if you don’t have to worry about convergence. They may set left/right/mid as integer types which wouldn’t make sense for this problem. Sometimes they struggle with when they can return early, which is usually just a sign they are overwhelmed with new information to struggle on something that was literally provided as part of the question.
The general lesson here is that many of the concepts you learned aren’t specific to the data types or values you practiced with. Unfortunately, instructors/authors/teachers have a bias to teach you using simplified examples that hides the complexity of the actual concept they want you to understand. The tension here is that you need exposure to that complexity if you want to perform at an intermediate or higher level of proficiency.
So what can you do about this? Mostly it comes down to understanding the general structure of the solution, and knowing which part of the general solution is fixed and which parts vary with the inputs. Once you understand this, you start practicing against classes of problems as opposed to specific problems.