Tag: interview question solution

Interview Basics: Reverse a Linked List

Interview Basics: Reverse a Linked List

Reversing a linked list is a very common task in technical interviews. That’s why we devote a whole section of Interview Practice to them! Being able to solve this question easily is a great way to demonstrate to an interviewer that you’re a capable, competent programmer. Let’s discuss two different ways of reversing the direction of a linked list: recursively and iteratively.Linked list refresher

A linked list can be modeled by Node objects, where each node stores a value and a next pointer to the next node in the list. The last node in the list points to NULL, to indicate that you’ve reached the end of the list. You access the linked list by having access to a head pointer at the beginning of the list.

Basic Linked List
A basic linked list

You need to apply a function reverse(head) that does two things:

  1. Reverses the direction of the arrows, changing the structure of the linked list, and
  2. Returns a pointer to the new beginning of the list.

So all the nodes will stay in place in memory, and only the direction of the pointers will change.

Linked List Reversed
What we want to get

You probably wouldn’t implement a linked list this way in an actual program. There might be a lot of different references to the linked list before you reverse it.

Linked List Multiple References
A linked list with multiple references

If you call reverse(head1), you would update head1. But all the other pointers would then be stuck at the end of the linked list, and only head1 would be a good head pointer.

Linked List Reversing With Multiple References
Only head1 was reversed

To get around this, you could make a LinkedList class, or a sentinel head that external references could point to that contains the pointer to the beginning of the linked list. Then you could safely update this reference without breaking any external references.

Linked List with Sentinel Head
A linked list with a sentinel head

But so that we can focus on just the core algorithm, the solutions in this video use a simple version of the linked list.

Why is reversing a linked list tricky?

Linked lists are designed to be easy to traverse in the forward direction, and once a node passes a particular point there is no way of going back to it. If you were in a position where reversing order was something you needed to do often, then a linked list would be a poor choice of data structure and you’d be better off choosing something else.

So this isn’t a problem that you’d really ever encounter on the job. In technical interviews, though, this kind of question is asked as a way of assessing how well you can perform tricky manipulations. That’s why sometimes the problems that interviewers ask can feel kind of artificial.

In this video, I demonstrate two different approaches to reversing a linked list: a recursive one, and an iterative one.

The code

CodeFights Solves It: houseRobber

CodeFights Solves It: houseRobber

This week’s Interview Practice Task of the Week is houseRobber, a technical interview question that’s been asked at LinkedIn. In this challenge, we’re asked to assist a robber in stealing from houses. Not something that we recommend you do in real life, of course! We will be looking at an (inefficient) recursive solution and then seeing how we can speed it up using memoization (not a typo!) or dynamic programming.

In this task, we are given an array loot, where loot[i] represents the total value of goods we can take from house i. Each house is connected to its neighbors, so the robber isn’t willing to rob two neighboring houses. This means if we take the loot from house i, houses i-1 and i+1 are off limits! Our task is to write a function houseRobber(loot) that returns the maximum amount of loot the robber can steal given loot.

For example, if loot = [5,10,12,2] then the maximum amount of loot that the robber can take is 17 (stealing 5 from house 0 and 12 from house 2). If we had the same values in a different order such as loot = [5,10,2,12], then the maximum amount the robber can take jumps up to 24 (stealing 10 from house 1 and 12 from house 2).

These examples are a little misleading, however. They suggest that we look at stealing from the even numbered houses, and compare that to what we would get stealing from the odd numbered houses. While stealing from evens or odds will ensure we visit the maximum number of houses, it doesn’t guarantee maximum value. For example:

LinkedIn technical interview question solution
Can’t just look at the even and odd houses!

In the problem we are guaranteed that each house has a non-negative amount of money.

Recursive solution

Let’s start by looking at a few cases. First, we’ll look at a few trivial cases:

  1. If there are no houses (i.e. loot = []) then the robber is out of luck and gets nothing. We return 0.
  2. If there is only one house, then the solution is obvious: take whatever is inside, so we return loot[0].
  3. If there are two houses, then the robber should steal from the house that has the most money, so we should return max(loot[0], loot[1]).

These are called our base cases.

Here comes the magic part: what if we have N houses, where N > 2? Let’s start at the first house: we have to decide whether the robber should rob this house or not. Our two choices are:

  1. Steal from the first house. Then we cannot steal from the second house. The best we will be able to get is the value from this house (loot[0]) plus whatever we can get from house 3 onward (because the second house is off-limits). So our payoff is loot[0] + houseRobber(loot[2:]).
  2. Don’t steal from the first house. Then this problem is identical to ignoring the first house altogether, and evaluating houseRobber(loot[1:]) (ignoring the first house, and solving the same problem from second house).

We should evaluate both choices, and return the larger of the two. Notice that regardless of which step we make, the problem gets smaller on each step. Eventually we’ll end up with 0, 1, or 2 houses in our list, and the base cases will actually evaluate our solution.

Here’s the recursive solution in code:

Running this code passes the first 24 tests, but then times out on test 25.

The problem is for all cases except the base cases, houseRobber calls itself 2 more times. This tells us that we can expect houseRobber to be O(2^N), where N is the number of houses. To see the calls, and to find a possible remedy, let’s walk through what our code is doing for the input loot = [4, 1, 2, 7, 5, 3, 1]. Each node here represents a call to houseRobber with the input in the box. The boxes have been color-coded, so each different input is represented with a different color.

LinkedIn technical interview question solution

One of the things that should jump out at you is that we are evaluating the same function many times. For example, houseRobber([5,3,1]) shown in red is called 5 times! Each time it returns the same value 6 (as robbing the first and the last house gets the most loot from houses with values [5, 3, 1]).

Improving with memoization

To reduce the amount of redundant work we have to do, one technique is to memorize the answer of each calculation as we do it. This is called memoization, as in “to write down the answer on a memo so we can get it later”. (Actually, memoization comes from the Latin “to be remembered”, but that makes it sound like we should be using the term “memorization” instead!) Basically, the first time we encounter a particular input we will store it in a hash table.

We will not call a helper function for two reasons: not to pollute the global namespace with our previously memoized answers, and because we need to convert loot to a tuple (we cannot use lists as keys to a hash table).

When we run this version, it passes all the tests. We can show the tree of calls to _houseRobberRecursive for this new variation. Note there are many fewer calls, as we are able to reuse anything we have already calculated. (It is important to note the left branch of each note is executed first, because of the order we evaluated valueSteal and valueLeave in _houseRobberRecursive).

LinkedIn technical interview question solution
Calls to “_houseRobberRecursive” when using memoization

Dynamic programming solution

We already have a solution, but it’s a little messy. We created a helper function to keep our hash table memo_ans outside of the global namespace, because it would be bad if someone else had also written a function that used memo_ans to store their results.

Notice that memoization started with the full list [4, 1,2, 7, 5, 3, 1] and broke it down to smaller and smaller cases. This is called a top-down approach. Our next approach will be a bottom-up approach, where we start from the small cases and work up to the final solution.

We will introduce an array steal[i], where steal[i] is the best we can do if we are only allowed to steal from the last i+1 houses. If loot = [4, 1, 2, 7, 3, 1] then

  • steal[0] = 1 (if we can only steal from the last house, then the best we can do is taking the last house’s loot)
  • steal[1] = 3 (we can either steal 3 or 1; 3 is clearly better)
  • steal[2] = 8 (given [7,3,1] stealing 7 and 1 is clearly more than just stealing 3).
  • steal[3] = 8 (best we can do from [2,7,3,1])
  • etc.

The answer we actually want is the last element of the steal array.

Remember our magic step for this problem? It was when deciding whether to steal from house i, all we had to do was compare loot[i] + (most you could steal from house i+2 on) and (most your could steal from house i+1 on). But note that steal[i] tells us the best we can do from the last i houses. This suggests we can find steal[i] using the following technique:

This won’t give us steal[0] or steal[1], but these are our base cases. Note how much simpler our code becomes:

This is much tidier, but we can reduce this code even more. Notice that steal[i] depends only on the current value of the loot and the last two values of steal. This means we don’t need to keep an array steal. Instead, we just need to keep track of the last two entries.

Warning: At the moment, we are still going to accomplish our goal of finding the maximum value that our robber could take. If you wanted to be able to produce a list of houses for the robber to pilfer to achieve the maximum, the steal array is incredibly useful. There is a “backtracking” algorithm to reconstruct which houses the robber should steal from. The optimized version below reduces the space complexity of our solution from O(N) to O(1), but at the cost of being able to efficiently reconstruct the list of houses that have been hit.

Our new code is:

So far we have implemented the bottom-up technique literally. We have made our way from the “end of the street” and worked backward. However, all that matters in this problem are which houses are next to each other. There isn’t a reason to reverse the houses. We could consider steal[i] as being the most we could steal from the first i houses (instead of the last i houses). The only reason we did it that way is it’s a little easier to conceptualize “running out of houses” at the end of the list.

We can make our problem look a little more like a standard problem with the following observation: if we initialize oldBest and newBest to zero, and go through every house, then the first pass through the loop sets oldBest and newBest to the correct value. This simplifies our base cases and makes the problem more familiar:

Similar problems

This problem is a recursively defined series in disguise. This is a series where you calculate the next value using the previous values. One of the most famous examples is the Fibonacci numbers:

where the first two numbers are 0 and 1. After the first two numbers, we get the next number by summing the previous two numbers in the sequence. For example, the seventh number in the sequence is 8 because 5 + 3 = 8. The mathematical expression for the Fibonacci numbers F[n] is given by

and where F[0] = 0 and F[1] = 1. This definition leads to a recursive function call:

Because we see each call to fib(n) (except the base cases n=0 and n=1) call fib two more times, we are not surprised to find an O(2^n) running time. We can memoize this function (and this is good practice!), but we can also write an iterative or dynamic programming solution:

Note how similar the program is to houseRobber. Many problems that involve making a choice to explore two different paths, such as rob house i or not, will given rise to these recursive sequences. This is a good pattern to know!

The overall approach:

  1. Usually we are iterating through our problem, and have to decide whether or not to include the current element. In this case our decision was whether or not to rob a house, but in other instances it might be whether or not to pack a certain item, or whether we use a road to get to our destination.
  2. Start by relating this problem to “smaller” instances of the problem. If it helps, write a recursive solution first (although usually these will have bad run times). Usually these smaller instances are related to the different possible choices you could have made. In this case, the smaller instances were “making the best value from the remaining houses”.
  3. Look at how many of the “smaller” instances you have to use to solve the next instance. In this case, we only used the last two instances. This can help you write the solution as an iterative solution.

Tell us…

Have you ever gotten a question like this in a technical interview? What strategy did you take to solve it? Let us know on the CodeFights forum!

CodeFights Solves It: chessQueen

CodeFights Solves It: chessQueen

Our latest Interview Practice Task of the Week was chessQueen, which has been asked in technical interviews at Adobe. This question might seem fairly easy at first: Given the location of a queen piece on a standard 8 × 8 chess board, which spaces would be safe from being attacked by the queen? But as with any “easy” technical interview question, it’s imperative that you think it through fully, watch out for potential traps, and be able to explain your reasoning as you solve it!

This question is a variation on a classic problem, Eight Queens. It’s very possible that you’ve encountered Eight Queens or a common variation, nQueens, in computer science classes or interviews in the past. Chess-based problems like this one come up a lot in interviews, there’s a good reason for that! If you think about a chess board, what does it look like? A grid. And chess pieces follow specific rules, making chess scenarios a great framework for questions that test your basic problem-solving and implementation skills.

If you haven’t solved chessQueen yet, now’s the time! Once you’ve written your own solution, head back here. I’ll discuss my solution, and why I chose it over other possible solutions to the problem.

Ready? Great, let’s get started!

The technical interview problem

chessQueen gives us the location of the queen in standard chess notation (e.g. “d4”). Our solution needs to return a list of all the locations on the board that are safe from the queen. The diagram below shows the locations that the queen could move to on her next move, which means that these cells are not safe from the queen.

position of the queen in Adobe technical interview question
Queen at D4

In this example, we’d need to have our function chessQueen("d4") return the following list:

Keep in mind that the output above has been formatted nicely to help us visualize the solution when looking at the diagram. The native output would put line breaks at locations dictated by the size the window.

What can the queen attack?

Remember that in chess, a queen can move any number of squares vertically, horizontally, or diagonally.

The rows are already numbered, so let’s number the columns as well. Internally, we can think of column A as ‘0’, column B as ‘1’, etc. We will call the queen’s location (qx,qy). Then the queen can take any location (x,y) that is:

  1. Anything in the same row (i.e. qy == y)
  2. Anything in the same column (i.e. qx == x)
  3. Anything on the up-and-right diagonal from the queen’s location. (i.e. slope 1 lines though the queen’s location: qx - qy == x - y)
  4. Anything on the down-and right diagonal from the queen’s location. (i.e. slope -1 lines though the queen’s location: qx + qy == x + y)

Any other location on the board is safe from the queen.

Our strategy

We see that we have to report and return all the squares that are safe from the queen for our solution. If we think of the chess board as N × N, we see that there are N squares excluded from the row, N excluded from the column, and at most N excluded from each of the diagonals. We are expected to return O(N^2) elements, so we know that we aren’t going to find a solution shorter than O(N^2).

The creative parts of this solution will be how you choose to map between the column letters and the numbers – basically, how you do the arithmetic! My choice below was to use the hard-coded string "abcdefgh", where the position in the string maps to the index. I’ll mention some alternatives below, as well as their advantages and disadvantages.

Other approaches to this coding challenge

My approach to translating between the column’s names and the numbers won’t be everyone’s favorite way. My approach to listing the elements isn’t elegant, but it gets the job done! And a lot of times, that’s exactly that an interviewer needs to see.

Here are some alternatives, and why I didn’t choose them:

  • Using the built-in string library
    We can get rid of the hardcoded string by writing

You have to be a little careful that people running different locales will still have the same “first 8 characters” that you have! Note that you can use cols = list(string.ascii_lowercase[:8]) instead to be safe, but at that point I’d rather be explicit about the letters I’m using.

  • Using “ASCII math”
    We can find the column numbers by subtracting the character code a from the letter. In Python, ord('a') will return the code for the letter ‘a’ (97 in ASCII). In C, the function casting the character to an integer does the same thing. So we can actually write code that is a lot smaller:

Because we aren’t relying on the position in the list, and have a direct translation between the column letters and numbers, we’re able to remove the column directly, instead of having to use the continue keyword. I avoided this because I get nervous doing encoding math (what about the locales?!) but the Python documentation assures me I’d actually be fine!

  • Using a dictionary for the conversion
    If I wanted to be fully explicit, I could make a dictionary {'a':0,'b':1, ..., 'h':7} to encode the values, and a separate dictionary to decode. This is a very flexible approach, but I would worry about what my interviewer might read into me setting up two hash tables for something that really only needed a little arithmetic! This is probably the easiest version to internationalize, so if you have a technical interview at a company that works in many different character sets, you could use this flexible code as a selling point. (“Oh, you want the names of the columns in Chinese? No problem, I just have to change the keys in this dictionary…”)

Tell us…

As you’ve seen, this is a challenge that can be solved in a number of different ways! How did you tackle it? How would you describe your reasoning for taking that approach to an interviewer? Let us know over on the CodeFights forum!

CodeFights Solves It: goodStringsCount

CodeFights Solves It: goodStringsCount

Our Interview Practice challenge this week is goodStringsCount, a combinatorics problem. As the name suggests, combinatorics deals with combinations of objects that belong to finite sets, and it’s one of those topics that come up a lot in technical interviews. This specific coding problem is from Apple, which makes sense since they’re known for asking combinatorics questions in their technical interviews!

If this isn’t your first CodeFights Solves It rodeo, I bet you know what I’m going to ask next: Have you solved goodStringsCount yet? If not, hop to it! Once you’ve got your solution, come back and we’ll walk through the problem together.

combinatorics interview question solution
The new MacBook Pro looks really nice!

Done? Great! Let’s get into it.

The technical interview problem

For this programming interview question, our job is to write a function that counts “good strings” of length n. A “good string” is defined as a string that satisfies these three properties:

  1. The strings only contain the (English) lowercase letters a – z.
  2. Each character in the string is unique.
  3. Exactly one letter in the string is lexicographically greater than the one before it.

The first two conditions tell us that any string made up of lowercase letters qualifies. For example, there are no good strings of length 1, because the single letter doesn’t have anything to be greater than! In other words, goodStringsCount(1) should return 0.

Looking at good strings of length 3

Strings of length 2 are actually a little misleading, because they don’t really allow us to dig into the third condition on good strings. It just tells us that the characters have to appear in ascending order, as the second character has to be greater than the first. So let’s start by looking for good strings of length 3 instead!

The third condition tells us that “bfg” is not a good string because all the letters appear in ascending order. But “bgf” is a good string since:

  • looking at the first two characters: ‘b’ < ‘g’ (so there is a letter greater than the one that precedes it)
  • looking at the next two characters: ‘g’ > ‘f’ (so there is only one letter greater than the one that precedes it)

From the letters b, f, and g, there are six possible strings, of which 4 are “good strings”.

“bfg”, “bgf”, “fbg”, “fgb”, “gbf”, “gfb”

There is nothing particularly special about the characters b, f, and g. We could use a, h, and k as well (just replace b with a, h with k, and g with k in the list above). In fact, any three distinct letters would do, since the only property we used was their relative order. So we have:


where is n choose r, the function for counting the number of ways of choosing r elements from n. This is a common function in combinatorics problems, so I’ve included a discussion of it as a footnote to this article! We’ll be using this function a lot, so if you haven’t come across it before skip to the end and read about it now.

Overall strategy for this problem

After looking at a specific case, we get an idea of the structure of this problem. For finding the good strings of length n:

  • We need to find the number of ways of picking n letters, which is 26 choose n.
  • Given the numbers 1, 2, …, n, we need to find the number of ways we can arrange them in a “good sequence”. A “good sequence” is when exactly one number is greater than the one before it. We will call the number of good sequences of 1, 2, …, n good(n).

The idea is that for each set of n letters, we can put them in alphabetical order, and label the letters from 1 to n by their order in this array. Any good string then gives a “good sequence” of 1 to $n$, and any “good sequence” corresponds to a unique string (from these letters). For example, using n=3 and the letters b,f, g:
* The good sequence [2,3,1] corresponds to the good string “fgb”
* The good string “gbf” corresponds to the good sequence [3,1,2]

The number of good strings of length n is then .

Finding good(n)

Let’s call our sequence [ a[1], a[2] , ..., a[n] ], where each a[i] is distinct and takes a value from 1 to n, inclusive. If this is a “good sequence”, then there is exactly one element a[j-1] that is greater than the element before it, a[j]. Note that this means that:

  • a[1] > a[2] > a[3] > … > a[j], i.e. the elements before a[j+1] make a decreasing sequence
  • a[j+1] > a[j+2] > a[j+3] > … > a[n], i.e. the elements from a[j+1] onward make a decreasing sequence

