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 nn cities numbered from 11 to nn. Two cities, xx and yy, are connected by a bidirectional road if and only if gcd(x,y)>g\text{gcd}(x,y) > g, where gcd\text{gcd} is the greatest common divisor of xx and yy. Julia is planning a long vacation and wants to know whether a path exists from city xx to city yy.

Complete the connectedCities function; it has four parameters:

Name Type Description
n integer The number of cities.
g integer Cities xx and yy are connected if and only if gcd(x,y)>g\text{gcd}(x,y)>g.
originCities integer array Each index ii (where 0iq0 \leq i \leq q) describes xx for the ithi^{th} pair of cities.
destinationCities integer array Each index ii (where 0iq0 \leq i \leq q) describes yy for the ithi^{th} pair of cities.

The function must return an array of qq integers where the value at each index ii (where 0iq0 \leq i \leq q) is 11 if a path exists from city originCitiesi\text{originCities}_i to city destinationCitiesi\text{destinationCities}_i; otherwise, it’s 00 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 nn.
  • The second line contains an integer denoting gg.
  • The third line contains an integer, qq, denoting the total number of elements in originCities\text{originCities}.
  • Each line ii of qq subsequent lines (where 0iq0 \leq i \leq q) contains an integer describing originCities\text{originCities}.
  • The next line contains an integer, qq, denoting the total number of elements in destinationCities\text{destinationCities}.
  • Each line ii of qq subsequent lines (where 0iq0 \leq i \leq q) contains an integer describing destinationCities\text{destinationCities}.

Constraints

  • 2n2×1052 \leq n \leq 2 \times 10^5
  • 1gn1 \leq g \leq n
  • 1gmin(n×(n1)/2,105)1 \leq g \leq min(n \times (n - 1)/2, 10^5)
  • 1originCitiesi,destinationCitiesin1 \leq \text{originCities}_i, \text{destinationCities}_i \leq n, where 0iq0 \leq i \leq q
  • originCitiesidestinationCitiesi\text{originCities}_i \neq \text{destinationCities}_i, where 0iq0 \leq i \leq q

Output Format

Return an array of qq integers where the value at each index ii (where 0iq0 \leq i \leq q) is 11 if a path exists from city originCitiesi\text{originCities}_i to city destinationCitiesi\text{destinationCities}_i; otherwise, it’s 00 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 00.

Sample Input 1 n=6n = 6 g=0g = 0 originCities=[1,4,3,6]\text{originCities} = [1,4,3,6] destinationCities=[3,6,2,5]\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 gcd(x,y)>g\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=6n = 6 g=1g = 1 originCities=[1,2,4,6]\text{originCities} = [1,2,4,6] destinationCities=[3,3,3,4]\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

Explanation of our first scenario
Explanation of our first scenario

What about Example #2?

Explanation 2

Explanation of our second scenario
Explanation of our second scenario

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!

Subscribe to know whenever I post new content. I don't spam!


At least this isn't a full screen popup

That would be more annoying. Anyways, if you like what you're reading, consider subscribing to my newsletter! I'll notify you when I publish new posts - no spam.