# How to approach algorithm problems

## An example that's probably closer to what you're experiencing in coding interviews

A lot of articles often give advice on how to approach coding interview questions. However, what I find lacking in these is the actual examples that they give. Most often these examples are very generic (e.g, may just require memorizing how to do BFS, for example), or are almost insultingly simple (i.e., you probably don’t need the special workflow if you’re just doing fizzbuzz, but in real life you’re going to encounter problems much tougher than that). Algorithm challenges can take many different unexpected turns. It used to be the case that just reading “Cracking the coding interview” was enough to pass an interview. Then interviewers caught on to the patterns and problems from that book. Then sites like Leetcode started coming up. Studying to sites like those worked for a bit, but then interviewers caught on again. Part of the reason for this is that some interviews try to make the process intentionally stressful.

With that in mind, I decided to try and replicate the experience in blog-post form. THe following problem was inspired by an interview experience I had with a company that will remain unnamed. I chose this because, unlike the problems on many other sites, I could not find any other tutorials or LeetCode problems or other renditions of this problem elsewhere on the internet. Having answers to problems readily available can give you a false sense of confidence. An entire industry has built up around teaching to the test when it comes to coding interviews, and as such companies like Google do their best to move away from cookie-cutter challenges.

### Problem Definition

There are $n$ cities numbered from $1$ to $n$. Two cities, $x$ and $y$, are connected by a bidirectional road if and only if $\text{gcd}(x,y) > g$, where $\text{gcd}$ is the greatest common divisor of $x$ and $y$. Julia is planning a long vacation and wants to know whether a path exists from city $x$ to city $y$.

Complete the connectedCities function; it has four parameters:

Name | Type | Description |
---|---|---|

`n` | integer | The number of cities. |

`g` | integer | Cities $x$ and $y$ are connected if and only if $\text{gcd}(x,y)>g$. |

`originCities` | integer array | Each index $i$ (where $0 \leq i \leq q$) describes $x$ for the $i^{th}$ pair of cities. |

`destinationCities` | integer array | Each index $i$ (where $0 \leq i \leq q$) describes $y$ for the $i^{th}$ pair of cities. |

The function must return an array of $q$ integers where the value at each index $i$ (where $0 \leq i \leq q$) is $1$ if a path exists from city $\text{originCities}_i$ to city $\text{destinationCities}_i$; otherwise, it’s $0$ instead.

**Input Format**

The code to read the inputs from stdin and to pass it to the function `connectedCities`

is provided for you. The below is documentation in case you need to create custom testcases.

- The first line contains an integer denoting $n$.
- The second line contains an integer denoting $g$.
- The third line contains an integer, $q$, denoting the total number of elements in $\text{originCities}$.
- Each line $i$ of $q$ subsequent lines (where $0 \leq i \leq q$) contains an integer describing $\text{originCities}$.
- The next line contains an integer, $q$, denoting the total number of elements in $\text{destinationCities}$.
- Each line $i$ of $q$ subsequent lines (where $0 \leq i \leq q$) contains an integer describing $\text{destinationCities}$.

**Constraints**

- $2 \leq n \leq 2 \times 10^5$
- $1 \leq g \leq n$
- $1 \leq g \leq min(n \times (n - 1)/2, 10^5)$
- $1 \leq \text{originCities}_i, \text{destinationCities}_i \leq n$, where $0 \leq i \leq q$
- $\text{originCities}_i \neq \text{destinationCities}_i$, where $0 \leq i \leq q$

**Output Format**

Return an array of $q$ integers where the value at each index $i$ (where $0 \leq i \leq q$) is $1$ if a path exists from city $\text{originCities}_i$ to city $\text{destinationCities}_i$; otherwise, it’s $0$ instead.

### Step 0: Remember, the interviewer is your friend

Interviews can seem intimidating at first (especially if you’re toward the beginning of a stretch of interviewing with multiple bottom-of-the-market companies for practice). It’s important to keep in mind that, while writing out code on a whiteboard of live typing may be unusual, don’t be intimidated by the interviewer. You should think of this as a trial pair-programming. The interviewer is not just trying to see how much you remmeber from your first-semester CS classes, but they’re also previewing what it’s like to work with you as a co-worker. The interviewer also wants you to succeed. Nobody likes interviewing interviewing a candidate for 3 stages of interviews, only to cut things off at the third. Your interviewer is rooting for you.

Back to the subject of the specific problem:

### Step 1: Language Choice

Before you even start, you should have some idea of what language you want to do this interview in. You should ideally pick a language that you are most comfortable with *and* that you would be using a lot during the course of the interview. For me, since I’ve mainly been doing Machine Learning, my languages of choice might be either Python or JavaScript.

For larger companies like Google or Facebook, SWEs might be expected to have knowledge of languages with more significant differences between them. In other words, Python and JavaScript might be too similar, and you would be better off choosing two out of the set of Python, Java, or C++.

If you’re doing a full whiteboard-style interview, make sure you’re used to writing your code out by hand on paper first. I would also recommend you choose a less verboe language like python, as it saves you a lot of time that you can use for reasoning and asking questions instead of writing eveything out.

For the sake of this article, I’m going to be doing my reasoning in Python because 1) it is by far the language I am most comfortable with, 2) it’s the the quickest to type and write (I will demonstrate by eventually showing the final answer in both typed and written format), and 3) Python is poised to pass Java as one of the most in-demand and highest-paying programming languages.

### Step 2: Come up with Example Outputs

In any coding interview, it’s important to clarify exactly what the question is asking. You want to avoid spending a full 30 minutes defining a solution for the wrong question (it won’t matter how elegant it is). If you’re in a bind and you’re not seeing any easy solutions come up, this will at least buy you some time. Let’s say you ask for an example for this problem, and the interviewer gives the following: 6 cities, 4 paths, with the greatest common denominator threshold being $0$.

**Sample Input 1**
$n = 6$
$g = 0$
$\text{originCities} = [1,4,3,6]$
$\text{destinationCities} = [3,6,2,5]$

We can expect an output like this:

**Sample Output 1**

```
1
1
1
1
```

### Step 3: Come up with a brute-force solution

To further confirm that you understand the problem, you can come up with an algorithm that throws runtime to the wind and assumes infinite time and resources. This is mainly to clarify that you understand what the pattern of outputs are, not so much what your solution to the algorithms is. If you are struggling with finding the optimial solution even after clarrifying some example outputs, this can also be a good way of buying time. It is highly possible that you could just create a gargantuan nest of `while`

loops for this problem.

(I should also clarify that while these techniques describe “buying time”, you probably should not delay if you can avoid it. If you have to pause, these techniques mean that you can at least fill the pause with some discussion of the nature of the problem, instead of sitting in slicence.)

### Step 4: Think of a simpler version of the same problem

What would this problem look like if we removed some of these conditions? For example, what would the problem look like if we didn’t need to trace the full path, and only needed to focus on whether the nodes have $\text{gcd}(x,y)>g$?

In that case, this would turn into a relatviely straightforward greatest commond denominator problem. You might be able to get some points by making it clear that you can stick to first principles. For example, you can let the interviewer know that you can do problems like that with recursion…

```
def gcd_rec(a,b):
if(b==0):
return a
else:
return gcd_rec(b,a%b)
```

…or loops…

```
def gcd_loop(a, b):
if a > b:
small = b
else:
small = a
for i in range(1, small+1):
if((a % i == 0) and (b % i == 0)):
gcd = i
return gcd
```

…or ideally using Euclid’s algorithm:

```
def gcd_euclid(a, b):
while(b):
a, b = b, a % b
return a
```

If you can build up the problem out of smaller sub-problems, this will work great towards demonstrating a rational and easy-to-follow reasoning process to the interviewer.

### Step 5: Think of simpler or more examples to try and notice a pattern

Let’s try another example output to this, perhaps one that explicitly does NOT result in similar outputs as the one before. What could we do to get an output that is *not* all 1’s?

**Sample Input 2**

$n = 6$ $g = 1$ $\text{originCities} = [1,2,4,6]$ $\text{destinationCities} = [3,3,3,4]$

**Sample Output 2**

```
0
1
1
1
```

Once you try another scenario like this, it should become easier to see a pattern.

### Step 6: Try to use some visualization

Let’s try visualizing what our reasoning from before was. Let’s refer back to Example 1:

**Explanation 1**

What about Example #2?

**Explanation 2**

With all this in mind, I would recommend trying to solve the problem yourself before scrolling down to the solution.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Regardless of whether you made the attempt (if you did, kudos to you for the awesome study ethic), here is the final optimized version.

### Step 7: Our Final Solution

Here is the code for our final algorithm in python:

```
import sys
def get_root(a, root):
while (a != root[a]):
a = root[a]
return a
def union_find(a, b, root, ids):
roota = get_root(a, root)
rootb = get_root(b, root)
if roota == rootb:
return
if ids[roota] < ids[rootb]:
root[roota] = root[rootb]
ids[rootb] += ids[roota]
else:
root[rootb] = root[roota]
ids[roota] += ids[rootb]
def connectedCities(n, g, originCities, destinationCities):
root = [None]*(n + 1)
ids = [None]*(n + 1)
for i in range(0, n+1):
root[i] = i
ids[i] = 1
for i in range(g + 1, n + 1):
for j in range(2*i, n+1, i):
union_find(j, i, root, ids)
city_list = []
for i in range(0, len(originCities)):
if get_root(originCities[i], root) == get_root(destinationCities[i], root):
city_list.append(1)
else:
city_list.append(0)
return city_list
```

Let’s see how it does against some sample inputs. We can run the test cases above, plus an additional one, and see if the outputs match our expectations:

**Test cases**

```
if __name__ == "__main__":
n, g, originCities, destinationCities = 6, 0, [1,4,3,6], [3,6,2,5]
res = connectedCities(n, g, originCities, destinationCities)
print("\n", res)
n, g, originCities, destinationCities = 6, 1, [1,2,4,6], [3,3,3,4]
res = connectedCities(n, g, originCities, destinationCities)
print("\n", res)
n, g, originCities, destinationCities = 10, 1, [10, 4, 3, 6], [3, 6, 2 ,9]
res = connectedCities(n, g, originCities, destinationCities)
print("\n", res)
```

**Outputs**

```
[1, 1, 1, 1]
[0, 1, 1, 1]
[1, 1, 1, 1]
```

Which it does…there we have it!

If python is not your strongest language (though I recommend choosing this for the sake of brevity), here is an example of an equivalent function in C++

**C++ version**

If you manage to do this on a whiteboard, you are either brilliant when it comes to low-level systems, or you are a masochist.

```
#include <bits/stdc++.h>
using namespace std;
#define int long
vector <int> vec, siz;
int root(int a)
{
while(a!=vec[a]) a=vec[a];
return a;
}
void union_find(int a, int b)
{
int roota = root(a);
int rootb = root(b);
if(roota==rootb) return;
if(siz[roota]<siz[rootb])
vec[roota]=vec[rootb];
siz[rootb]+=siz[roota];
else
vec[rootb]=vec[roota];
siz[roota]+=siz[rootb];
}
vector <int> connectedCities(int n, int g, vector <int> originCities, vector <int> destinationCities) {
vec.clear();
int N=n;
for(int i=0;i<=N; i++) vec.push_back(i);
siz.assign(N+1, 1);
for(int i=g+1; i<=N; i++)
for(int j=2*i; j<=N; j+=i)
union_find(j, i);
vector <int> ret_vec;
for(int i=0; i<originCities.size(); i++)
if(root(originCities[i]) == root(destinationCities[i]) ) ret_vec.push_back(1);
else ret_vec.push_back(0);
return ret_vec;
}
```

This was just an example post detailing some useful mindsets and strategies for getting through algorithm challenges (as well as a test of how well I can get code to render on this website. Checks out great so far!).

If you want to see more posts on programming and/or coding strategies, let me know!

Cited as:

```
@article{mcateer2019algos,
title = "How to approach algorithm problems",
author = "McAteer, Matthew",
journal = "matthewmcateer.me",
year = "2019",
url = "https://matthewmcateer.me/blog/how-to-approach-algorithm-problems/"
}
```

*If you notice mistakes and errors in this post, don’t hesitate to contact me at [contact at matthewmcateer dot me] and I will be very happy to correct them right away! Alternatily, you can follow me on Twitter and reach out to me there.*

See you in the next post 😄