Understand the game
There’s nothing crazy or mysterious about Google interview questions. They’re just programming exercises. You can check out some for yourself. They’re not terribly different from the types of questions you get at, and most of the big-name tech companies. In fact, they aren’t terribly different from the types of questions you’ll get at most tech companies. Again, they’re just programming exercises.
Now, that doesn’t mean they’re easy. They’re not. They’re hard. They’re hard for everyone. But if you understand the game, you can learn how to beat them.
What makes Google interview questions hard is this: Google interviewers aren’t just looking for an answer, they’re looking for the best answer.
Not only that—you need to be able to show why a certain answer is best (a lucky guess isn’t enough). This means you’ll need a vocabulary for talking about how efficiently a function solves a problem, and a method for deriving more efficient solutions.
What we’re talking about here is algorithm design, and it’s the main thing most engineers without a CS degree are lacking.
It’s the main thing Google tests for in their interviews. But it doesn’t take 4 years to learn. More like 4 weeks. Or less.
Today, I want to give you a taste for that algorithm design process. My goal is to prove to you that this stuff is:
- Totally learnable
- Really fun
- A great way to elevate your engineering craft, whether or not you want to interview at Google
A sample problem
The best coding interview problems have 3 answers: a bad answer, a good answer, and a great answer. All 3 answers are correct—what makes each answer better than the last is how much time it takes to run.
In each Google interview, a candidate spends as much as an hour working aloud—with some help from her interviewer—as she tries to derive the bad answer, tweak and improve to get to the good answer, and (if she’s good!) iterate further to get to the great answer.
The fastest way to get a feel for this process is to look at an example, so let’s work through a problem together. As we go, I’ll share the thinking used to derive each answer, so you can see that great coding interview performance isn’t just about being lucky enough to stumble into the right blind insight. There’s a learnable process to solving these problems.
Okay, let’s get into it. Here’s the problem:
Write a function that takes an array of numbers and returns the greatest difference you can get by subtracting any two of those numbers.
For example, if our input is [5, 8, 6, 1], the greatest difference we can get is 8-1, which is 7. So we should return 7.
Let’s solve this together. How should we get started?
The first solution
Here’s my first thought: we’re trying to find the greatest difference. So how about we find all of the possible differences, and return the greatest from among them?
To get every possible difference, we just need to subtract every number from every other number. We can do this by nesting two loops, with each one iterating over our input array. Here’s how that could look in Python:
def get_greatest_difference(nums): greatest_difference = 0 for num1 in nums: for num2 in nums: difference = num1 - num2 if difference > greatest_difference: greatest_difference = difference return greatest_difference
Alright, this’ll work! But how well does it work? Specifically, how long does this function take to run?
In algorithm design, we use a specific language for talking about run time, called . It’s a bit tricky to understand at first, but it comes together quickly with a bit of practice. It’s best learned through example, so let’s jump right in:
We want to know how many steps our algorithm takes as it solves the problem. In this case the question is, “how many times do we have to compute a new difference and see if it’s our new greatest_difference?”See also: