### Tag: interview question

Interview Basics: Static vs. Dynamic Arrays

## Interview Basics: Static vs. Dynamic Arrays

Arrays are one of the most basic data structures in computer science. But they form the basis of some difficult technical interview questions! So no matter where you are in your programming career, you need to be very familiar with arrays and how to use them. Read on to review the basics of static and dynamic arrays, then watch our video to get clear on the differences between them. And once you’re ready to solve some array-based technical interview questions on your own, head to Interview Practice. You’ll be able to practice solving array interview questions that have been asked at Google, LinkedIn, Apple, Uber, and Palantir.

## First Things First

Whatever programming language you choose use in an interview, make sure you know its array methods very well. Like, forwards and backwards well. Interviewers will definitely be judging you on this! If you don’t know something basic like this in the language you’ve chosen to interview with, they’ll question how well you know that language at all… Not to mention how well you can program, period. So spend some time with your language’s documentation to make sure that you’ve got a handle on its basic and advanced array methods.

## Arrays

The simplest definition of an array is that it’s a data structure that contains a group of elements. In interviews, you’ll get a lot of questions about static arrays, which are the most basic implementation of this data structure. You’ll also get questions about dynamic arrays. We’re going to focus on static and dynamic arrays in this article. (You’ll also get questions about multidimensional arrays in technical interviews, which we’re going to cover in an upcoming article.)

## Static Arrays

The most basic implementation of an array is a static array. A static array is a random-access data structure with a fixed size. You have to declare its size when you first initialize it. To add or remove elements from a static array, you have to create a new appropriately-sized contiguous chunk of memory. Then you have to copy the elements that you want to keep into this new array.

The good: The item lookup by index for static arrays is really quick (O(1)), and they have a very low memory footprint.

The bad: Adding elements to or deleting elements from the array is an O(n) operation, where n is the number of elements in the array. Searching the array for a particular element is also O(n). Arrays don’t allow for the quick rearrangement of their elements.

## Dynamic Arrays

A dynamic array is a random-access, variable-sized list data structure that elements can be added to or removed from. They’re basically like static arrays, but with the addition of space that’s reserved for adding more elements. When dealing with a dynamic array, there are two important factors to consider. There’s the logical size of the array (the number of elements being used by the array’s contents) and its physical size (the size of the underlying array). The physical size is counted in either the number of elements the array has room for, or the number of bytes used. In a technical interview, you should use a dynamic array if you know you’ll need to add or delete information.

The good: On average, it’s quick to insert elements to the end of the dynamic array. And item lookup by index is O(1).

The bad: They don’t allow for the quick rearrangement of their elements. And they have inconsistent runtimes for adding elements to the array, so they’re not good for real-time systems.

## Diving Deeper

Now that you’re clear on the basics of static and dynamic arrays, watch this video for a deeper dive on the differences between the two.

## Bonus Array Joke

1. Why did the programmer leave his job?
2. Because he didn’t get arrays.

(Get it? Arrays, “a raise”! Stop groaning. It’s a great joke.)

Interview Practice: Graphs, Advanced Trees & RegEx

## Interview Practice: Graphs, Advanced Trees & RegEx

We’ve just added three-brand new computer science topics to Interview Practice! Get ready to dive deep on Graphs, Trees: Advanced, and RegEx. We’ve added these topics to our Extra Credit learning plan, which covers all of the topics in Interview Practice.

Why are these topics so important to know for technical interviews? Read on for a brief introduction to each concept!

### Graphs

A graph is an abstract data structure composed of nodes and the edges between nodes. Graphs are a useful way of demonstrating the relationship between different objects. For instance, did you know that you can represent social networks as graphs? Or that the 6 Degrees of Kevin Bacon game can be modeled as a graph problem? Graph questions are really common in technical interviews. In some cases, the question will be explicitly about graphs, but in other cases the connection is more subtle. Read our tutorial to get up to speed on this topic and to learn how to identify this kind of question. Then practice your skills on graph questions from real technical interviews!