For example, a good sequence [4,2,5,3,1] can be broken into the two decreasing sequences [4,2] followed by [5,3,1]. In the notation above the value of j in [4,2,5,3,1] is 2 because a[2+1] = 5 is the only element bigger than the previous element.

Given the list of n numbers, there are n-1 choices for a[j]. (You can’t use the very last element, because there is no a[j+1].) Another way of seeing this is that we are splitting the array into two decreasing subarrays, and the only places that we can split on are the locations of the commas!

For now, let’s pick a particular value of j and ask how many good sequences of 1 through n we can make with this value of j. Given a set of distinct numbers, there is only one way of making them into a decreasing sequence, so really we just need to pick which j numbers go in the first decreasing sub-array, and which n-j numbers go in the second decreasing array. Note that once we pick the j numbers for the first array, the remaining numbers automatically go into the second array, so the number of distinct ways of splitting these numbers up is really just . (We have counted one problematic sequence in here, which we’ll come back to.)

In case you got lost in the n and js, here’s an example to help you out. Let’s pick n = 5 and j=2. Instead of counting all the good sequences, we are just counting the ones where the split happens at position 3. So we have:

[a[1], a[2]] make a decreasing sequence, and [a[3],a[4],a[5]] make a decreasing sequence.

How many sequences like this are there? I need to split 1,2,3,4,5 up into two pieces: two elements (i.e. j) become a[1] and a[2], while the remaining three elements (n-j) become a[3] through a[5]. But once I pick a[1] and a[2], whatever is left over has to go into the other array. There are ways of picking a[1] and a[2]:
* a[1] and a[2] are 1,2: the sequences are [2,1] [5,4,3] -> [2,1,5,4,3]
* a[1] and a[2] are 1,3: the sequences are [3,1] [5,4,2] -> [3,1,5,4,2]
* a[1] and a[2] are 1,4: the sequences are [4,1] [5,3,2] -> [4,1,5,3,2]
* …
* a[1] and a[2] are 3,5: the sequences are [5,3] [4,2,1] -> [5,3,4,2,1]
* a[1] and a[2] are 4,5: the sequences are [5,4] [3,2,1] -> [5,4,3,2,1] (UH OH!)

The last one is problematic, because all the numbers are decreasing! So while there are 10 ways of making the split into two decreasing sequences with n=5 and j=2, there are only 9 good sequences (with n=5 and j=2) because these is one sequence where all the numbers are decreasing.

The example shows us the problem with the way we have counted by splitting into two decreasing arrays: We never made sure that a[j+1] was bigger than a[j]. Fortunately there is only one arrangement that doesn’t work: the arrangement [n,n-1,...,1], so we have over-counted by exactly one. The number of good sequences split of 1 through n, split into arrays of length j and n-j is therefore .

To determine good(n), we just need to add up all the different good sequences we can get by putting the cutoff between the two arrays at different locations j. We get:

This gets us to a point where we can write a program that will run quickly enough, so if you’re totally “mathed out” you can stop here! We can do a little bit better, through. Here are a couple of clever tricks:

  • , because there is 1 way of not choosing anything from n objects regardless of n – just don’t pick any of them! – and 1 way of choosing all n objects from n objects. So putting j=0 and j=n into gives zero. Now we can rewrite:
  • You might remember from Pascal’s triangle that

    One way of seeing this result is: The sum is asking us about the number of ways we can select a subset of n elements by figuring out the number of subsets with 0 elements, the number of subsets with 1 element, et cetera. Since each element is either in a subset or not, there are 2^n different subsets.

After all this work, we get:

Putting it all together

From our overall strategy, we had ways of picking the n characters, and for each of our choices we had good(n) ways of arranging those characters into good strings. So the number of good strings of length n is:

…and now, some code!

The hard part about this problem isn’t writing the code, but figuring out how to count efficiently. The code is pretty small in this case:

Footnote: Ways of choosing r objects from n objects

How do we get the formula for in the first place? Suppose we have n=6 objects: a flag, a cookie, a laptop, a pen, a cup of coffee, and an orange. Note that we have picked easy-to-distinguish items! We want to select r = 4 of them. How many different sets of items could we come up with?

We have n choices for which item we pick first. We have n-1 choices for the second item, and so on. So it seems like the result is n(n-1)(n-2)(n-3). This becomes a little inconvenient to write for a general r (in this case, we know that r = 4), but notice that:

This formula over-counts the number of different sets of items we could have because selecting the laptop, then the coffee, then the orange, and then the pen would give you the same set of items as selecting the coffee, followed by the orange, the pen, and the laptop. In the formula above, we have counted these two arrangements separately! (This is called a permutation of selecting 4 items from n, and is another useful formula to have under your belt).

How many different orders are there for selecting these 4 items? This is the number of times we have over-counted each set of items we could end up with. We’ll have 4 choices for whichever one we could have picked first (laptop, coffee, orange, or pen) without affecting the items we end up with. With the first item selected, we have 3 items to choose from for the second item, 2 choices for the third item, and then the last item is the 1 thing left over. So we can rearrange these 4 items in ways. The number of combinations for picking r=4 things from n items is:

You can (and should!) run through this argument for a general value of r, and convince yourself that the number of ways of choosing r items from n is:

Tell us…

How did you solve this combinatorics interview question? Did you solution differ from mine? Let us know over on the CodeFights forum!

CodeFights Solves It: findSubstrings

CodeFights Solves It: findSubstrings

The Interview Practice Task of the Week was findSubstrings. This is an Uber interview question, and their technical interviews are notoriously lengthy and difficult. And the solution implements tries, a data structure that you’ll see a lot in interview questions. It’s a double whammy!

You know the drill by now: If you haven’t solved this challenge yet, hop on over to CodeFights and do it! Then come back here and we’ll walk through solving it together. We’ll start with a naive implementation and then work on optimizing it.

…Done? Okay!

Technical interview question

The goal of this Uber interview question is to find the longest substring that appears in a given list parts in a set of words. You’ll return the list of words, with the substrings enclosed in square brackets. If there is a tie for the longest substring, you’ll mark the one that appears earliest in the input string.

On a word-by-word basis, if our list is parts = ["An","a","men", "ing", "ie","mel","me"] then we would indicate substrings in the following way:

  • “word” becomes “word” (there is no substring of “word” in parts)
  • “anticipating” becomes “anticipat[ing]” (the substrings “a” and “ing” both appear, but “ing” is longer)
  • “interest” becomes “interest”
  • “metro” becomes “[me]tro”
  • “melrose” becomes “[mel]rose”
  • “melting” becomes “[mel]ting” (“mel” and “ing” are the same length, but “mel” appears first in the word)
  • “ingoltsmelt” becomes “[ing]oltsmelt”

Our function, findSubstrings, should take a list of strings words and another list of strings parts, and return the list of words with the longest substring indicated. For example, with words = ["word", "anticipating", "ingolt", "melting"], and parts defined as before we would get:

Naive solution

Let’s try approaching this problem directly. This would mean going through our list of words, one at a time, and then checking each substring in parts to see if it appears in our word. We will keep track of the longest part that occurs earliest in the string.

We can try running this function on our example, and it works. So we have a running implementation.

But is it good enough to pass the CodeFights time tests, or will it take too long to execute? We submit it and… it passes!

(I’m going to add an important caveat here and say that it passes at the time when I wrote this. Our engineers add new tests to challenges fairly frequently, based on user feedback and challenge results, so there’s a chance that when you read this my naive solution might not pass anymore. But the explanation below of its run time is still really useful, so don’t just skip to the optimized solution!)

What’s the run time?

We should take a moment to think about the running time of this code. If we call W the number of words, and P the number of parts, then we can tell that the running time is at least O(WP) from our nested loop. With a high-level language like Python, we also want to look for hidden loops in function calls. Inside the p loop, we call if p in w and w.index(p) multiple times. These functions are scanning the word w to look for p, and will have a running time of O(len(W)). We could speed up the function a little bit by calling w.index(p) once and saving the result, but we still have a running time that looks like O(WPN), where N is the length of a typical word in w.

So how bad is O(WPN)? From the constraints page:
* We have at most 5000 words, so in the worst-case scenario W = 5000;
* Each word is at most 30 characters, so the worst case is N = 30;
* We have at most 5000 substrings in parts, so the worst-case is P = 5000.

Putting this together, this gives us 750 million loops. This means each loop would have to run in about 5 picoseconds to be done in 4 seconds! Put another way, we would have to have PetaHz processors for the worst case scenario.

Can we argue that we solved the challenge anyway, and that the CodeFights test showed us that the cases we will be seeing aren’t the worst possible cases? Yes, you can absolutely argue that! When companies are hiring, they want people who can write code quickly to solve today’s problems. A working solution today is better than a perfect solution in a month!

But you should make sure you demonstrate to the interviewer that you know how to think about algorithmic complexity. Microsoft famously had an exponential algorithm for determining which software patches were needed for Windows XP, but it was working fast enough for 10 years(!), and no one realized that the algorithm was exponential.

So you can tell the interviewer that you know this is an algorithm with three multiplicative factors (length of a typical word, number of words, and number of substrings). You should explain that you pass the tests, but that your algorithm won’t handle the worst case in reasonable time. Go on to explain that this isn’t an exponential algorithm, so getting more powerful computers or waiting a little longer isn’t unreasonable.

An interviewer may ask you to write a faster algorithm anyway, so if you really want to impress her you can preemptively mention that you think there are better algorithms that you would use if there was a good business case for spending the extra time on this. Remember that premature optimization is the root of all evil. (Maybe that’s a little over-dramatic… but it’s still bad!)

Giving it our best Trie

Instead of the naive implementation above, we will use a special type of tree data structure called a trie to store the substrings in parts. Like all trees in programming, a trie has a root node. Every other node keeps track of a letter, and getting to this point in the trie completes a substring from parts. Taking our example of parts = ["An","a","men", "ing", "ie","mel","me"] from earlier, we can think about the trie pictorially as:

trie data structure

Note there are 7 red letters in the picture of the trie, which correspond to the 7 words we have in parts. Every leaf is a red letter, but the e below the m is also red to indicate that me is in parts.

To check if a string s is in parts, we start at the root and move to the first level in the trie that matches the first letter of s. If we are trying to match me, for example, we would start by moving from the root to m, and then from m to e. Since we end up on a red node, we know that our word is on the list.

trie data structure

To see if in is a member of parts, we would start at the root and follow the path to i, then to n. Since n is not red, we haven’t completed a string from parts, so we would conclude that in is not a member of parts.

trie data structure

If we want to see whether dog was in parts, we would see there is no path from the root to a d, so we could report right away that dog isn’t in parts. We will be scanning a word character-by-character, and instead of having to search through all of parts, we only have to search through the subset of parts that matches what we have already seen.

You have seen this data structure in action before – in fact, every time you see auto-complete working every time you use a browser or text!

Implementing it in code

Now we have to translate our picture into code. We will make a class TrieNode to store all the information in a node:

To create a trie with the words “cat”, “cam”, and “cha” and “chat”, we could write the following (tedious) code:

or, pictorially, we have

trie data structure uber interview question

Let’s make a function that adds a word to the trie so that we don’t have to do it manually. Our method will be to start at the root, reusing existing nodes along our path (or making new nodes as needed). The code for this is:

Using this function, we can condense the code to create our trie to:

Using the trie

I am going to move most of the hard work – that is, finding the longest substring and enclosing it in square brackets – to a function findSubstringInWord(word, root). The function findSubstrings(words, parts) will be responsible for making the trie and collecting all the words together at the end.

Here is our strategy for findSubstringInWord:

  1. Initialize our lenLongSubstr to 0.
  2. Go through word one character at a time, using that character as a starting point for matching substrings in parts.
  3. For each character, use the trie to find the longest substring from parts starting from this character. If it is longer than the longest one we’ve seen so far, record the current position in the string and the current length.
  4. Use the length of the longestSeenSubstring and its starting position to put the square brackets in the right place.

Note how going through the string in order, and only updating the position when we see a strictly longer string, automatically encodes our tie-breaking condition (yay!). The trickiest part is finding the the longest substring from parts starting at a given location, because we need to know the last terminal node we passed though before failing to find a match on the trie. It would be a lot easier if we just had to keep track of the last node we were on before we failed to match.

The function findSubstrings is simple by comparison! Note that it uses our earlier method of constructing the trie directly from parts.

Running time for the trie

Our algorithm still looped through each word. The constraint that we haven’t used yet is the length of the each element in parts. The worst case scenario is having to check 5 levels at each position at each word. In the worst case, we have:

  • The number of words, W = 5000;
  • The number of letters in a word, N = 30;
  • The number of levels to check in the trie, P = 5.

This is smaller than the naive implementation by a factor of 1000.

The final code!

Our code was spread over a few functions. Collecting it all together, we have:

We did it! High fives for everyone!

