Join our discord to discuss these problems with the author and the community!

Welcome to yet another installment of my series on interview questions I used to ask at Google before they were leaked and banned. I’ve since left being a software engineer at Google and moved on to being an engineering manager at Reddit, but I’ve still got a few great questions to share. So far I’ve covered dynamic programming, matrix exponentiation, and query synonymity, and this time around I’ve got a brand new question for us to dig into.

Before we begin, two notes. First off, working at Reddit has been amazing, and I’ve spent the past eight months building and leading the new Ads Relevance team and setting up the new engineering office in New York. As much fun as that has been, I’ve unfortunately found it hasn’t left me much time or energy to write until recently, and so I’m afraid this series has become a little neglected. Sorry for the delay.

Secondly, if you’ve been keeping up with this series you might have come away from my last post with the expectation that I’ll dig into variants of query synonymity. While I would like to do this at some point, I must confess this job change has caused me to lose momentum on that problem, and I’ve decided to shelve it for now. Stay tuned, though! I owe you all a writeup, and I intend to deliver it to you. Just, you know, later…

Quick disclaimer: while interviewing candidates is one of my professional responsibilities, this blog represents my personal observations, my personal anecdotes, and my personal opinions. Please don’t mistake this for any sort of official statement by or about Google, Alphabet, Reddit, or any other person or organization.

Finding a New Question

In my last post I described one of my favorite questions, one which I used for a long time before it was inevitably leaked and banned. Previous questions I had used were fascinating from a theoretical standpoint, but I wanted to pick a problem that was a little more relevant to Google as a company. When that question was banned I wanted its replacement to satisfy a new constraint: I wanted it to be easier.

Now it might seem a little surprising to hear this, given how notoriously difficult the Google interview process is. However, at the time an easier problem made perfect sense. My reasoning had two parts. The first part was pragmatic: candidates tended not to do well on my previous questions despite multiple hints and simplifications, and I wasn’t always entirely sure why. The second part was theoretical: the interview process should separate candidates into categories of “worth hiring” and “not worth hiring,” and I was curious as to whether a slightly easier question would still allow me to do this.

Now before I elaborate on what these two things mean, I’m going to point out what they don’t mean. “I’m not always sure why this person is struggling” does not mean I thought hard questions weren’t useful and that I wanted to make the interview process easier. Even the hardest question had plenty of candidates who performed well on it. What it means is that when candidates struggled, I had a difficult time constructing a narrative around where they are lacking.

Good interviews provide a broad picture of a candidate’s strengths and weaknesses. Simply saying “they rocked” doesn’t do much to help the hiring committee decide whether the candidate has the company-specific characteristics they’re looking for. Similarly, simply saying “they bombed” doesn’t help the committee when they have a candidate who is strong in some areas but might deserve the benefit of the doubt in others. I found more difficult questions caused candidates to fall into one of these two buckets more often than I would have liked. In this light, “I’m not always sure why they were struggling” means “failure to progress on this question doesn’t by itself paint a picture of this candidate’s abilities.”

“Classifying candidates into ‘worth hiring’ and ‘not worth hiring’” does not mean “the interview process should separate dumb candidates from the smart ones.” I can’t remember any candidates I spoke to who weren’t intelligent, talented, and motivated. Many of them came from excellent schools, and the ones who didn’t were clearly exceptionally self motivated. Simply making it past a phone screen is a good sign, and even rejection at that stage is no indication of lack of ability.

However, I can remember many who were not sufficiently prepared for the interview, or worked at too slow a pace, or required too much supervision to solve a problem, or communicated in an unclear way, or failed to translate their ideas into code, or had an attitude that simply wasn’t going to lead them to success in the long term, etc. The definition of “worth hiring” is squishy and varies by company, and the interview process is there to see how well each candidate fits into a given company’s definition.

After reading many reddit comments sections complaining about how they thought interview questions were unnecessarily difficult, I was curious to see if I could still make a “worth it/not worth it” recommendation using an easier problem. My suspicion was that it would give me useful signal while simultaneously making things easier on the candidate’s nerves. I’ll discuss my findings at the end of this post…

All these concerns were top of mind as I was choosing a new question. In a perfect world, I would use one that wasn’t so difficult that it couldn’t be solved in 45 minutes, but at the same time could be elaborated a bit to let stronger candidates show their skills. It would also need to be compact in its implementation, because even though text editor-only chromebooks were beginning to enter the interviewing room at this time, a lot of candidates still used the whiteboard. It was also a major bonus if it was somehow related to Google’s products.

I finally settled on a question some wonderful Googler had carefully written up and inserted into our question database. I’ve reached out to someone I know at Google to confirm that it is still banned, so you shouldn’t expect to see it during your interviews. I’m presenting it in a way that I found effective, with apologies to the original author.

The Question

Let’s talk about measuring distance. A hand is a unit of distance equal to four inches, and is commonly used to measure the height of horses in English-speaking countries. A light year is another unit of distance equal to the distance a particle (or is it wave?) of light travels in a certain number of seconds, equal roughly to one Earth year. On the face of it, these two units have little to do with one another beyond being used to measure distance, but it turns out that Google can convert between them pretty easily:

This might seem obvious: after all, they both measure distance, so of course there’s a conversion. But when you think about it, it’s a little odd: how did they compute this conversion rate? Surely no one actually counted the number of hands in a light year?

Of course not. It turns out you don’t actually need to count this directly. You can just use commonly-known conversions:

• 1 hand equals 4 inches
• 4 inches equals 0.33333 feet
• 0.33333 feet equals 6.3125e-5 miles
• 6.3125e-5 miles equals 1.0737e-17 light years

The aim of this problem is to design a system that will perform this conversion for us. To be precise:

Given a list of conversion rates (formatted in the language of your choice) as a collection of origin unit, destination unit, and multiplier, for example:

foot inch 12

foot yard 0.3333333

etc…

Such that ORIGIN * MULTIPLIER = DESTINATION, design an algorithm that takes two arbitrary unit values and returns the conversion rate between them.

Discussion

I like this problem because it has a pretty intuitively obvious answer: just convert from one rate to another and then to another until you find the goal! I can’t recall a single candidate who encountered this problem and was completely mystified as to how they would solve it by hand. This boded well for my “easier” requirement, since other questions tend to required long minutes of staring and meditating before the candidate arrived at even a basic approach.

And yet, I’ve seen plenty of candidates who weren’t able to drive this intuition to a working solution without significant hints. One of the strengths of this question is that it tests the candidate’s ability to frame a problem in a way that yields to both analysis and coding. As we will see, it also features a very interesting extension that requires yet another conceptual leap.

For context, framing is the act of translating a problem where the solution is not obvious into an equivalent one where the solution yields naturally. If that sounds completely abstract and unapproachable, forgive me because it is. I’ll explain what I mean as I provide the initial solution to this problem. The first part of this solution will be an exercise in framing and application of algorithmic knowledge. The second part will be an exercise in manipulating that knowledge to arrive at a novel and non-obvious optimization.

Part 0: The Intuition

Before we dig deeper, let’s fully investigate the “obvious” solution. Most of the conversions we are asked to perform are simple and straightforward. Any American who’s traveled outside the United States knows that most of the world uses a mysterious unit called a “kilometer” to measure distance. Converting from one to another is as simple as multiplying miles by roughly 1.6.

This is about the depth of complexity that we will encounter for most of our lives. For most units, there’s already a precomputed conversion, and all we need to do is look it up in the appropriate chart. However, for the tougher ones for which we have no direct conversion (such as hands to light years), it’s not unreasonable to plot out a conversion path (duplicated from above):

• 1 hand equals 4 inches
• 4 inches equals 0.33333 feet
• 0.33333 feet equals 6.3125e-5 miles
• 6.3125e-5 miles equals 1.0737e-17 light years

That wasn’t hard at all, I just came up with that conversion using my imagination and a standard conversion chart! Some questions remain, though. Is there a shorter way to do this conversion? How accurate is this rate? Is there always a conversion? Can we automate it? Unfortunately, here is where our naive approach breaks down.

Part 1: The Naive Solution

As nice as it is that this problem has an intuitive solution, that approachability is actually an obstacle to solving this problem. There is nothing harder than learning something you already know, not least because you often don’t know nearly as much about it as you think you do. To illustrate, imagine you’re in an interview room and you’ve got this approach in your head. There’s a number of crucial concerns that the intuitive approach does not enable you to address.

For instance, what if there is no conversion? The obvious approach doesn’t tell you anything about whether there actually is a conversion, and if I were given a thousand conversion rates, I would have a very difficult time determining whether such a conversion exists. Perhaps I’m being asked to convert between unfamiliar (or made up) units called wobbles and a thingles, and I have no idea where to even start. How would the intuitive approach handle that?

I have to admit, that’s kind of a contrived scenario, but there’s another, more realistic one to consider. You’ll notice that my problem statement only includes units of distance. This is very intentional. What if I ask my system to translate from inches to kilogram? You and I both know this can’t be done because those units measure different things, but our input tells us nothing about the “kind” of thing each unit measures.

This is where the careful statement of the question allows strong candidates to shine. Strong candidates think through the edge cases of a system before they design an algorithm, and this problem statement purposefully gives them an opportunity to ask me whether we’ll be translating different units. It’s not a huge deal if they don’t catch this issue early on, but it’s always a good sign when someone asks me “what should I return if there is no conversion?” Stating the question this way gives me an indication of the candidate’s abilities before they write a single line of code.

