Feature #1: Friend Circles
Explore how to identify all friend circles on Facebook by representing user friendships as connected components in a graph. Learn to apply depth-first search on an adjacency matrix to count these groups and understand the algorithm's time and space complexity.
We'll cover the following...
Description
First, we need to find all the people that are in each user’s friends circle on Facebook. Your individual friend circle is defined as a group of users who are directly or indirectly friends with you. Assume there are a total of n users on Facebook. Some of them are your friends and others are not. The friendship/connection is transitive in nature. For example, if Shaw is a direct friend of Andy, and Andy is a direct friend of Noah, then Shaw is an indirect friend of Noah. Getting the total number of friend circles that exist on Facebook helps us suggest connections on Instagram for every user.
We’ll be provided with an n x n square matrix, where n is the number of users on Facebook. A cell [i,j] will hold the value 1 if user i and user j are friends. Otherwise, the cell will hold the value 0. For example, consider the input: ...
There are two friend ...