uber interview question trie data structure

Tell us…

How did you solve this Uber interview question? Have you ever seen one like it in a coding interview? Let us know on the CodeFights user forum!

CodeFights Solves It: isTreeSymmetric

CodeFights Solves It: isTreeSymmetric

The most recent Interview Practice Challenge of the Week was isTreeSymmetric. This interview question from LinkedIn and Microsoft is checking to see how comfortable you are with the tree data structure. Trees have a wide variety of applications, so your interviewer is going to make sure that you know your stuff!

Have you solved it yet? If not, head over to CodeFights and give it a shot. Once you have a solution, come back here and I’ll walk you through how to answer this interview question. (Need to review first? Check out the CodeFights Explainer article about trees.)

solve this tree challenge
This cat is definitely solving isTreeSymmetric right now. You should too!

The technical interview question

Done? Okay, let’s get started!

Our job is to determine if a (binary) tree is a mirror image of itself. That is, we want to know if the left side mirrors the right side. Here is an example of a symmetric tree:

In contrast, this is not a symmetric tree:

The tree on the bottom is the same on the left and the right. In other words, starting at each 2, you get exactly the same tree. But it’s not a mirror image because the left and right sides — the 3 and 4 — don’t swap positions.

We are going to implement a tree in Python with the following data structure:

Subtrees and recursion

A subtree is what we get by starting at any node, and treating it as the root of its own tree. For example, consider the tree:

The subtree under node 2 is:

While the subtree under node 6 is:

A simpler question: Are left and right sides equal?

Let’s start with a slightly simpler problem. We’ll ask if the left-hand side of the tree is equal to the right-hand side of the tree, and we’ll assume that we have at least three nodes. With these assumptions, this is the same as asking whether the subtree under the first left node is the equal to the subtree under the first right node. Since subtrees are trees in their own right, what we would like is a function areTreesEqual(treeLeft, treeRight).

To figure out how to determine if two trees tree1 and tree2 are equal, we’ll turn to recursion. We have two trees, tree1 and tree2. Suppose that each tree has at the first two levels full (i.e. we have the root and both a left and right branch on level 1). Then tree1 looks like the following:

with a similar structure for tree2. We can think of tree1 as:

tree1 and tree2 are equal if and only if all of the following are true:

  1. A1 and A2 are equal;
  2. The tree {subtree L1} is equal to the {subtree L2} (determined by calling areTreesEqual(tree1.left, tree2.left));
  3. The tree {subtree R1} is equal to the {subtree R2} (determined by calling areTreesEqual(tree1.right, tree2.right)).

Now we need to work out the base case, so that the recursion will terminate. We assumed above that the first two levels would be full. This certainly isn’t true for leaf nodes, and even close to the root we may not have two branches. Here are the cases we need to consider that don’t fall into the recursion above:

  • Both trees are at a leaf (i.e. no children on either side). Just check to see if the values of the nodes are the same; if they are then these two subtrees are equal.
  • Either the left or right side is missing from both nodes. If the sides are the same, just check that side. If the sides are different (e.g. tree1 has no left side, but tree2 has no right side) then the trees are not equal.
  • The left side or right side is missing from only one node. Then the two trees are automatically not equal.

We now have enough information to write our function areTreesEqual:

A function areBranchesEqual, which tests if the two branches of a tree are equal, could then be written to first check if we have a root node, then use areTreesEqual on the two subtrees root.left and root.right.

The original problem: isTreeSymmetric?

The big difference between isTreeSymmetric and areBranchesEqual is implementing the mirroring. When we investigate the left hand path of a node on one side, we have to investigate the right hand side on the other. Our full code is:

The problem with recursion

So far we have a really neat and elegant solution for this interview question. It passes all of the tests on CodeFights, including the hidden ones. A lot of tree problems lend themselves really well to being solved with recursion. However, in a technical interview, the interviewer might point out that the constraints of the problem told us that we were guaranteed the tree would be smaller than 5 * 10^4 values. Could we trigger a maximum recursion depth error in Python? (In other languages, the general term for this is “run out of stack space”).

Our algorithm is a depth-first search check, so if we run into problems it will be on very deep trees. Whenever we move down a level, before calling the recursive step we check if the current left side and right side are equal. So our worst case scenario tree would be:

The depth of this tree is 24999, and the (default) maximum recursion depth in Python is only 1000. Thankfully CodeFights didn’t give us this “torture test” for our algorithm! But how would we deal with it if our interviewer asked us to solve these trees?

The solution is to convert the recursive algorithm into an iterative one.

Phew! Though the recursion version is a lot easier to read, it’s a good idea to practice rewriting recursive algorithms as iterative ones since there are limitations on how many successive recursive calls you can make before returning.

Tell us…

How did you solve this Interview Practice challenge? Have you ever encountered it (or one like it!) in an interview? Let us know over on the forum!

CodeFights Solves It, Interview Practice Edition: groupsOfAnagrams

CodeFights Solves It, Interview Practice Edition: groupsOfAnagrams

This week’s featured Interview Practice challenge was groupsOfAnagrams. It’s a Twitter interview question, and they’re known for their difficult technical interviews! If you haven’t solved it yet, go ahead and do that first, then head back here and we’ll discuss how to get to a solution with a good runtime.

…Done? Okay, let’s dig into this coding challenge!

The technical interview challenge

You are given a list of n words. Two words are grouped together if they are anagrams of each other. For this interview question, our task is to determine how many groups of anagrams there are.

For example, if the list words = [listen, admirer, tea, eta, eat, ate, silent, tinsel, enlist, codefights, married], we should have groupsOfAnagrams(words) return 4 because there are 4 groups:

  • listen, silent, tinsel, enlist are all anagrams of each other.

  • tea, eta, eat, ate are all anagrams of each other.

  • married and admirer are anagrams of each other.

  • codefights is not an anagram of anything in words except itself.

In the challenge, we are guaranteed that each word only consists of lowercase letters. So we don’t need to worry about the rules regarding spaces and punctuation. Each word is guaranteed to be at most 10 letters. The hard part is that we have to do this on lists containing up to 10^5 words!

First attempt: Determining if two words are anagrams

There are a few standard ways to determine whether or not words are anagrams of each other. One way is to go through each letter of the alphabet, and check that it appears the same number of times in each word.

What is the runtime of this algorithm? Suppose a typical word has L characters. In calling word.count(char), we are asking the computer to scan word to count the number of times character char appears. This is an O(L) operation. Technically, this makes areAnagrams an O(L) algorithm because we do this count operation for each letter of the alphabet, which doesn’t depend on the size of the word. However, big O notation suppresses the really bad constants hiding in the runtime! Consider that our words have at most 10 letters, and some may be repeats. That means that of our 26 iterations of the loop, at least 16 of them are wasted looking for letters that don’t appear. If we call the number of letters in the alphabet A, then the runtime of this algorithm is O(AL).

Interview Tip:

Asymptotic, or “big O”, notation misses constants. Analysis such as treating the size of the alphabet as a parameter is useful to estimate the size of the constants. This is particularly true in this case, where L is guaranteed to be less than the size of the alphabet A.

If the interviewer questions why you’re doing this (after all, English is almost certainly going to have 26 lowercase letters for our lifetimes!) you have the chance to impress them by saying that you’re considering what happens if punctuation is allowed, or if the company decides to look at large unicode character sets. This shows that you’re forward thinking, and have design on your mind – two things that it’s important to emphasize in technical interviews.

Basically, if using a constraint in the problem helps you significantly reduce the problem, feel free to use it. If you need time while you’re working on your solution, or are doing something odd like considering the number of letters in the alphabet as a variable, you can always defend your move as considering the design implications of the constraint!

We can reduce this runtime of our solution significantly by going through each letter in word1 one at a time. This is at most 10 letters, rather than 26. Here’s one way of implementing it:

While the code is longer, and it’s still O(L), it is no longer O(AL). Note that we are no longer assuming the strings are only made of lowercase letters!

Approach 1: Works, but too slow…

We have an anagram checker that will tell us if any pair of words are anagrams.

What is the runtime here? We run through the loop O(N) times, where N is the number of words. If we are lucky, we remove a lot of words early. However, if each word is not an anagram of any other word, the while loop runs exactly N times. Inside the loop, we scan the remaining words for anagrams. So this is an O(N^2) algorithm. Since we can have up to 10^5 words in a list, O(N^2) probably won’t work. Sure enough, this code doesn’t pass the tests on CodeFights – and it’s not an answer that will knock the interviewer’s socks off during a technical interview. We can do better!

Approach 2: Precomputing invariants

We are going to find an invariant that all the words that are anagrams share with each other, but don’t share with any words they are not anagrams of. We will use these as keys in hash tables with dummy values. At the end, we will simply count the number of keys in the hash table.

What are the invariants that we can use? A simple invariant is the number of as, the number of bs, …, etc. Any two words that are anagrams will have the same invariant, and any two words that aren’t anagrams will have different invariants.

For each word, this is an O(AL) process, as we are iterating through both the letters in the word and in the alphabet. The gain is going to occur because we only calculate it once per word.

Our algorithm is then:

Because calcInvariant is O(AL), where L is the number of letters in the word, we see this algorithm has time complexity O(NAL). Note that we never compare invariants. Instead, we use the magic of hash tables to set the value of 1 to the appropriate entry. If that key already exists, we overwrite the value. If it doesn’t exist, a new value is created. It was the comparison between keys that gave us our problematic O(N^2).

A cleaner, faster, invariant

There is another natural invariant for the words: sorting the letters that occur in the words. We could use:

This has the advantage of being easy to understand, and not making any assumptions about the underlying algorithm. It is a sorting algorithm, so it is O(L log L) instead of O(AL). (Technically we can’t compare algorithms using big O notation like this, because we don’t know the constants involved.) The sorted string can then be used for the invariant. In fact, the code for groupsOfAnagrams doesn’t have to change at all!

This is faster because our sorting algorithm on small words is much faster than our O(AL) dictionary. If the words are long (e.g. we are comparing novels) then our compression of the string to count the number of times the characters are repeated would win. When accessing the hash table hash_of_invariants we need to use the hash function, which depends on the length of the keys. Since L < 10, we know that each key is at most 10 characters long, so the sorting invariant is elegant and understandable.

Dictionaries where we don’t care about the value: Sets

In our hash table, we didn’t really care about the values assigned to the keys. We were only interested in the number of distinct keys we had, as that told us how many groups of anagrams we had.

There is nothing wrong with this, except that someone reading your code may wonder what the significance of the 1 is when you wrote:

The comments certainly help. But Python has a built-in data structure for this case called set. If we made a set of invariants instead, we would simply have:

There is not a visible dummy value that might confuse future maintainers of your code. Under the hood, the Python set is implemented as a dictionary (hash table) with hidden dummy values with a few optimizations, so the real reason for doing this is readability. Because hash tables are used more frequently than sets, there is a valid argument that the hash table is more readable for more programmers.

The final solution

Here is our final, compact solution! Any interviewer would be happy to see this solution during a technical interview.

Timing all the methods

In an interview, you always have to consider the runtime. As you could see, a lot of the effort in creating a solution for this interview question was finding an algorithm that was quick enough! I timed the algorithms for two cases:

  • Our first example, words = [listen, admirer, tea, eta, eat, ate, silent, tinsel, enlist, codefights, married]

  • A pathological example, where each word was its own group of 10 letters, starting with abcdefghij, abcdefghik, …, to abgilnoz (this is a total of 10^5 words)

I didn’t include the raw times, as that tells you more about my computer than the algorithm. Instead I normalized to the time for Method D on the list words (i.e. Method D has a time of 1 by definition).

Method Description Time for words (compared to D on words) Time for 10^5 words (compared to D on words)
A O(N^2) method 5.4 Too Long to Time
B Using precalculated tuple invariant for hash table 6.4 70300
C Using sorted words for hash tables 1.2 10450
D Using sorted words for sets 1.0 7000

Tell us…

Did your solution for this Interview Practice challenge look different than mine? How did you approach the problem? Let us know over on the CodeFights forum!

CodeFights Solves It, Interview Practice Edition: productExceptSelf

CodeFights Solves It, Interview Practice Edition: productExceptSelf

If it’s been asked as an interview question at Amazon, LinkedIn, Facebook, Microsoft, AND Apple, you know it’s got to be a good one! Have you solved the challenge productExceptSelf in Interview Practice yet? If not, go give it a shot. Once you’re done, head back here. I’ll walk you through a naive solution, a better solution, and even a few ways to optimize.

…Done? Okay, let’s get into it!

The object of this problem is to calculate the value of a somewhat contrived function. The function productExceptSelf is given two inputs, an array of numbers nums and a modulus m. It should return the sum of all N terms f(nums, i) modulo m, where:

f(nums,i) = nums[0] * nums[1] * .... * nums[i-1] * nums[i+1] * ... * nums[N-1]

Whew!

We can see this most easily with an example. To calculate productExceptSelf([1,2,3,4],12) we would calculate:

  • f([1,2,3,4], 0 ) = 2*3*4 = 24
  • f([1,2,3,4], 1 ) = 1*3*4 = 12
  • f([1,2,3,4], 2 ) = 1*2*4 = 8
  • f([1,2,3,4], 3 ) = 1*2*3 = 6

The sum of all these numbers is 50, so we should return 50 % 12 = 2.

A naive solution

The explanation of the code suggests an implementation:

This is technically correct, but the execution time is bad. Each call to the function f(nums, i) has to do a scan (and multiplication) in the array, so we know the function is O(N). We call f(nums,i) a total of N times, so this function is O(N2)!

Sure enough, this function passes all the test cases. But it gives us a time length execution error on test case #16, so we have to find a more efficient solution.

Division is a better solution (but still not good enough)

A different way of approaching this problem is to find the product of all the numbers, and then divide by the one you are leaving out. We would have to scan to see if any of the numbers were zero first, as we can run into trouble dividing by zero. Essentially, we’d have to deal with that case separately, but it turns out that any array nums with a zero in it is easy to calculate. (This would be a good extension exercise!)

If we look under the constraints of the code, we are told that 1 <= nums[i], so we don’t have to worry about this case. We can simplify our problem to:

Again, we get a time execution error! Note that the running time is much better. We make a pass through the array once to get productAll, then a pass through the array again to get the f_i, and one more pass through the array to do the sum. That makes this is a O(N) solution!

Why is the interviewer asking this question?

In other words, what is this question testing? As I mentioned in the introduction, the function we’re calculating is a little contrived. Because it doesn’t seem to have any immediate applicability, the companies asking us this question in interviews are probably looking to see if we know a particular technique or trick.

One of the assumptions that I made when calling the algorithms O(N) or O(N2) was that multiplication was a constant time operation. This is a reasonable assumption for small numbers, but even for a computer there is a significant difference between calculating

456 x 434

and

324834750321321355120958 x 934274724556120

There are a couple of math properties of residues (the technical name for the “remainders” the moduli give us) that we can use. One is:

(a + b + c ) % m is the same as (a % m + b % m + c % m) % m

This is nice because a%m, b%m, and c%m are all small numbers, so adding them is fast.

The other property is:

(a * b) % m is the same as ((a % m) * (b % m)) % m

That is, I can multiply the remainders of a and b after division by m, and the result I get will have the correct remainder.

At first glance, this doesn’t seem to be saving us much time because we’re doing a lot more operations. We are taking the modulus three times per multiplication, instead of just once! But it turns out that the modulus operation is fast. We more than make up for it by only multiplying small numbers.

So we can change our calculation of f_i to

This still isn’t good enough to pass the test, but we’re getting there. The problems we still have are:

  1. The number productAll is still very large
  2. Integer division is (relatively) slow

Our next approach will eliminate both of these problems.

Note: NOT a property

The big number is productAll, so you might hope that we can find productAll % m, and _then_ do the division. This doesn’t work.

The mathematical problem is that non-zero numbers can be multiplied to give 0, so division is problematic. Looking at division, and then taking a modulus:

48 / 6 = 8_ so _(48 / 6) % 12 = 8

but reversing the order (taking the modulus, then doing the division) yields:

(48 % 12) / 6 = 0 / 6 = 0

So we can’t take the modulus of productAll and avoid big numbers altogether.

Prefix products (aka cumulative products)

We can speed up the execution by building by an array, prefixProduct, so that prefixProduct[i] contains the product of the first i-1 numbers in nums. We will leave prefixProduct[0] = 1.

The neat thing about this array is that prefixProduct[i] contains the product of all elements of the array up to i, not including i. If we also made a suffixProduct such that suffixProduct[i] was equal to all the product of all numbers in nums past index position i, then the productExceptSelf for number i would just be the product of all numbers except the ith one = prefixProduct[i] * suffixProduct[i]

We have eliminated one of the costly operations: division! We can also avoid seeing large numbers in the multiplication as well, by changing the step inside the loop to contain a modulus.

Our new solution is:

This finally works! We’ve eliminated all multiplication by big numbers (but still have multiplications by small numbers), and no divisions at all. But we can still do better…

For the technical interview, an even better solution

It turns out that we don’t need to have a suffixProduct. We can build it as we go! This is the accumulator pattern:

Takeaways

The main things you’re being asked to think about in this task are:

  • Arithmetic operations aren’t always constant time. Multiplying big numbers is much slower than multiplying small numbers.
  • Operations are not all the same speed. Integer modulus is very fast, addition and multiplication are fast, while division is (relatively) slow.
  • Some number theory: You can multiply the residues of numbers, instead of the numbers themselves. But you cannot divide by residues, or divide the residues unless you have certain guarantees about divisibility.
  • The idea of precomputing certain operations, which is where the prefixProduct comes in.

Other problems that use the cumulative or prefix techniques are finding the lower and upper quartiles of an array, or finding the equilibrium point of an array. (I cover prefix sums in a lot more detail in this article.)

Footnote: Horner’s Method

One of the solutions presented used a method of calculation known as Horner’s method. Take the cubic

f(x) = 2 x^3 + 3 x^2 + 2 x + 6

To evaluate f(3) naively would require 8 multiplications (every power x^n is n copies of x multiplied together, and then they are multiplied by a coefficient), and three additions. There is a lot of wasted calculation here, because when we calculate x^3 we calculate x^2 in the process! We could store the powers of x separately to reduce the number of multiplications.

Horner’s method is a way of doing this without using additional storage. The idea is, for example, that we can use operator precedence to store numbers for us:

3 x^2 + 2 x + 6 = (3 * x + 2) * x + 6

The left side has a (naive) count of 4 multiplications and 2 additions, while the right side has 2 multiplications and 2 additions. Moving to the cubic is even more dramatic:

f(x) = 2 x^3 + 3x^2 + 2 x + 6 = ( (2 * x + 3) * x + 2 ) * x + 6

This takes our 8 multiplications and 3 additions to only 3 multiplications and 3 additions!

The shortest solution so far, submitted by CodeFighter k_lee, uses Horner’s method, along with taking moduli at the different steps. See if you can decipher it.

Tell us…

Did your solution for this Interview Practice challenge look different than mine? How did you approach the problem? Let us know over on the CodeFights forum!