In Which David Rants About Data Structures Interviews

Something that annoys me about how we interview about software performance is that we emphasize the wrong part of the process. The motivating example for today's rant was about Arrays vs hashed Sets, but almost any question where an app team is asking a candidate to look at some trivial code and give its time complexity gets my ire.

If you have some code you suspect is using a slow algorithm or data structure and you’re staring at it in your editor, you’re probably not even in the right app. First you should be in your own app. Then in whatever you use to talk to your team. Then in a profiling tool. Then in a web browser. THEN in an editor.

The process for solving an algorithmic performance problem in a codebase looks like:

1. Identify that a performance problem in your code even exists
2. Convince your organization to devote resources to fixing the problem
3. Determine (probably in part via profiling tools like Instruments) that it’s an algorithmic complexity problem and not some other sort of perf issue
4. Characterize the abstract operations involved in the task sufficiently to search the literature for them
5. Actually implement the fix
6. Verify your fix and prevent it from regressing again in the future

Very few teams reliably make it past step 2. Most of the ones that manage to make it to step 5 don’t make it to step 6, which it turns out is by far the most important of the lot. Actively developed software is essentially a gas. It will expand until it hits constraints of some sort, and the only naturally occurring constraint is end users being so miserable that they push back. Fixing individual perf issues buys you time, and wiggle room to fit other work into, but it will eventually slow down again. The only way to make software fast in the long term is to prevent yourselves from making it slow.

The point of learning about algorithms and data structures isn’t to memorize lists of them, it’s to learn how to look at the shape of a human problem your users have and figure out what combination of data structures and algorithms match that shape.

So if you want to interview effectively about performance, try asking about how the candidate would identify and investigate a problem, and how they'd defend against it regressing once fixed. You can structure the sample problem so that the natural answer is using a better data structure if you want.