The Graph Framing

Clearly the naive approach isn’t going to be helpful, so we have to ask ourselves, how can we translate this? The answer is the first leap of insight required by this problem: treat the units as a graph.

In particular, imagine each unit is a node in a graph, and there exists an edge from node A to node B if A can be converted into B:

The edges are labeled with the conversion rate you must multiply A by to arrive at B.

I almost always expected the candidate to come up with this framing, and I rarely gave major hints toward it. I can forgive a candidate not noticing a problem can be solved using disjoint sets, or not knowing enough linear algebra to realize a problem reduces to repeated exponentiation of the adjacency matrix, but every CS program and bootcamp worth its salt teaches graphs. If a candidate doesn’t have the CS skills to know a graph problem when they see one, that’s a “not worth hiring” signal.

Anyway

Framing the problem as a graph unlocks all the classic graph search problems. In particular, two algorithms are useful here: breadth first search (BFS) and depth first search (DFS). In breadth-first search, we explore nodes according to their distance from the origin:

Whereas with depth-first search, we explore nodes in the order in which we encounter them:

Using either of these, we can easily determine whether there exists a conversion from one unit to another simply by performing a search over the graph. We start at the origin unit and search until we find the destination unit. If we fail to find the destination (as when trying to convert inches to kilograms), we know there is no path.

But hang on, something is missing. We don’t want to find whether a path exists, we want to find the conversion rate! This is where the candidate must make a leap: it turns out you can modify any search algorithm to find the conversion rate, simply by keeping additional state as you traverse. Here’s where the illustrations stop making sense, so let’s dive right in to some code.

First off, we need to define a graph data structure, so we’ll use this:

Next, we’ll get to work on DFS. There are many ways of implementing DFS, but by far the most common one I’ve seen is the recursive solution. Let’s start with that:

In a nutshell, this algorithm starts with a node, starts iterating over its neighbors, and immediately visits each by performing a recursive function call. Each function call in the stack stores the state of its own iteration, so when one recursive visitation returns, its parent immediately continues iterating. We avoid visiting the same node twice by maintaining a visited set across all invocations. We also compute the rate by assigning to each node the conversion rate between it and the origin. This way, when we encounter the destination node/unit, we’ve already built up the conversion rate from the origin, and we can simply return it.

This is a fine implementation, but it suffers from two major weaknesses. First off, it is recursive. If it turns out the path we need is more than a thousand or so hops long, we’ll crash. Sure, it’s not likely, but if there’s one thing you don’t want happening in a long-running service, it’s crashing. Second off, even if we were to stop successfully, our answer has some undesirable properties.

I actually already gave you a hint way up at the top of the post. Did you notice how Google says the conversion rate is 1.0739e-17 but the conversion I computed manually came out to 1.0737e-17? It turns out given all the floating point multiplications we’re performing, we have to start worrying about error propagation. The subtleties are a little more than I want to go into for this post, but the gist of it is we want to perform as few floating point multiplications as possible to avoid errors accumulating and causing trouble.

DFS is a fine search algorithm, and if a solution exists it will find it, but it lacks a crucial property: it does not necessarily find the shortest path. This is relevant to us because a shorter path means fewer hops, which means fewer error-propagating floating point multiplications. To get around this, we’ll want to use BFS.

Part 2: The BFS Solution

At this point, if a candidate has successfully implemented a recursive DFS solution and stopped there, I would usually give them at least a weak hire recommendation. They understood the problem, chose an appropriate framing, and implemented a working solution. It’s a naive solution, so I’m not exactly jumping to hire this person, but if they performed well on their other interviews then I’m not going to recommend a rejection.

This bears repeating: when in doubt, write out a naive solution! Even if it’s not fully optimal, having code on the board is an accomplishment, and you can often iterate on it to get to a proper solution. Another way of saying this is: never let work go to waste. Odds are you thought of a naive solution but didn’t want to throw it out there because you know it’s not optimal. If you have a better solution on the tip of your tongue, that’s fine, but if not make sure you bank the progress you’ve made before you move on to more sophisticated things.

From here on out, we’re talking improvements, and the recursive DFS solution’s major weaknesses are that it’s recursive and it doesn’t minimize the number of multiplications. BFS,as we’ll soon see, does minimize the number of multiplications, and it also happens to be very tricky to implement recursively. Unfortunately we’ll have to scrap the recursive DFA solution, as improving on it will require a complete rewrite.

Without further ado, I present an iterative BFS-based approach:

This implementation is functionally very different from the earlier one, but if you looks carefully you’ll notice it does roughly the same thing, with one major change. The biggest change is that while recursive DFS stores the state of what to visit next in the call stack, effectively implementing a LIFO stack, the iterative solution stores it in a FIFO queue.

This is the source of the “shortest path/fewest multiplications” property. We visit nodes in the order in which they are encountered, and so get generations of nodes. The first node inserts its neighbors, and then we visit those neighbors in order, all the while attaching their neighbors, and so on. The source of the shortest path property is that nodes are visited in order of their distance from the origin, so when we encounter the destination, we know there is no earlier generation that could have led to it.

At this point, we’re almost there. There are a few questions we need to answer first, and they both involve coming back to the original problem statement.

First, and most trivially, what if the input unit does not exist? That’s easy, nodes and units are equivalent, so if we can’t find a node with the given name then the unit doesn’t exist. In practice we need to perform a fair bit of string normalization so that “Pound” and “lb” and “POUND” all map to “pound” (or some other canonical representation), but that’s beyond the scope of this question.

Second, what if there is no conversion between two units? Recall that our input only gives us conversions between units, and it gives no indication of whether two units can be converted from one to another. This solution solves for this: conversions and paths are directly equivalent, so if there’s no path from one to another then there’s no conversion. In practice what happens is you end up with disconnected islands of units, one for distances, one for weights, one for currencies, etc.

Finally, if you look carefully at the graph I gave you at the top, it turns out you can’t actually convert between hands and light years using this solution:

Unfortunately, as the conversions were stated, the directed edges mean there is no path from hand to light-year. This is fairly easy to fix, though, since the conversions can be reversed by taking the reciprocal of the rate. We can modify our graph initialization code as follows:

Part 3: Evaluation

That’s it! If a candidate got to this point, I would strongly consider giving them a firm “Hire” recommendation. If you studied computer science or took an algorithms course, you might be saying to yourself “is that really all it takes to pass this guy’s interview?”, to which my answer is “yeah, pretty much.”

Before you think this question is easy, though, let’s consider what a candidate has to do to arrive at this point:

• Understand the question
• Frame the conversion network as a graph
• Realize conversion rates can be mapped to paths through the graph
• Recognize they can use search algorithms to accomplish this
• Choose their favorite algorithm and modify it to track the conversion rate
• If they implemented DFS as a naive solution, realize its weaknesses
• Implement BFS
• Step back and examine the edge cases:
• What if we’re asked for a nonexistent node?
• What if the conversion rate does not exist?
• Realize the reversing the conversions is possible and likely necessary

This question is easier than the others I’ve asked and at the same time just as hard. As with all my previous questions, it requires that the candidate make a mental leap from an abstractly stated question to an algorithm or data structure framing that unlocks progress. The only thing that’s easier is that the algorithm to which they need to leap is less advanced than what other questions required. Outside this algorithmic stuff, the same demands are in place, especially around edge cases and correctness.

“But wait!”, you might ask, “Doesn’t Google have an obsession with runtime complexity? You haven’t asked me the time or space complexity for this problem. What gives?” You might also ask “Hang on, isn’t there a ‘Strong Hire’ rating you can give? How do we earn that?” Very good questions, both. This leads us to our final extra credit round…

Part 4: Can You Do Any Better?

At this point, I like to congratulate the candidate on a well-answered question and make it clear everything from here on out is extra credit. With that pressure gone, we can start to get creative.

So what is the runtime complexity of the BFS solution? In the worst case, we have to consider every single node and edge, making for a complexity of O(N+E), so effectively linear. That’s on top of the O(N+E) complexity of building the graph in the first place. For the purposes of a search engine, this is probably fine: a thousand units is enough for most reasonable applications, and performing a search in memory on each request isn’t an excessive burden.

However, we can do better. To motivate the question, consider what would happen if this code were inserted into a search engine. Some uncommon unit conversions are simply less uncommon than others, and so we’ll be computing them over and over again. Every time we do that, we’ll be performing a search, computing intermediate values, etc.

The first approach I often saw was to simply cache the results of a computation. Whenever a unit conversion is computed, we can always just add an edge between the two conversions. As a bonus, we would get the inverse conversion as well for free! Solved, right?

Indeed, this would give us an asymptotically constant lookup time, but it would come at the cost of storing the additional edges. This actually becomes quite expensive: over time we would tend toward a complete graph, as all pairs of conversions gradually become computed and stored. The number of edges possible in a graph grows with half the square of the number of nodes, so for a thousand nodes we’d need half a million edges. For ten thousand nodes we’d need around fifty million, etc.

Moving beyond the search engine problem, for a graph of a million nodes, we’d gradually tend toward half a trillion edges. That’s simply not reasonable to store, plus we’d waste time inserting things into the graph. We have to do better.

Fortunately, there’s a way to achieve constant-time conversion lookups without incurring quadratic space requirements. In fact, most of what it takes is already right under our noses.

Part 4: Constant Time

So it turns out that the “cache everything” solution is actually not far off from the mark. In that approach, we (eventually) end up with an edge between each node and every other node, meaning our conversion happen in a single edge lookup. But do we really need to store conversion from every node to every node? What if we just stored the conversion rates from one node to every other node?