A tree is a data structure composed of parent and child nodes. Each node contains a value and a list of references to its child nodes. Tree traversal and tree implementation problems come up a lot in technical interviews. Common use-cases for an interview are: needing to store and do searches on data that is sorted in some way; needing to manage objects that are grouped by an attribute (think computer file systems); or implementing a search strategy like backtracking. You need to be very familiar with how to deal with these kinds of questions! (The tasks in Trees: Advanced ramp up in difficulty from the ones you get in the Trees: Basic category, so make sure you finish those questions before moving on to these ones!)

### RegEx

A regex is a string that encodes a pattern to be searched for (and perhaps replaced). They let you find patterns of text, validate data inputs, and do text replacement operations. A well-written regex can make it easier to solve really tricky interview questions like “Find all of the 10-digit phone numbers in a block of text, where the area code might or might not be surrounded by parentheses and there might or might not be either a space or a dash between the first and second number groupings”. While the specifics of how to implement a regex can vary between languages, the basics are pretty much the same. In the topic tutorial, we cover regex character classes, quantifiers, anchors, and modifiers and how to use them to write a good regex.

### Start now

These topics might not get asked in every interview, but they’re important to know! Read the tutorials about each concept, then solve the real interview tasks to practice your skills and solidify your understanding of the topic. (Learn more about how we’ve updated the Interview Practice experience to make it an even better practice and preparation tool.)

If you’re signed up for the Extra Credit learning plan, these topics have been added to your Interview Practice page already. If you’re signed up for a different learning plan, you can switch over to Extra Credit. Or you can sign up for a customizable Freestyle plan and add these topics!

Do you need to prepare for technical interviews?

## Do you need to prepare for technical interviews?

If you’re already working as a software engineer, you might think that you don’t need to do any preparation for your next technical interview. Maybe you write C++ that’s pure poetry, or perhaps your SQL queries are so efficient that they make grown men weep. So when you’re looking for a new job, it’s easy to fall into the trap of assuming that you’re ready for interviews right away – no prep needed. But are you?

Sidebar: If you’re not working as a software engineer yet, don’t stop reading! A lot of this applies to you too. And we’re going to be posting another article about preparing for coding interviews specifically for you very soon. Stay tuned!

Think back to your last interview experience.

What kind of questions did you get asked? Some of the questions might have been pretty straightforward, aimed at evaluating how well you could do the task at hand. And if that task was something you were already pretty comfortable doing, you probably didn’t have too much trouble getting it done.

But chances are good that you also got some pretty esoteric or challenging questions. Questions that were more about testing whether you remembered how to implement certain algorithms or data structures… potentially ones that you hadn’t touched since you were in school.

Let’s face it: You’re good at your job, but that doesn’t necessarily mean you’re good at interviewing. Interviews are a completely different beast.

Bottom line: If you’re looking for a new job, you might not be as prepared as you think you are.

Tigran Sloyan, the founder of CodeFights, puts it this way:

“The reality is that the interview questions you’ll face at most companies are miles away from what you do at your day job, so make sure to do some research and practice using real questions that the company uses in its interviews.”

You might think that traditional technical interviews don’t effectively measure how well you would actually perform on the job, and you’re not alone in that. But the fact is that for now, most companies rely on them to weed out people who can’t cut it. They also use them to gauge the aptitude, interest, and intelligence of those who can.

### What should you practice?

A mainstay of the technical interview process is asking questions that help the interviewer determine how well a candidate understands computer science fundamentals like data structures and algorithms, whether they can implement them appropriately, and whether they take time and space complexity into account.

A great way for you to revisit these concepts and get those rusty skills back up to snuff is solving Interview Practice challenges on CodeFights. All 100+ of these questions are pulled directly from actual interviews at top tech companies. You can filter by company and by question topic, which gives you a personalized experience that lets you focus on the topics you need to practice the most.

The list of topics you need to study will be largely informed by research that you’ve done on the companies you are interviewing at (or would like to interview at). If you know that a company is likely to ask you questions about tree traversal, you can start working on tree traversal interview questions to prepare! It’s really important to be honest with yourself about the current state of your skills and knowledge. For example, you might have been a dynamic programming expert in college. But if you’ve been a front-end developer working strictly in HTML, CSS, and JavaScript for the past few years, you probably need a refresher.

### Finding time

One common issue that we hear from professionals who are starting to look for new programming jobs is that they don’t have time to practice technical interview questions. It’s true that adding yet another commitment on top of your job and your real life can be daunting. Once you’ve determined what it is that you need to study, you’ll need to carve time out to make that happen.

This is going to look different for everyone. Do you actually have an interview in three weeks? Then that’s your timeline. If you’re just at the contemplation stage and don’t have any interviews lined up yet, then your timeline might be more in the month to two months range. In general, though, it’s best to keep your timeline fairly short. Having a longer timeline means that you risk losing focus and drive.

Now that you know your timeline and what you need to study, it’s time to set your routine. A routine benefits most people because it becomes a built-in framework to adhere to, which in turn creates accountability. There are countless different schools of thought about what constitutes an effective routine, but they all have one thing in common: consistency. You have to practice consistently in order to see the benefits from it. For most people, at least an hour a day is ideal. If your timeline is short, try to spend more time daily. You may have to scale back on some other commitments while you’re in interview preparation mode!

#### Stick to it!

Once you’ve got a routine that works for you, stick to it. This is the hard part, because it usually involves scaling back on other, more fun parts of your life. But stick to your guns and protect the time you’ve set aside for practice. Remember, this isn’t a forever commitment! Once you’ve gotten to your goal, you can lay off on the interview preparation and get back to whatever it was that you had to scale back on to find the time, whether it’s watching Friends reruns or running marathons.

### Practice pays off

We know you’re a good engineer. You know you’re a good engineer! But technical interviews require different skills – and like any other skill, you have to work to get better. Actually writing code that solves the actual technical interview questions makes you more comfortable with the process. We can’t emphasize this enough: The absolute best way to ensure that you’re good at interviewing is to practice solving coding interview problems!

Now go get ’em, tiger. You’re going to knock that interviewer’s socks off!

### On the job hunt? Read these articles too:

Resumes. Not fun, right? But in a lot of cases, they’re a necessary part of the job search process. Read Make Your Engineering Resume Stand Out to find out how to write a resume that really highlights your programming skills and experiences and makes you stand out from the crowd of applicants.

Once you’re on a company’s radar, there’s still a few steps before you make it to the in-person technical interview! First, you have to get past the recruiter phone screen. Read Ace Your Phone Screen By Telling Your Story, Pt. 1  to learn how to create a personal elevator pitch that resonates with recruiters. Then check out Ace Your Phone Screen By Telling Your Story, Pt. 2 for tips on how to wow the recruiter during the phone screen itself.

## Tell us…

What’s your take on preparing for interviews? If you do prepare (and we hope you do), what does your process look like? Let us know over 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.

## 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.

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.

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:

${\text{numGoodStringsOfLength3}}=4\times(\text{numWaysOfPicking3LettersFrom26})=4\times{{26}\choose{3}}=4\times\frac{26!}{4!22!}$
where $n\choose{r}$ 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 ${{26}\choose{n}}\times\text{good}(n)$.

## 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 ${{n}\choose{j}}$. (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 ${{5}\choose{2}}=10$ 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 ${{n}\choose{j}}-1$.

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:

$\text{good(n)}=\large\sum_{j=1}^{n-1}\bigg[{{n}\choose{j}}-1\bigg]$

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:

• ${{n}\choose0}={{n}\choose{n}}=1$, 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 $\bigg[{{n}\choose{j}}-1\bigg]$ gives zero. Now we can rewrite:
$\text{good(n)}=\large\sum_{j=1}^{n-1}\bigg[{{n}\choose{j}}-1\bigg]=\large\sum_{j=0}^{n}\bigg[{{n}\choose{j}}-1\bigg]=\large\sum_{j=0}^{n}\bigg[{{n}\choose{j}}\bigg]-(n+1)$
• You might remember from Pascal’s triangle that
$\large\sum_{j=0}^{n}\bigg[{n\choose{j}}\bigg]=2^n$
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:

$\text{good}(n)=\text{(numberofgoodsequencesof[1,2,3,...,n])}=2^n-(n+1)$

## Putting it all together

From our overall strategy, we had ${26\choose{n}}$ 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:

${26\choose{n}}\times(2^n-n-1)$

## …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 ${n\choose{r}}$ 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:
$n(n-1)(n-2)(n-3)=n(n-1)(n-2)(n-3)\times\frac{(n-4)\ldots(2)(1)}{(n-4)\ldots(2)(1)}=\frac{n!}{(n-4)!}$
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 $4\times3\times2\times1=4!$ ways. The number of combinations for picking r=4 things from n items is:

${n\choose4}=\frac{n!}{(n-4)!4!}$

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:

${n\choose{r}}=\frac{n!}{(n-r)!r!}$

## 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:

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.

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.

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

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!

## 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.)

## 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

• 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!

Mastering the Basics for Technical Interviews

## Mastering the Basics for Technical Interviews

It’s natural to want to focus on really tricky concepts when you’re preparing for interviews. You know you’re going to get some really hard problems, and so that’s the stuff that you want to practice! But we hear stories all the time about people who prepare for higher-level questions, only to completely blank out when they get questions about the basics. And we definitely don’t want that to happen to you!

You absolutely need to be able to answer questions about programming basics quickly and easily, because for most interviewers, this represents the baseline of what you should be able to do. And if you don’t perform well, this can automatically put you out of the running even if you’ve done well on the rest of the interview.

## The basics

Consider the fizzBuzz conundrum that Imran Ghory and others have written about: A surprising amount of seemingly well-qualified applicants are unable to answer even trivial programming questions during technical interviews. An example of this sort of question is the old standby fizzBuzz, which asks the interviewee to write a program that takes a number n and print out the numbers from 1 to n, replacing multiples of 3 with fizz, multiples of 5 with buzz, and multiples of both 3 and 5 with fizzbuzz. (Go ahead, take a minute and do it. We know you want to.) While the odds that an interviewer actually asks you to solve fizzBuzz is pretty low since it’s well-trod territory at this point, it’s a good example of the level of this type of “basic” question.

Questions like this are aimed at making sure that you have a fundamental understanding of how to write code. The interviewer also wants to make sure that you can problem-solve in ways that take test cases and optimization into account. Since this sort of question is usually asked while you’re whiteboarding, interviewers also use this to gauge how you think while you’re working through a problem.

It’s also important that you actually know your favored interviewing language well. Can you write loops, use appropriate methods when they’re available to you, and use the right terminology when you’re discussing elements of the code you’re writing? If not, it’s going to show and the interviewer is going to pick up on it.

## Technical interview topics

What basic things should you be really solid on in order to prepare for technical interviews? They tend to fall into a few basic categories:

• String manipulation (Generate permutations, find substrings, reverse a string, substitute specific letters…)
• Array manipulation or traversal
• Number manipulation
• Pattern matching (If necessary, be ready to write your own regular expression rather than using a regex library)
• Condition matching (Find the largest/smallest/missing element)

Remember, this represents the baseline of what you should know in order to succeed in an interview (not to mention on the job). You’ll actually need to know a lot more advanced stuff to ace the interview – and don’t worry, Interview Practice has you covered on that front too. But even if you do well on more advanced topics, if you don’t wow the interviewer on the simple ones they’re going to question how capable you actually are. So don’t neglect the basics! Here are some great examples on Interview Practice to get you started:

## Tell us:

Have you ever encountered a basic programming question in an otherwise hard interview? How did you handle it? Let us know on the CodeFights forum!