Friend Circle. Photo by Margarida CSilva on Unsplash
Lately I’ve been trying to challenge myself by taking a stab at some common coding questions asked in software engineering job interviews. After years of working on apps you would think that this kind of thing comes easy, but software development in the modern age comes with a heavy side of Googling and lookup, so challenging your brain in this way to implement an algorithm or process from just its definition or description is good practice to keep you sharp.
Yesterday, I came across a question on LeetCode that asked me to find the total number of friend circles given an N by N
matrix
showing their relationships. Here is how I implemented a solution in ruby:
The exact working of the question looks like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

In short, we have a matrix where each row of index i
represents a different student, and each column of index j
within that row represents a friendship with the student at i
.
Because you are always your own best friend, any row on the identity diagonal where i == j
will be 1
. The rest can be either a 0
or a 1
, with a 1 representing a friendship
between i
and j
. A friend circle is defined as containing anybody who is a friend, or a friendofafriend. We are interested in finding how many friend circles are present within the matrix.
My initial thoughts on how to approach this was to write out some pseudocode:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 

This is basically a BreadthFirst Search for each friend. As we come across new nodes on the friendship tree, we add them to the current circle and remove the friendship.
When a circle is completed, we keep the process going starting with the next friendship. This next friendship will not have any friends within the first circle, otherwise they would have been found
on the BFS. Thus, this new BFS will be a completely new friend circle. Finally, we keep on going, discovering new circles, until all of the friendships have been exhausted (all 0
in the matrix).
When starting with the code, I realized that I would need a helper method to determine whether or not the matrix had any friendships left, and if so, what student index i
was the first one found?
1 2 3 4 5 6 7 8 9 10 

We are told the input will always be a N by N
matrix of arrays, with 1 <= N <= 200
so there is no need for empty or nil
checks here. Now lets get started on some framework code
for the main method.
1 2 3 4 5 6 7 8 9 10 11 12 

Running this asis would obviously get stuck in the while
loop forever, but shows how we will keep track of the friend circles overall, iterate over the matrix of friendships until there are none, then return the number of circles found.
Let’s get into the while
loop:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

Running this asis would still get stuck in a while
loop forever, but shows that once we know we have friendships and know the first friend that has a friendship, we can use that to create a stack
for us to start a BFS, keeping track of the found friends along the way inside of circles
. When the stack is exhausted, our circle
is complete, so we can add it to the overall circles
collection,
and setup the has_friendships
variable for the outer while
loop. Let’s get into the inner while
loop, the BFS:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 

Inside the inner while
loop, we first pop a friend off the stack
, then iterate over all of that persons friends. At each person_j
, if the relationship is a friendship (== 1
),
then we add it to the circle
to denote that this person_j
is a friend or a friendofafriend of everyone there, and we also add this person_j
to the stack to find their friends. Of course,
we only want to add the friend person_j
if we haven’t already seen them before, so we check to see if the circle
already includes person_j
before doing so. Finally, we make sure that we mark this friendship
as visited by making sure it is covered by a 0
in the friendship matrix.
This passes all LeetCode tests, but is not crazy fast:
1 2 

It’s been awhile since I did any matrix manipulations in a computer science math class, but I seem to recall there were various tricks you could use to traverse a matrix and perform operations on them that are faster than iterations like I have done. This would probably speed things up. I could reduce memory usage by not storing the circles themselves, but just the counts, as I am never required to return the friend circles with members inside. I could probably go faster by deleting rows and columns of a student after processing them, so the overall matrix would get smaller and smaller as I go along. This would increase speed as well. I’ll save all these potential optimizations for another day.