Let’s take another look at that BFS solution:

Let’s consider what’s happening here: we start with the origin node, and for every node we encounter, we compute the conversion rate from the origin to that node. Then, once we arrive at the destination, we return the rate between the origin and the destination, and we throw away the intermediate conversion rates.

Those intermediate rates are the key here. What if we don’t throw them away? What if instead we record them? All the most complex and obscure lookups become simple: to find the rate from A to B, first find the rate from X to B, then divide it by the rate from X to A, and you’re done! Visually it looks like this:

If we look at the code, it turns out we barely have to modify the BFS solution to compute this table:

The conversions structure is represented by a dict from a unit A to two values: the root for unit A’s connected component, and the conversion rate between the root unit and unit A. Since we insert a unit into this dict on each visitation, we can use the key space of this dict as the visited set instead of using a dedicated visitation set. Note also we don’t have an end node, and instead we iterate over nodes until we run out.

Outside this BFS, we have a helper function which iterates over the nodes in the graph. Whenever it encounters a node that isn’t in the conversions dict, it triggers a BFS starting at that node. This way, we are guaranteed to collapse all nodes into their connected components.

When we need to convert between units, we simple use the conversions structure we just computed:

We handle the “no such unit” case by listening for an exception when accessing the conversions structure. We handle the “no such conversions” case by comparing the roots of the two quantities: if they don’t have the same root, they were encountered through two different BFS calls, meaning they are in two different connected components, and so no path between them exists. Finally we perform the conversion.

That’s it! We’ve now produced a solution that requires O(V+E) preprocessing (no worse than the earlier solutions) but also supports a constant time lookup. In theory, we are doubling the space requirements, but most of the time we no longer need to original graph, so we can simply delete it and use just this one. That being said, the space complexity is actually smaller than the original graph: the graph requires O(V+E) because it has to store all the edges as well as the vertices, whereas this structure only requires O(V), because we no longer need the edges.

Results

If you’ve made it this far, you might recall part of my aim was to test whether an easier problem could be still be useful in selecting worthwhile candidates and whether such a problem could give me a better picture of candidates’ abilities. I’d like to give you some definitive scientific answer, but at the end of the day all I have are anecdotes. However, I did notice some positive results.

If we break solving this problem into four hurdles (framing discussion, algorithm choice, implementation, constant time discussion), almost all candidates made it as far as “algorithm choice” by the end of the interview. As I suspected, the framing discussion turned out to be a good separator: candidates either got it immediately or struggled to grasp it despite substantial hints.

Right away, this is a useful signal. I can understand not knowing advanced or obscure data structures, because let’s be honest, how often are you going to have to implement a disjoint set. Graphs, however, are a fundamental data structure and are taught in just about every introductory level course on the topic. If a candidate struggles to understand them or can’t apply them readily, they are likely going to have a hard time thriving at Google (at least Google circa my employment there, I have no information about the Google of today).

Algorithm choice, on the other hand, turned out not to be a particularly useful source of signal. People who got over the framing stage usually arrived at using this algorithm without much trouble. I suspect this comes from the fact that search algorithms are almost always taught alongside graphs themselves, so if someone is familiar with one they’re likely to know the other.

Implementation turned out to be tricky. Many people had no problems implementing DFS recursively, but as I mentioned above, that implementation is not going to cut it in a production setting. To my surprise, the iterative BFS and DFS implementations do not seem to be at the tips of peoples’ fingers, and I often found that even after I gave substantial hints, people often faltered.

In my mind, since making it all the way through to the implementation stage earned a “Hire” from me, the “constant time discussion” stage was extra credit in my mind. While I went into detail in this post, I found it was usually more productive to have a verbal discussion instead of expecting code. Very few candidates got this one immediately. I often had to give substantial hints to lead people to this solution, and even then many people didn’t grasp it. Which is fine, the “Strong Hire” rating is supposed to be hard to achieve.

But Wait, There’s More!

That’s most of this problem, but if you’re interested in exploring this problem further, there’s a whole host of extensions I won’t be diving into. I leave the following as exercises for the reader:

First, a warm-up: in the constant time solution I laid out, I chose the root node of each connected component arbitrarily. In particular, I use the first node of that component we encounter. This is not optimal, because for all we know we’ve chosen some node way off on the fringes of the graph, while some other node might be more central and so have shorter paths to all other nodes. Your assignment is to replace this arbitrary choice with one which minimizes the number of multiplications required and this the floating point error propagation.

Second, this whole discussion assumes all equal-length paths through the graph are created equal, which isn’t always the case. One interesting variant of this problem is currency conversions: nodes are currencies, and edges from A to B and vice-versa are the bid/ask prices of each currency pair. We can rephrase the unit conversion question as a forex arbitrage question: implement an algorithm that, given a currency conversion graph, computes a cycle through the graph that can leave a trader with more money than when they started. Assume no transaction fees.

Finally, a real doozie: some units are expressed as a combination of various basic units. For instance, the watt is defined, in SI units, as “kilogram meters squared by seconds cubed”. The final challenge is to extend this system to support converting between these units given only the definitions of the basic SI units.

If you have questions, feel free to PM me on reddit.

Conclusion

When I chose to start using this problem, I hoped it would be a little easier than the ones I had asked before. I found my experiment was largely a success: people who did well on it generally aced it immediately, leaving us with plenty of time to talk about the advanced constant time solution. People who struggled tended to struggle in places other than the algorithmic conceptual leap: they couldn’t quite frame the problem in a useful way, or they sketched out a good solution but were unable to translate it into working code. Regardless of whether and where they struggled, I found I was able to give meaningful information about candidates’ strengths and weaknesses.

For your part, I hope you found this post useful. I realize it might not be as much of an algorithmic roller coaster as some of my previous editions, but the truth is that for all the algorithm-heavy reputation software interviewing has acquired, there’s a lot of complexity even in using a simple, well-known method. If you’d like to see code, take a look at this series’ github repo for more.

My next post will take a different angle. Switching from engineering to management has allowed me to experience the hiring process from a completely different point of view. I’m going to share my thoughts on how companies like Google and Reddit hire, and hopefully shed some light on the mysteries of the hiring process. If this sounds up your alley, make sure to follow me on Twitter or Medium to be notified once it comes out. You can also join our discord to ask questions and discuss with others.

Join our discord to discuss these problems with the author and the community!

Welcome to another edition of Google Interview Problems Deconstructed, a series in which I present the interview problems I used to use to interview candidates at Google until they were leaked and banned from use in interviews. My loss is your gain, however, because once they’re out in the world I can write them up and explain them to you.

Before I dive in, I have some exciting news: I’ve left Google! I’m excited to announce that I’ve joined Reddit as an engineering manager in NYC! I’m still gonna publish this series, though, so stay tuned.

A disclaimer: while interviewing candidates is one of my professional responsibilities, this blog represents my personal observations, my personal anecdotes, and my personal opinions. Please don’t mistake this for any sort of official statement by or on behalf of Google, Alphabet, Reddit, or any other person or organization.

The Question

One of the criticisms I get about the knight’s dialer question I described in the last two posts is that it’s not a realistic problem. As helpful as it might be to probe a candidate’s thinking, I admit it’s ultimately a bit of an unrealistic exercise. (I do have some thoughts about whether it’s important to have a correlation between interview questions and reality, but I’m going to save them for a future post. Rest assured, comment sections everywhere, I hear you and I have things to say. Just not now.)

In the meantime, when the knight’s dialer was banned a few years ago, I took the feedback to heart and tried to replace it with a question that’s a little more relevant to Google. And what can be more relevant to Google than the mechanics of search queries? I found this question and used it for a good long time before it was also leaked and banned. As before, I’ll present the question, dive into its explanation, and then discuss how I used this question in interviews and why I like it:

Imagine you operate a popular search engine and in your logs you observe two queries, let’s say “obama approval ratings” and “obama popularity rate.” (If I recall correctly, these were the actual examples used in the interview problem database, which dates the question a bit…) Those two queries are different strings, but I think we can all agree that they’re basically searching for the same thing, and should be considered equivalent when counting queries, showing results, etc. How can we detect that two queries are synonymous?

Let’s formalize this. Suppose you’re given two inputs. First, a list of pairs of strings representing synonyms where the two strings in the pair are synonymous with one another. Secondly, a list of pairs of strings representing queries.

To make this concrete, here is a sample input to illustrate:

Your task is to output a list of boolean values such that each entry in the output indicates whether the corresponding pair of queries are synonymous.

Questions, Questions

On the face of it, this is a simple problem. However, the closer you look, the more complex it becomes. Right off the bat, it becomes clear this problem is pretty under-defined. Can words have multiple synonyms? Does word order matter? Are synonym relationships transitive, meaning if A is synonymous with B, and B is synonymous with C, does that mean A is synonymous with C? Can synonyms span multiple words, such as how “USA” is synonymous with “United States of America” or “United States”?

This ambiguity immediately gives good candidates an opportunity to set themselves apart. The first thing a good candidate does is sniff out these sorts of ambiguities and try to resolve them. How they do this varies from candidate to candidate: some step up to the whiteboard to try to manually solve specific cases, whereas some take one look at the question and see the gaps immediately. In any case, spotting these issues early is crucial.

I place a lot of importance on this question’s “problem understanding” phase. Software engineering is what I like to call a fractal discipline, meaning it shares a quality with fractals where zooming in reveals additional complexity. Just when you think you understand a problem, you look closer and realize there’s a subtlety you overlooked, or there’s an implementation detail you can improve on, or there’s a new way of framing the problem that reveals additional insight.

An engineer’s caliber is largely determined by how deeply they can understand a problem. Transforming a vague problem statement into a detailed set of requirements is step zero in this process, and purposefully under-defining the problem allows me to assess how well a candidate approaches novel situations.

As an aside, there are also the trivial questions like “does capitalization matter?” that, unbeknownst to the candidate, don’t affect the core algorithmic problem. For these questions, I always give whatever answer is easiest on the candidate (in this case, “assume everything is already preprocessed to be lowercase”).

Part 1: The (Not So) Simple Case

However candidates arrive at these questions, they inevitably end up asking me for an answer, and I always start off with the simplest case possible: words can have multiple synonyms, order matters, synonyms are not transitive, and synonyms can only map from one word to another. This makes for a pretty limited feature in a search engine, but there’s more than enough subtlety in it to make for an interested interview question.

The high-level overview of the solution is as follows: break the query up into words (splitting along spaces is fine), and compare pairs of corresponding words to see if they are either identical or synonymous with one another. Visually, it looks like so:

In implementation, it looks a little something like this:

Easy, right? Algorithmically, this is pretty simple. No dynamic programming, no recursion, no tricky data structures, etc. Just simple, straightforward manipulation of the standard library, and a linear time algorithm, right?

You’d think, but there’s more subtlety here than you’d see at first glance. By far the trickiest component of this simple algorithm is the synonym comparison. While simple to understand and describe, there are a lot of ways the synonym comparison component can go wrong. I’ll go into some of the more common ones I’ve seen here.

To be clear, none of these mistakes are disqualifying in my mind; if the candidate produced an implementation with an error, I would simply point it out, they would adjust their solution, and we would move on. However, an interview is, first and foremost, a battle against time. Making, noticing, and correcting mistakes is expected, but it saps time that could be spent elsewhere, such as producing a more optimal solution. Very few candidates make no mistakes, but candidates who make fewer make more progress simply because they spend less time cleaning up after themselves.

This is why I like this problem: unlike the knight’s dialer, which requires a flash of algorithmic insight followed by a (hopefully) simple implementation, this question requires a multitude of small, incremental steps in the right direction. Each step represents a tiny hurdle over which the candidate can either leap gracefully or trip and have to recover. Good candidates avoid these little pitfalls using their experience and intuition and are rewarded with a more fleshed-out and correct solution, while weaker ones waste time and energy on mistakes and are usually left with buggy code.

While every interview saw a different mix of leaps and faceplants, here is a small sampling of the more common errors I saw.

Accidental Runtime Killers

First off, some candidates implemented the synonym detection using a simple traversal of the synonyms list:

On the face of it, this seems reasonable. On closer inspection, this is a very, very bad idea. For those of you who don’t know Python, the in keyword is syntactic sugar for a contains method, and works over all standard Python containers. This is a problem here because synonym_words is a list, which implements the in keyword using linear search. Python users were especially susceptible to this mistake because the language hides types, but C++ and Java users occasionally made similar errors.

In my entire career, I’ve only written code that uses linear search a handful of times, and every time it involved lists that were no more than two dozen elements long, and even then I included a long comment to let readers know why I chose such a seemingly-suboptimal approach. I suspect the reason some candidates used it is because they simply didn’t know the Python standard library well enough to know how the in keyword is implemented over lists. It’s an easy mistake to make, and it’s not the end of the world, but showing a lack of familiarity with your language of choice is not a good look.

In terms of practical advice, this is actually an easy mistake to avoid. First off, never forget the types of your objects, even if you’re using an untyped language like python! Second, remember that when you use the in keyword on a list, that’s a linear search. Unless that list is guaranteed to always be very small, it’s going to be a performance killer.

Reminding candidates that the input structure is a list is usually enough to rouse them. What happens after I give a hint is very informative. The better candidates immediately think to preprocess the synonyms somehow, which is a good start. However, that approach is not without its pitfalls…

Use the Right Data Structure

From the code above, it’s immediately obvious that in order to implement this algorithm in linear time, we need a constant-time synonym lookup. And b behind every constant-time lookup, there’s always a hashmap or a hashset.

Which of these two the candidate chooses is less interesting to me than what they put in it. (By the way, never use a dict/hashmap that goes to True or False. That’s called a set.) Most candidates settle on some sort of dict/hashmap. The most common error I see is a subconscious assumption that each word can have at most one synonym:

I don’t really penalize candidates for making this mistake. The example input is purposefully designed to not call to mind that words can have multiple synonyms, and some candidates simply haven’t had this edge case occur to them. Most quickly correct themselves after I point out this error. Good candidates save themselves the trouble by noticing it early, but it’s usually not a major loss of time.

A slightly more serious problem is not realizing that the synonym relationship goes both ways. You’ll notice the above code does this. Correcting this, however, can be error prone. Consider the following approach to implementing this property:

Why perform two insertions and use double the memory when you can use no additional memory and perform two checks?

The takeaway: always ask yourself if you can do less work! In hindsight, permuting the lookup is an obvious way of saving time if you look for it, but using a suboptimal implementation suggests the candidate didn’t think to look for ways to optimize. Again, I’m happy to give a hint, but it’d be better if I didn’t have to.

Sorting?

Some of the more clever candidates think to sort the synonyms list, and then use binary search to determine if two words are synonyms. This approach actually has the major advantage of not requiring any additional space besides the input synonym list (assuming modifying the input list is acceptable).

Unfortunately, the time complexity isn’t great: it takes Nlog(N) time to sort the synonym list, and then log(N) time to lookup each synonym pair, whereas the preprocessing solution described above happens in linear and then constant time. Plus, making a candidate implement both sorting and binary search on a whiteboard is a no-no in my book because 1. sorting algorithms are very well-known, so for all I know the candidate might be regurgitating, and 2. these algorithms are devilishly tricky to get right, and oftentimes even the best candidates will make mistakes that don’t tell me anything about their ability to program.

Whenever a candidate offered this solution, I would ask for the runtime complexity and ask if they can do better. As an aside: if an interviewer asks if you can do better, most of the time the answer is “yes.” If I ever ask you that question, the answer is always “yes”.

Finally, the Solution

Hopefully at this point the candidate has produced something correct and optimal. Here is a linear time, linear space implementation for this introductory statement:

A few super-quick notes:

• Notice the use of dict.get(). You could type out the “check if the key is in the dict and then get it” implementation, but that’s cluttered whereas this way you can show off your knowledge of the standard library.
• I’m personally not a fan of code that uses a whole lot of continues, and some style guides ban or discourage their use. I actually introduced a bug in my initial implementation of this code by omitting the continue after the query length check. It’s not bad, just know that it’s error prone.

Part 2: It Gets Harder!

With good candidates I would often find myself with at least ten or fifteen minutes left. Fortunately, there are tons of follow-up questions I can ask, but we’re not likely to get much code written in that time. At the end of the day, though I think I don’t need to. I want to know two things about a candidate: can they design algorithms? and: can they code? The knight’s dialer answers the algorithm design question first and examines coding after, whereas this question gets answers in reverse order.

By the time a candidate has completed the first part of this question, they’ve already solved a (surprisingly nontrivial) coding problem. At this point, I can confidently speak to their ability to design rudimentary algorithms, and to translate their ideas into code, as well as their familiarity with their favorite language and standard library. The question then becomes a lot more fun for me because the coding requirements can be relaxed and we can dive into the algorithmic component.

To that end, let’s return to the basic assumptions of the first part: word order matters, synonym relationships are not transitive, and synonyms cannot multiple words. As the interview progresses, I reverse each of these constraints, and in this new post-coding phase the candidate and I have a purely algorithmic discussion. I’ll be producing code samples to illustrate my point, but in an actual interview I’d be talking in purely algorithmic terms.

Before I dive in, I’ll explain my expectations by saying that the follow-ups are basically “extra credit.” My personal approach to this question is to assign candidates who absolutely nail the first section a “Hire” rating, and to use next section to separate the “Hire” candidates from the “Strong Hire” candidates. A “Hire” rating is a strong rating that says “I believe this person is good enough to work here,” whereas a “Strong Hire” says “I believe this person is excellent and hiring them would represent a great win for the company.”

Transitivity: Naive Approaches

The first constraint I like to relax is the one around transitivity, meaning that if words A and B are synonymous, and if words B and C are synonymous, then words A and C are synonymous. Sharp candidates quickly realize they can adapt their earlier solution to solve this because they’re still determining whether simple pairs of words represent synonym pairs, whereas the other relaxations invalidate the core logic of the earlier algorithm.

To that end, how do we do that? One common approach is to maintain a complete set of synonyms for each word, based on the transitive relationships. Every time we insert a word into the synonym set, we also add it to the corresponding sets for all the words currently in that set:

This solution works, but it’s far from optimal. To see why, consider the space complexity of this solution. Every time we add a synonym, we have to not only add to the start word’s set, but also to the sets belonging to all the words with which that word is synonymous. If it’s synonymous with one word, we have to add one entry. If it’s synonymous with fifty words, we have to add fifty more entries. Illustrated, it looks like this:

Note we’ve gone from 3 keys and 6 entries to 4 keys and 12 entries. A word with 50 synonyms would require 50 keys and almost 2,500 entries. The space required to represent one word grows quadratically with the size of its synonym set, which is pretty wasteful.

There are other solutions, but in the interest of space I won’t dive too far into them. The most interesting one involves using the synonyms data structure to construct a directed graph, and then using breadth-first search to find whether there exists a path between two words. This is a fine solution, but the lookup becomes linear in the size of that word’s synonym set. Since we’re performing that lookup multiple times for each query, that approach is very much suboptimal.

Transitivity: Using a Disjoint Set

It turns out we can lookup synonym relationships in (almost) constant time by using a data structure called a disjoint set. This structure is called a set, but it offers somewhat different capabilities than what most people think of when they hear the word “set.”

The usual set structure (hashset, treeset) is a container which allows you to quickly determine if an object is in or out of that set. A disjoint set solves a very different problem: rather than concerning itself with whether a particular item is in a set, it allows you to determine if two items belong to the same set. What’s more, it does this with a blindingly fast O(a(n)) time, where a(n) is the inverse of the Ackerman function. Unless you’ve taken an advanced algorithms course you can be forgiven for not knowing this function, and for all reasonable inputs it’s effectively equal to constant time.

At a high level, the algorithm operates as follows. Sets are represented by trees where each item has a parent. Since every tree has a root (meaning an item that is its own parent), we can determine if two items belong to the same set by following their parents until we find a root element for each. If the two elements have the same root, they must belong to the same set. Joining sets is easy too: we simply find the root elements and make one the root of the other.

So far, so good, but there’s clearly no blinding performance just yet. The genius of this structure is in a procedure called compaction. Suppose you have the following tree:

Imagine you want to know whether “speedy” and “hasty” are synonyms. Starting from each, you traverse the parent relationships and find that they both share “fast” as a root node, therefore they must be synonyms. Now suppose you want to know if “speedy” and “swift” are synonyms. You would, once again, start at each node and traverse up until you reached “fast,” but this time you might notice that you’ve duplicated the traversal for “speedy.” Can you avoid this duplicate work?

Yes you can, it turns out. In a way, every element in this tree is destined to arrive at “fast.” Instead of traversing the tree multiple times, why not simply change the parent of each element along the way to “fast” and save ourselves the work? This process is called compaction, and in a disjoint set it’s built into the root-finding operation. For example, after we determine if “speedy” and “hasty” are synonyms, the above tree will look something like this:

Now, all subsequent accesses will happen in constant time because every node in this tree points to “fast.” Analyzing the proper time complexity of this structure’s operations is nontrivial: it’s not really constant, because it depends on the depth of the trees, but it’s not very much worse than constant, because things amortize to constant time very quickly. For our analysis, we’ll do the lazy thing and just call it constant time.

With that concept in hand, here’s a disjoint set implementation that provides exactly the functionality we need for this problem:

Using this structure, we can preprocess the synonyms and solve this problem in linear time.

Evaluation and Notes

At this point, we’ve reached the limit of what I’ve seen done in the 40–45 minutes of an interview. I gave any candidate who completed the introductory portion and made significant progress toward describing (not implementing) the disjoint set solution a “Strong Hire” rating and proceeded to let them ask me questions. I’ve never seen a candidate get this far with much time to spare.

This leaves us with a few more follow-ups: a version of this question where word order doesn’t matter, and one where synonyms can span multiple words. The solutions to each of these are challenging and delightful, but in the interest of space I’ll address them in a followup post.

This question is useful because it allows candidates to make mistakes. Day-to-day software engineering consists of a never-ending cycle of analysis, execution, and refinement. This problem provides candidates with opportunities to demonstrate their command of each of these stages. Consider the skills you need to earn a “Strong Hire” on this question:

• Analyze a problem statement and recognize where it is ambiguous and under-defined, clarifying where necessary to develop an unambiguous problem statement. Continue doing this as you progress through a solution and encounter new questions. For maximal efficiency, do as much of this stage as early as possible because recovering from errors becomes more costly as your work progresses.
• Frame the problem in such a way that makes it easier to approach and solve. In this case, the most important point is the observation that you can line up corresponding words in the queries.
• Implement your solution. This involves choosing optimal data structure and algorithms, as well as designing your logic to be readable and easy to modify in the future.
• Circle back and try to spot bugs and errors. These could be actual bugs like how I forgot to insert a “continue” statement above, or performance bugs like using an incorrect data structure.
• When the problem definition changes, repeat this process and adapt your solution whenever appropriate, and scrap it where not. Knowing when to do both is a critical skill, both in an interview and in the real world.
• Keep your data structures and algorithms knowledge at your fingertips. The disjoint set data structure is not exactly a common structure, but it’s not really that rare and refined either. The only way you can ensure you know the tool for the job is by learning as much as you can.

None of these skills can be learned from textbooks (except maybe for the data structures and algorithms). The only way to acquire these skills is through regular and extensive practice, which aligns well with what companies want: candidates who mastered their skills, and are practiced enough to apply them effectively. Detecting these people is the point of an interview, and this question served me well for a long time.

Looking Forward

As you can probably deduce from my writing this post, this question was eventually leaked, too. Since then, I’ve been using several questions, depending on my mood (asking one question all the time gets boring) and on what the candidate’s earlier interviewers had asked. Some of them are still in use, so I’ll keep them a secret, but some are not! You can look forward to seeing the later ones in future posts.

In the short term, however, I have two more posts coming down the pike. First, as promised above, I’ll be writing up and publishing the remaining two follow-ups to this question. Not because they ever came up in interviews, but because they’re interesting in and of themselves. I’ll also share my reflections and personal opinions on the hiring process in the tech world, which is especially interesting to me now that I’m hiring engineers for my own team at Reddit.

As always, if you’d like to stay up to date with this series, follow me on Twitter or Medium. If you enjoyed this post, be sure to clap or leave a comment. I love the feedback, and I use it to tell what’s working and what isn’t.

Thanks for reading!

Update: Now that I’ve got a number of posts up, here is a listing of all other the posts in this series:

• Introduction
• Knight’s Dialer
• Knight’s Dialer Followup
• Ratio Finder

P.S.: You can check out the code at this series’ GitHub repo, or you can play with the code live thanks to my good friends at repl.it. You can also join our discord to ask questions and go deeper into these problems.

Join our discord to discuss these problems with the author and the community!

This is the second post in my series where I lay out my favorite interview questions I used to ask at Google until they were leaked and banned. This post is a continuation of the first one, so if you haven’t taken a look yet, I recommend you read it first and come back. If you don’t feel like it, I’ll still do my best to make this post sensible, but I still recommend reading the first one for some background.

First, the obligatory disclaimer: while interviewing candidates is one of my professional responsibilities, this blog represents my personal observations, my personal anecdotes, and my personal opinions. Please don’t mistake this for any sort of official statement by or about Google, Alphabet, or any other person or organization.

Apologies for the delay, by the way. In the time since I published the first part of this series, I’ve gone through a number of (very positive) changes in my life, and as a result writing sort of fell by the wayside for a while. I’ll share what I can as things become public.

This post goes way above and beyond what I would expect to see during a job interview. I’ve personally never seen anyone produce this solution, and I only know it exists because my colleague mentioned that the best candidate he had ever seen had blasted through the simpler solutions and spent the rest of the interview trying to develop this one. Even that candidate failed, and I only arrived at this solution after weeks of on-again, off-again pondering. I’m sharing this with you for your curiosity and because I think it’s a cool intersection of mathematics and programming.

With that out of the way, allow me to reintroduce the question:

The Question

Imagine you place a knight chess piece on a phone dial pad. This chess piece moves in an uppercase “L” shape: two steps horizontally followed by one vertically, or one step horizontally then two vertically:

Suppose you dial keys on the keypad using only hops a knight can make. Every time the knight lands on a key, we dial that key and make another hop. The starting position counts as being dialed. How many distinct numbers can you dial in N hops from a particular starting position?

At the end of the previous post, we had developed a solution that solves this problem in linear time (as a function of the number of hops we’d like to make), and requires constant space. This is pretty good. I used to give a “Strong Hire” to candidates who were able to develop and implement the final solution from that post. However, it turns out we can do better if we use a little math…

Adjacency Lists

The crucial insight of the solutions in the previous post involved framing the number pad as a graph in which each key is a node and the knight’s possible next hops from a key are that node’s neighbors:

In code, this can be represented as follows:

This is a fine representation for a number of reasons. First off, it’s compact: we represent only the nodes and edges that exist in the graph (I include number 5 for completeness, but we can remove it without any repercussions). Second off, it’s efficient to access: we can get the set of neighbors in constant time via a map lookup, we can iterate over all neighbors of a particular node in time linear to the number of neighbors by iterating over the result of that lookup. We can also easily modify this structure to determine the existence of an edge in constant time by using a sets instead of tuples.

This data structure is known as an adjacency list, named after the explicit listing of adjacent nodes to represent edges. This representation is by far the most common method of representing graphs, chiefly because of its linear-in-nodes-and-edges space complexity as well as its time-optimal access patterns. Most computer scientists would look at this representation and say “pack it up, that’s about as good as it gets.”

Mathematicians, on the other hand, would not be so happy. Yes, it’s compact and fast to operate on, but mathematicians are (by and large) not in the business of pragmatic ease of use like most computer scientists and engineers. A computer scientist might look at this graph data structure and say “how does this help me design efficient algorithms?” whereas a mathematician might look at it and say “how does this representation allow me to use the rest of my theoretical toolkit?”

With that question in mind, the mathematician might be disappointed by this representation. Personally, this representation of a graph rhymes with nothing I’ve encountered during my mathematical education. It’s useful for writing algorithms, but that’s pretty much it.

Graphs as Matrices

There is another, more fruitful, way to represent a graph, though. You’ll notice a graph is all about relationships between nodes. In the case of an adjacency list, we relate each node with the nodes it’s connected to. Why not instead focus on pairs of nodes? Instead of asking “what nodes are connected to one another with an edge,” you can ask “given a pair of nodes, is there an edge that connects them?”

If this seems like a sort of “six of one, half dozen of another” situation, it is. But the second formulation is magical because it calls into focus something that’s invisible in the adjacency list representation: suddenly we’re very interested in pairs of nodes that don’t have edges. Rather than starting with nodes and computing only the relevant pairs, we start with all possible pairs, and decide whether or not they are relevant later.

We can reframe the adjacency list as follows. Note for each pair (A, B), NEIGHBORS_MAP[A][B] will be 1 if that pair represents an edge in the graph and 0 otherwise:

Why would we do this? Certainly not to create a more efficient data structure. Our space complexity has gone from being proportional to the number of edges to the number of possible edges, which means N squared, where N is the number of nodes. Iterating over neighbors also just got more expensive: for a given node we get a bunch of irrelevant zeros that we have to filter through.

A mathematician, on the other hand, just got interested. Anyone beyond the junior year of a mathematics undergrad should look at this and immediately say “that’s a matrix!”

(For the sake of brevity, I’ll assume here that you know enough about linear algebra and matrix multiplication to follow along with this post. If you don’t, you can find a great introduction here.)

The wonderful thing about matrices is that they support an algebra. Matrices can be added, subtracted, and multiplied with one another, according to some simple rules. What this particular representation lacks in compactness, it more than makes up for in abstract ease of manipulation.

An Aside

A slight digression: “okay cool”, you might say, “we’ve represented the graph as a matrix. And that matrix can be multiplied by another matrix. What does this have to do with the graph? Who cares?” This is a much more valid question that you may realize, and the answer is “nothing, yet.” Undergrads are my intended audience, so I feel obligated to put you in the right frame of mind before I continue because I’m afraid this might otherwise be more discouraging than enlightening.

After you finish reading this logic presented in the rest post, you may be tempted to ask yourself “how the hell was I supposed to come up with that?” I certainly had that reaction time and time again while reading proofs and textbooks. The short answer is: you’re not. At least not immediately. The more proofs and theorems you learn, the more you’ll find you’re able to spot patterns and apply your knowledge. I suggest treating this post as just another tidbit to know and hopefully apply later.

Down to Business

Alright, now that that’s out of the way, let’s get down to the solution. First we’ll explore the structure of this matrix a little. (Note all indices are offsets from zero. This is a departure from mathematical tradition, but this is a CS-oriented post, so let’s go with it.) In this matrix, each row represents the destinations accessible from each key: row 0 has a 1 in position 4 to show you can hop from 0 to 4. It has a 0 in position 9 to show you can’t hop from 0 to 9.

The rows also have a meaning. While the rows represent where you can go from the corresponding position, the columns represent how can get to each position. If you look closely, you’ll notice that the rows and columns look strikingly similar: the i-th position in each row is the same as the i-th position in each column. This is because this graph is undirected: each edge can be traversed in both directions. As a result, the entire matrix can be flipped along its main diagonal and emerge unchanged (the main diagonal is formed by the positions where the row and column numbers are equal).

Now that we’ve introduced representing the graph as a matrix, it’s no longer an algorithmic object but an algebraic one. The particular algebraic operation we’ll be concerned with is matrix-vector multiplication. What happens when we multiply this matrix by a vector? Recall that the formula for multiplying an R row by C column matrix A with an C-length column vector v (short for a matrix with C rows and 1 column) is:

In words, this means that the resulting C-length vector can be computed by taking each row, multiplying each element of that row by the corresponding element in the vector, and adding the component values together. The results are then placed in a vertical, C-by-one matrix, or a C-length vector for short.

This may seem uninteresting at first glance, but that algebraic relation up there is actually the crux of this entire solution. Consider what it means. Each row represents the numbers you can reach from that row’s corresponding key. With this in mind, matrix multiplication is no longer an abstract algebraic operation, it’s a means of summing values corresponding to destinations from a given key on the dialpad.

To make the implications clear, recall the recurrence relation from my previous post:

caption: Remember T represents the number of distinct sequences you can dial from key K in N hops

This is nothing more than a weighted sum of values corresponding to destinations from a given key on a dialpad! This framing ignores edges that aren’t in the graph by not even considering them in the iteration, whereas the matrix-oriented one includes them, but only as multiplications by zero that don’t affect the final sum. The two statements are equivalent!

So then what is the meaning of the vector v in all this? So far we’ve been talking almost entirely about the matrix, and we’ve mostly ignored the vector. We can choose any v we want, but we want to choose one that will be meaningful in this calculation. The recurrence relation provides us with a hint: in that case, we start with T(K, 0), which is always 1 because in zero hops we can only dial the starting key. Let’s see what happens with a v where all the entries are 1:

Multiplying the transition matrix by the 1 vector gives us a vector where each element corresponds to the count of numbers that can be dialed in 1 hop. Multiplying again, we can:

Now each element in the resulting vector equals the count of numbers that can be dialed from the corresponding key in 2 hops! We’ve just developed a new linear-time solution to the Knight’s Dialer Problem. In particular:

Logarithmic Time

But this solution is still linear. We need to multiply A by the vector v again and again and again, N times. If anything, this solution is actually slower than the dynamic programming solution we developed in the previous post because this one requires unnecessarily multiplying by zero a whole bunch of times.

There is, however, another algebraic property we can use: matrices can be multiplied, and anything that can be multiplied can be exponentiated (to an integer power). Our solution becomes the following:

How do we compute A^N? Naturally, one way is to repeatedly multiply A by itself. However, this is somehow even more wasteful than multiplying by the vector: rather than multiplying one vector by A again and again, we multiply all the columns of A again and again. There is a better way: exponentiation by squaring.

As you probably know, every number has a binary representation. If you’ve been studying computer science you already know that this the preferred way of representing a number in hardware. In particular, every number can be represented as a sequence of bits:

Where k is the largest nonzero bit. For example, 49 in binary is “110001,” or:

Something interesting happens when we perform this expansion for N in our matrix exponentiation solution:

This results in a total of k matrix multiplications. How does k relate to N? k is equal to the number of bits required to represent N, which as you may already know is equal to log2(N). Instead of requiring a number of multiplications that grows linearly in N, we only need a logarithmic number of matrix multiplications! This hinges on a few useful facts:

• A to the power of zero is the identity matrix. Multiplying any matrix by the identity matrix results in the original matrix. As a result, if any bit is zero, we’ll end up multiplying by the identity matrix, and it’ll be as though we ignored it.
• We can compute A to any power of two by squaring the result again and again. A squared is A times A. A to the 4th is A squared times A squared, etc.

This is it! We now have a logarithmic solution.

While this solution requires a little more code than the previous ones on account of the definition of matrix multiplication, it’s still quite compact:

Wrapping Up

On the face of it, this solution seems awesome. It features logarithmic time complexity and constant space complexity. You might think it really doesn’t get any better than that, and for this particular problem you would be right.

However, this matrix exponentiation-based approach has one glaring drawback: we need to represent the entire graph as a (potentially very sparse) matrix. This implies we’ll have to explicitly store a value of every possible pair of nodes, which requires space quadratic in the number of nodes. For a 10-node graph like this one, that isn’t a problem, but for more realistic graphs which might have thousands if not millions of nodes, it becomes hopelessly infeasible.

What’s worse, the matrix multiplication I gave up there is actually cubic in the number of rows (for square matrices). The best-known matrix multiplication algorithms like Strassen or Coppersmith–Winograd have sub-cubic runtimes, but either require extreme memory overhead or feature constant factors that negate the effects for matrices of reasonable size. A cubic-time matrix multiplication starts to become unreasonable with graphs with sizes around the ten thousand range.

At the end of the day, none of these limitations really matter in my mind. Let’s be honest: how often are you going to be computing this on any realistic graph? Feel free to correct me in the comments, but I personally can’t think of any practical application of this algorithm.

The main purpose of this problem is to evaluate candidates on their algorithm design chops and coding skills. If a candidate makes it anywhere near the things I discussed in this post, they’re probably a lot more qualified for the Google SWE job than I am…

If you liked this post, applaud or leave a response! I’m writing this series to educate and inspire people, and nothing makes me feel quite as good as receiving feedback. Also, if this is the sort of stuff you enjoy, and if you’re all the way down here there’s a good chance it is, give me a follow! There’s a lot more where this came from. If you want to ask questions or discuss with like-minded people, join our discord!

Also, you can find runnable the code for this and the previous post here.

Next Steps

After this question was banned I felt like I wanted to start asking a more straightforward programming question. I searched far and wide for a question that was simple to state, had a simple solution, allowed for many levels of followup questions, and had an obvious tie to Google’s products. I found one. If that sounds like something you’d like to read about, stay tuned…

Update: Now that we’re up and running, here is a listing of all the other posts in this series:

• Introduction
• Knight’s Dialer
• Synonymous Queries
• Ratio Finder

Join our discord to discuss these problems with the author and the community!

This is the second in a series of posts in which I share my advice for candidates interviewing for tech companies, drawing on my experience as an engineer and interviewer at Google. If you haven’t already, take a look at the introduction to this series.

Before I start, a disclaimer: while interviewing candidates is one of my professional responsibilities, this blog represents my personal observations, my personal anecdotes, and my personal opinions. Please don’t mistake this for any sort of official statement by or about Google, Alphabet, or any other person or organization.

This was the first problem I used during my interviewing career, and it was also the first to leak and get banned. I like it because it hits number of sweet spots:

• It’s easy to state and understand.
• It has a number of solutions, each requiring varying degrees of algorithms and data structures knowledge. Also, a little bit of insight goes a long way.
• Each solution can be implemented in relatively few lines, making it perfect for a time-constrained environment.

If you’re a student or otherwise applying to tech jobs, my hope is that you’ll come away from reading this with a better understanding of what to expect from interview problems. If you’re an interviewer, I’d like to share my thought process and stylistic approach to interviewing, the better to inform others and solicit comments.

Note I’ll be writing code in Python. I like Python because it’s easy to learn, compact, and has an absolutely massive standard library. Candidates like it, too: even though we impose no language constraints, 90% of people I interview use Python. Also I use Python 3 because c’mon, it’s 2018.

The Question

Imagine you place a knight chess piece on a phone dial pad. This chess piece moves in an uppercase “L” shape: two steps horizontally followed by one vertically, or one step horizontally then two vertically:

Suppose you dial keys on the keypad using only hops a knight can make. Every time the knight lands on a key, we dial that key and make another hop. The starting position counts as being dialed.

How many distinct numbers can you dial in N hops from a particular starting position?

Discussion

Every interview I conduct basically breaks down into two parts: first we find an algorithmic solution and then the candidate implements it in code. I say “we” find a solution because I’m not a mute spectator: 45 minutes is not a lot of time to design and implement anything under the best circumstances, never mind under pressure. I let candidates take the lead in the discussion, generating ideas, solving instances of the problem, etc., but I’m more than happy to give a nudge in the right direction. The better the candidate, the fewer hints I tend to have to give, but I have yet to see a candidate who required no input from me at all.

I should underscore this, because it’s important: as an interviewer, I’m not in the business of sitting back and watching people fail. I want to write as much positive feedback as I can, and I try to give you opportunities to allow me to write good things about you. Hints are my way of saying “okay, I’m gonna give this bit to you, but only so you can move on and show me what you’ve got on the other parts of the question.”

With that being said, your first action after hearing the question should be stepping up to the whiteboard and solving small instances of the problem by hand. Never dive right into code! Solving small instances lets you spot patterns, observed and edge cases, and also helps crystallize a solution in your head. As an example, suppose you start on 6 and have two hops to make. Your sequences will be…

• 6–1–8
• 6–1–6
• 6–7–2
• 6–7–6
• 6–0–4
• 6–0–6

…for a total of six sequences. If you’re following along, try taking a pencil and paper and deriving these. This doesn’t translate well into a blog post, but trust me when I say there’s something magical about working out a problem by hand that leads to many more insights than just staring at it and thinking quietly.

With all that said, you may have a solution forming in your head. But before we get there…

Level 0: Getting the Next Hop

One of the surprises I had when I started using this problem is how often candidates get stuck on computing the keys to which we can hop from a given position, also known as the neighbors. My advice is: when in doubt, write an empty placeholder and ask the interviewer if you can implement it later. This problem’s complexity does not lie in the neighbor computation; I’m paying attention to how well you count full numbers. Any time spent on neighbor computation is effectively wasted.

I would accept “let’s assume there’s a function that gives me the neighbors” along with the following stub. Of course, I’ll probably ask you to double back and implement this later, but only if we have time. You can simply write a stub like this and move on:

def neighbors(position):
    ...

Also, you don’t really lose much by asking to use a stub: if the question’s complexity is elsewhere I’ll allow it. If not, I’ll ask you to actually implement it. I don’t mind when candidates don’t realize where the complexity of a question lies, especially in the early stages when they might not have fully explored the problem.

As for the neighbors function here, given that it never changes you can simply create a map and return the appropriate value:

Edit note: I made an error in the original version of this code. It used to be 4: (3, 9, 0) I’ve corrected it since. Sorry about that.

Level 1: Recursively Generating Numbers

Anyway, on to the solution. Perhaps you’ve already noticed this problem can be solved by enumerating all possible numbers and counting them. You can use recursion to generate these values:

This works, and it’s a common starting point I saw in interviews. Notice, however, that we generate the numbers and never actually use them. This problem asks for the count of numbers, not the numbers themselves. Once we count a number we never revisit it. As a general rule of thumb, I recommend paying attention to when your solution computes something it doesn’t use. Often you can cut it out and get a better solution. Let’s do that now.

Level 2: Counting Without Counting

How can we count phone numbers without generating them? It can be done, but not without an additional insight. Notice how the count of numbers that can be generated from a given starting position in N hops is equal to the sum of the counts of hops that can be generated starting from each of its neighbors in N-1 hops. Stated mathematically as a recurrence relation, it looks like this:

This is intuitively obvious when you consider what happens with one hop: 6 has 3 neighbors (1, 7, and 0) and in zero hops you can reach one number for each, so you can only dial three numbers.

How does one arrive at this insight, you might ask? If you’ve studied recursion, this should become evident after some exploration on the whiteboard. Many candidates who’ve practiced recursion immediately notice this problem breaks down into smaller subproblems, which is a dead giveaway. If you’re in an interview with me and you can’t seem to arrive at this insight, I will usually give hints to help get you there, up to and including outright giving it away if prodding fails.

Once you have this insight in hand, you can already move forward and solve this problem again. There are a number of implementations that use this fact, but let’s start with the one I see most often in interviews: the naive recursive approach:

That’s it! Combine this with a function to compute the neighbors and you’ve produced a working solution! At this point, you should pat yourself on the back. If you scroll down you’ll notice we’ve still got a lot of ground to cover, but this point is a milestone. Producing any working solution already sets you apart from a surprising number of candidates.

This next question is one you’re going to be hearing a lot from me: what is the Big-O complexity of this solution? For those who don’t know, Big-O complexity is (informally) a sort of shorthand for the rate at which the amount of computation required by a solution grows as a function of the size of the input. For this problem, the size of the input is the number of hops. If you’re interested in the proper mathematical definition, you can read more here.

For this implementation, every call to count_sequences() recursively calls count_sequences() at least twice, because each key has at least two neighbors. Since we recurse a number of times equal to the desired number of hops, and the number of calls to count_sequences() at least doubles with each call, we’re left with a runtime complexity of at least exponential time.

This is bad. Asking for an additional hop will double, if not triple, the runtime. For small numbers like 1 through maybe 20 this is acceptable, but as we ask for larger and larger numbers of hops, we hit a wall. For instance, 500 hops would require until well after the heat death of the universe to complete.

Level 3: Memoization

Can we do better? Using only the mathematical relation above and nothing else, not really. One of the reasons I love this problem, though, is it features layers of insight that yield more and more efficient solutions. To find the next one, let’s map out the function calls this function makes. Let’s consider the case of count_sequences(6, 4). Note I use C as the function name for brevity:

You may notice something peculiar: the C(6, 2) call is performed three times, and each time it performs the same computation, and returns the same value. The crucial insight here is that these function calls repeat, each time returning the same value. After you compute their result once there’s no need to recompute them.

If you’re wondering how you’re supposed to arrive at this, the easiest way is through good old-fashioned whiteboarding: staring at this problem statement in the abstract is nice, but I always encourage candidates to throw a sample solution up on the board. Solving out a problem like this and drawing the tree like I did above will see you writing the subtree for C(6, 2) multiple times, which you’re sure to notice. This is sometimes enough of an insight to allow candidates to bypass solutions 1 and 2 altogether and jump straight to this stage. Needless to say, that’s a huge time save in an interview where you only have 45 minutes to solve a problem.

Armed with this insight, how do we solve this problem? We can use memoization (not memorization), which basically means we record results of function calls we’ve seen before and use those instead of redoing the work. This way, when we encounter a place in the call graph where we would unnecessarily recompute an entire subtree, we instead immediately return the result we already computed. Here’s an implementation:

Alright, what’s the runtime complexity (Big-O) now? That’s tougher to answer. For the previous implementation, computing the runtime was as simple as counting the number of times the recursive function was called, which was always two or three times per call. This time counting is more complicated because the recursive call is guarded by a conditional. On the face of it there’s no obvious way to count function calls.

We can solve this mystery by instead looking at the cache. Each function call’s result is stored in the cache, and it’s inserted there exactly once. This allows us to reframe the question as “how does the size of the cache grow with the size of the input?” Given that the cache is keyed by position and number of hops, and there are exactly ten positions, we can conclude that the cache grows in direct proportion to the number of requested hops. This follows from the pigeonhole principle: once we have an entry in the cache for every combination of position and jump count, all calls will hit the cache rather than result in a new function call.

Linear time! That’s not bad. In fact, it’s remarkable: the addition of a simple cache changed the algorithm’s runtime from exponential to linear. On my venerable old MacBook Air, the recursive implementation takes about 45 seconds to run for twenty hops. This implementation can handle 500 hops in around 50 milliseconds. Not bad at all.

So we’re done right? Well, not quite. This solution has two drawback, one major(ish) and one minor. The major-ish drawback is that it’s recursive. Most languages place limits on the maximal size of their call stacks, which means there’s always a maximal number of hops an implementation can support. On my machine it fails after about 1000 hops. This is a major-ish limitation rather than a major one because any recursive function can be re-implemented in an iterative way, but still, it’s a hassle. As for the minor limitation, that actually leads us into the next solution…

Level 4: Dynamic Programming

The minor limitation of the recursive memoizing solution is clear when you look at the recurrence relation from above:

Notice that the results for N hops depend only on the results for calls with N-1 hops. Meanwhile, the cache contains entries for every (nonzero) number of hops. I call this a minor issue because it doesn’t actually cause any real problems, given that the cache grows only linearly with the number of hops. Requiring linear space isn’t the end of the world, but still, it’s inefficient.

What gives? Again, the result is clear when you look at a written-out solution and the code. Notice that the code starts with the largest number of hops and recurses directly down to the smallest:

If you imagine the entire function call graph as a sort of virtual tree, you’ll quickly see we’re performing a depth-first traversal. This is fine, it gives a proper solution, but it doesn’t take advantage of the shallow dependency property I pointed out above.

Can you perform a breadth-first traversal instead, where you start at the top and “visit” function calls for N-1 hops only after you’ve visited those for N hops? Sadly, no. The values of function calls with nonzero hops absolutely require the values from smaller hop counts, so you won’t get any results until you reach the zero-hop layer and start returning numbers rather than additional function calls (note the zero-hop layer isn’t depicted here).

You can however, reverse the order: visit layers with N hops only after you’ve visited layers with N-1 hops. Those of you who studied or are studying discrete mathematics will recognize all the necessary ingredients for an induction: we know that the values of zero-hop function calls are always one (the base case). We also know how to combine N-1 hop values to get N hop values, using the recurrence relation (the inductive step). We can start with a base case of zero hops and induce all values greater than zero. Here’s an implementation:

So what’s better about this version than the recursive, depth-first solution? Not a ton, but it has a few benefits. First off, it’s not recursive, meaning it can run for extremely large values without crashing. Second off, it uses constant memory, because it only ever needs two arrays of fixed size rather than the ever-growing cache of the memoization solution. Finally, it’s still linear time: I can compute 200,000 hops in just under twenty seconds.

Assessment

So we’re done, right? Pretty much. Designing and implementing a linear time, constant space solution in a job interview is a very good result. When I was using this question, I gave candidates who provided the dynamic programming solution an excellent rating.

What about the other solutions, you might ask? Unfortunately it’s impossible to rate an abstract candidate. Interviews are chaotic things; they can start late, people can be nervous, and they often arrive at insights and solutions late in the session, leaving them with little time to code anything. There’s also a conversation happening: I pay attention to how well the candidate communicates their thoughts and incorporates ideas and feedback. I always take these factors into account before making a hire/no-hire recommendation, and you just can’t do that in the abstract.

Instead of potential recommendations, I’ll focus on the things I’d like to be able to say. When assessing algorithms and data structures, I want to say something like “TC (The Candidate) explored the problem and produced a solution that addressed all edge cases, and improved the solution when presented with its shortcomings. In the end, they arrived at an optimal solution.” I also want to be able to say “TC chose appropriate data structures for the solution, and correctly answered questions about the Big-O of their solution’s runtime and space requirements.”

When assessing coding, my ideal statement would be “TC quickly and concisely translated their ideas into code. The code uses standard language constructs and is easy to read. All edge cases are addressed, and TC walked through their code to debug it and verify it’s correct.” For entry-level roles I give bonus points if there’s some sort of testing, but more experienced roles I penalize candidates who don’t at least list relevant test cases.

As for speed of progress, I’d love to be able to say “TC drove the problem solving process: they developed most of their own solution, and were able to identify and address shortcomings without my pointing them out. TC required only minimal hints to get them moving in the right direction.”

Anyone I can say these things about gets a “Strong Hire” in my book. However, “Hire” and “Leaning Hire” are also positive endorsements. If you come up short in one area but shine in another then I can probably still justify a positive recommendation.

Wrapping Up

This problem might seem daunting, especially given that this post has become as long as it has. Keep in mind, however, that this post is purposefully much more thorough than any interview will ever be. I’m not laying out everything I expect to see, I’m dissecting a problem into its finest details to leave nothing out.

To that end, here is a list of skills this question covers and habits you ought to develop:

• Always start by solving a small instance of the problem by hand. In this problem the recurrence relation and the repetition of function calls become much more obvious when you hand-solve a problem.
• Pay attention to when your solution is computing things you don’t need, like how the naive counting solution generates the sequences but doesn’t actually use them. Reducing unnecessary computation can often provide simpler solutions, if not open the door to more efficient ones.
• Know your recursion. It’s almost useless in most production code because it blasts through the stack, but it’s a very powerful algorithm design tactic. Recursive solutions can often be adapted and improved: the difference between the exponential time naive solution and the linear time nearly-optimal memoization solution is minimal.
• Know your Big-O analysis! You’re practically guaranteed to be asked this at some point during the interview process.
• Always be on the lookout for opportunities to memoize. If your function is deterministic and you’ll be calling it multiple times with the same inputs, your solution may benefit from memoization.
• Find and write out the recurrence relation. In this case writing it out makes it obvious that counts for N hops depend only on counts for N-1 hops.

If you liked this post, applaud or leave a response! Nothing makes me feel warm and fuzzy inside like hearing from readers. Also, if this is the sort of stuff you like to read, and if you’re all the way down here there’s a good chance it is, give me a follow! There’s a lot more where this came from.

But Wait, There’s More!

Okay, so I said we were done, but it turns out this problem has one more solution. In all my time interviewing with this problem I’ve never seen anyone provide it. I didn’t even know it existed until one of my colleagues came back to his desk with a shocked look on his face and announced he had just interviewed the best candidate he’d ever seen.

I’ll post a detailed follow-up soon, but in the meantime I’ll leave you all to wonder how this problem can be solved in logarithmic time…

If you’d like to ask me questions or just learn more about interviewing, check out our discord!

Update: Now that we’re up and running, here is a listing of all the posts in this series:

• Introduction
• Knight’s Dialer
• Synonymous Queries
• Ratio Finder

Google Interview Questions Deconstructed: The Knight’s Dialer was originally published in HackerNoon.com on Medium, where people are continuing the conversation by highlighting and responding to this story.

Before I continue, a disclaimer: while interviewing candidates is one of my professional responsibilities, this blog represents my personal observations, my personal anecdotes, and my personal opinions. Please don’t mistake this for any sort of official statement by or about Google, Alphabet, or any other person or organization.

First, bit about me: I graduated in 2012 with a B.S. in Mathematics from Fordham and a B.S. in Computer Science Engineering from Columbia through a dual-degree program. I’ve been working at Google NYC ever since, first on the bidding automation group, and more recently on the AdWords recommendations group. It’s given me the opportunity to do a lot of fun and challenging things: write petabyte-scale data analyses, fight late-night production fires, lead multi-person projects from the ground up, implement algorithmic optimizations to core business logic. The list goes on and on, and I’ve enjoyed every minute of it.

I also volunteer an hour or two of each week for interviewing candidates for engineering positions, leading them through the classic whiteboard coding format where the candidate has 45 minutes to design and implement a solution to a technical problem. Every once in a while, my favorite interview question will leak to the public, meaning I have to dig up a new one. My loss is your gain, though: the moment a question is leaked, I’m free to share a case study on it!

Next, a bit about you. If you’re reading this, you’ve clearly got an interest in computer science and might be interested in interviewing at tech companies. While I want to make this series useful to people of all levels, I’m targeting it in particular at undergraduates and master’s students in CS or a related field. If you don’t fall into that category, don’t leave! I’d like to think there’s something here for you, too.

Interview Format

Before we dive into the questions, though, a quick introduction to how these interviews work. Keep in mind, this is all my personal perspective as an interviewer, so your mileage may vary. As always, Google recruiters are the authoritative sources, so if you have access to one, ask them first!

I interview for full-time software engineer (SWE) roles, as well as SWE internships. If you were applying for a full-time SWE position, you’d typically be given one or two 45 minute screening interviews, conducted over the phone. If you did well, you’d then be invited to travel to one of our campuses (all expenses paid) for a day of on-site interviews. This consists of four to five in-person interviews, again 45 minutes each. Plus lunch, of course.

If you were applying for a SWE internship, there’s usually no on-site interview: you’d typically be given one or two phone screens and that’s that.

After each interview is done, the interviewer writes up feedback. For entry-level technical roles, this feedback is only on your technical abilities: How well did you apply your data structures and algorithms knowledge? How well do you code? Did your solution handle all the edge cases? How close did your solution get to optimal time and space complexity for the problem? How well did you communicate your thoughts and respond to questions?

Behavioral questions are typically reserved for more senior roles like management, as well as non-technical roles like sales and operations. When I interview, I only care about your ability to solve problems and communicate as you do it. In other words, don’t spend too much time worrying about the your outfit or the strength of your handshake.

Another crucial point: you will not have access to a compiler, shell, repl, or IDE. Phone screens are conducted in a shared Google Docs document. On-site interviews give you the option of either writing by hand on a whiteboard or typing on a laptop into a text editor. You’ll have no tools except yourself and your wits.

Now What?

Now that we’ve got all that out of the way, my next post will talk about my first favorite interview question, the Knight’s Dialer…

Update: Now that the series is up and running, here is a listing of all the posts:

• Knight’s Dialer
• Knight’s Dialer Followup
• Synonymous Queries
• Ratio Finder