Math for Technical Interviews: A Comprehensive Guide

How much math do I need to know for technical interviews?

The short answer is about high school-level math.

Computer science is often associated with math, and some universities even place their computer science department under the math faculty. However, the reality is that you usually only need high school math for most software engineering interviews and day-to-day software engineering jobs.

But I have seen an xxx question on LeetCode that needs a yyy math trick

LeetCode has 3000+ questions, mainly user-submitted. Having a particular question in the vast question bank doesn’t mean very much. What really matters is whether the question is asked in an actual interview. If you look at the top questions companies ask, the questions that require advanced math tricks or knowledge are rarely asked. Questions that require knowing a particular math trick or fact are a knowledge test, and interviews are supposed to test your coding and problem-solving skills, not specific math knowledge.

What if I’m so unlucky that I get asked a tricky math question?

At most companies, candidates’ performance ratings are reviewed by engineers other than the interviewers. And if a question is considered too difficult or off-topic, that round will be considered to carry less significance and assigned less weight in the final decision. So don’t sweat about not knowing advanced math.

What if I don’t even remember high school math?

You can learn it in one hour. Let’s go through it now!

Understanding Number Bases

Base 10

We humans naturally count using the decimal (base 10) system, which has ten unique digits: 0 through 9. Think about how you count: after reaching the number 9, we reset to two digits, starting at 10. This pattern continues, with each position from the right representing an increasing power of 10.

For example, in the number 352:

2 is in the ones place (which is 10 ^ 0)
5 is in the tens place (which is 10 ^ 1)
3 is in the hundreds place (which is 10 ^ 2)

Transition to Base 2 in Computer Science

In contrast, computers operate using the binary (base 2) system. This system has only two unique digits: 0 and 1. The reasons for this binary nature are rooted in the on-off, true-false electronic logic of computer circuits. In the binary system, each position from the right represents an increasing power of 2.

In the binary number 1011:

The rightmost 1 is in the “ones” place (which is 2 ^ 0)
The next 1 is in the “twos” place (which is 2 ^ 1)
The 0 indicates no value in the “fours” place (which is 2 ^ 2)
The leftmost 1 is in the “eights” place (which is 2 ^ 3)

Introduction to Logarithms

What is a Logarithm?

A logarithm answers the question: To what power must we raise a certain base to get a number? In simpler terms, it’s the inverse of an exponential function.

Exponential Examples with Base 2:

2^2 means 2 multiplied by itself once: 2 * 2 = 4
2^3 means 2 multiplied by itself twice: 2 * 2 * 2 = 8
2^4 means 2 multiplied by itself thrice: 2 * 2 * 2 * 2 = 16

Understanding Logarithms with Base 2:

Given a number, the logarithm tells us how many times we need to multiply 2 to obtain that number.

log(8) = 3 means we need three 2’s multiplied together to get 8: 2 * 2 * 2
log(16) = 4 means we need four 2’s multiplied together to get 16: 2 * 2 * 2 * 2

Alternatively, the logarithm tells us how many times we can divide a number by 2 until we reach 1:

8 / 2 / 2 / 2 = 1 - Dividing 8 by 2 three times gives 1, so log(8) = 3
16 / 2 / 2 / 2 / 2 = 1 - Dividing 16 by 2 four times gives 1, so log(16) = 4

Logarithms, especially with base 2, are fundamental in computer science because many computational problems instinctively split themselves in half.

Permutations and Factorials

Sets and Sequences

Set: A collection of distinct items, referred to as “elements,” where the order of the items does not matter. E.g., {a, b}.
Permutation: A specific arrangement or ordering of the elements of a set. In permutations, the order is crucial. For the set {a, b}, we have two permutations: [a, b] and [b, a].

The following figure shows all the permutations of (a, b, c).

Counting Permutations

Imagine arranging three letters: a, b, and c.

For the first position, you have 3 choices (a, b, or c). Once you’ve chosen the first letter, only 2 remain for the second position. For the third and final position, only 1 letter is left.

This gives a total of 3 * 2 * 1 permutations, or 6 possible sequences: [a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a, b], and [c, b, a].

We can generalize this idea to count the number of permutations for a set of size n.

For the first position, we have n choices. Once the first position has been fixed, there’s n - 1 choice for the second position. Then, we have n - 2 choices for the third position. We’ll keep making choices until only 1 letter is left.

From this, we can get that the number of permutations for a set of size n is n * (n-1) * (n-2)… * 1. This is called the factorial of n, denoted by n!. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120. This means there are 120 ways to arrange 5 letters in a row.

Understanding Subsets

What is a Subset?

A subset of a set A is another set that contains only the elements that are also present in A. For instance, the set {1, 3, 9} is a subset of {1, 2, 3, 5, 6, 7, 9} because every element of the former is present in the latter.

How Many Subsets Can a Set Have?

When we look at the elements of a set, for each element, we have a choice:

Include it in the subset
Exclude it from the subset

This gives two possibilities for each element.

Here’s a figure to illustrate this. Think of it like switches: each element has a switch that can either be “ON” (included in the subset) or “OFF” (excluded from the subset).

With one element (or switch), we have 2 ^ 1 or 2 possible states. With two elements, we have 2 ^ 2 or 4 possible states. With three elements, we’ll get 2 ^ 3 or 8 possible states.

Expanding on this idea, if a set has n elements, then there will be 2 ^ n subsets. Note that these 2 ^ n subsets include the empty subset (where no elements are chosen) and the original set itself (where all elements are chosen).

Arithmetic Sequence

An arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant. For example:

1, 2, 3, 4, 5 is an arithmetic sequence because the difference between consecutive numbers is 1.
1, 3, 5, 7, 9 is an arithmetic sequence because the difference between consecutive numbers is 2.
1, 2, 4 is NOT an arithmetic sequence because 2 - 1 = 1 (first difference) but 4 - 2 = 2 (second difference). Here, the differences between consecutive terms are different.

Sum of an Arithmetic Sequence

The sum of an arithmetic sequence is (first_element + last_element) * number_of_elements / 2.

For example:

sum([1, 2, 3, 4, 5]) = (1 + 5) * 5 / 2 = 15
sum([1, 3, 5, 7, 9]) = (1 + 9) * 5 / 2 = 25

Because last_element = first_element + difference * (number_of_elements - 1), the sum can be expressed as (2 * first_element + difference * (number_of_elements - 1)) * number_of_elements / 2.

In Big-O complexity analysis, we drop the constant terms (first_element, difference, and -1), so this really becomes O(n^2).

When is Arithmetic Sequence Useful [for my interviews]?

It’s sometimes useful for nested loop complexity analysis.

Consider the code below:

n = 10
for (i = 0; i < n; i++) {
  for (j = 0; j <= i; j++) {
    doSomething();
  }
}

Here, i goes from 0 to n, while j goes from 0 to i, meaning that j can run i + 1 times. The time complexity of the nested loop is, therefore, 1 + 2 + 3 + 4 + … + n, which is an arithmetic sequence with a common difference of 1. The number of elements is n, and the sum is O(n^2).

Geometric Sequence

In a geometric sequence, each term is found by multiplying the previous term by a constant factor called the common ratio.

For example:

2, 4, 8, 16, 32 is a geometric sequence where the common ratio is 2.
1, 2, 4, 8, 16 is a geometric sequence where the common ratio is 2.
3, 6, 12, 24 is a geometric sequence where the common ratio is 2.

The sum of a geometric sequence is

sum = first_element * (1 - (common_ratio ^ number_of_elements)) / (1 - common_ratio).

Since we drop constants in Big-O notation, the sum of a geometric sequence is O(first_element * common_ratio ^ number_of_elements).

Sum of Digits

Given a non-negative integer, finding the sum of its digits is a simple yet frequently asked question in coding interviews. To understand how to approach this, let’s break down the problem.

Breaking Down the Problem

Consider the number 123. The goal is to break it down into its individual digits:

The digit ‘1’ represents the hundreds place: 1 * 100.
The digit ‘2’ represents the tens place: 2 * 10.
The digit ‘3’ represents the ones place: 3 * 1.

Mathematically, 123 = 1 * 10^2 + 2 * 10^1 + 3 * 10^0.

To extract the digits:

Use modulo (modulus) to get the last digit: 123 % 10 = 3.
Divide by 10 to remove the last digit: 123 / 10 = 12.
Repeat the steps to extract all digits.

Implementing the Solution

Here’s a simple algorithm:

Initialize a variable sum = 0.
While the number is greater than 0:
1. Add the last digit of the number to the sum.
2. Remove the last digit by dividing the number by 10.
The sum will contain the sum of all digits.

Example: For 123:

Initialize sum = 0.
123 % 10 = 3; sum = 3. Now, 123 / 10 = 12.
12 % 10 = 2; sum = 5. Now, 12 / 10 = 1.
1 % 10 = 1; sum = 6. Now, 1 / 10 = 0.
The final sum of digits is 6.

Analyzing the Time Complexity

Each operation (modulo and division) is O(1), and you perform these operations for each digit. If the number has d digits, the time complexity is O(d).

Combinatorics

Combinations and Probability

Combinations are a crucial concept in combinatorics, where order does not matter. This is particularly important when you want to calculate the probability of a specific event happening.

For example, let’s say you have 5 objects, and you want to choose 3 out of them. The order in which you choose the objects doesn’t matter. The number of combinations is calculated as:

nCr = n! / (r! * (n - r)!)

Where n is the total number of objects, and r is the number of objects to choose.

Example:

n = 5, r = 3
nCr = 5! / (3! * (5 - 3)!) = 10

This means there are 10 different ways to choose 3 objects from a set of 5.

Applications of Combinations

Combinations are often used in probability problems. For example, if you want to know the probability of drawing 2 aces from a deck of cards, you would use combinations to determine the number of favorable outcomes divided by the total possible outcomes.

Pigeonhole Principle

The Pigeonhole Principle is a simple yet powerful concept in combinatorics. It states that if you have more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon.

In other words, if you have n + 1 objects and n containers, at least one container must contain more than one object.

Example Problem

If you have 6 pairs of socks in a drawer, and you randomly select 7 socks, the Pigeonhole Principle guarantees that you will have at least one matching pair.

Big-O and Counting

The Pigeonhole Principle is often used in Big-O analysis to show that certain algorithms cannot be faster than a particular bound. For example, if you need to search for a specific value in a list of n elements, you can’t do better than O(n) in the worst case because you might have to check every element.

What Else?

This article covers the basic mathematical concepts you need to understand for most technical interviews. While there are more advanced topics, they are less likely to appear in interviews unless you’re applying for a specialized role that requires deep mathematical knowledge.

In summary, focus on understanding these core concepts and practicing their application in coding problems. This will give you a strong foundation for tackling most technical interviews.