Degrees of Friendship
Easy
We're building a new social network where users are friends with one another. In order to make better friend recommendations, we want to develop a "friend distance" algorithm.
Write a function friend_distance(friends, userA, userB) that returns the minimum distance between two users (similar to the "degree" of connection on LinkedIn).
The input to your function will be a 2D array friends, where each entry (A, B) contains the friendship status between user A and user B.
In the friends array, each user's friendships are represented by rows, and each column represents a user. For example, if friends[0][1] is 1, it means that user 0 is friends with user 1. Similarly, if friends[1][2] is 1, it indicates that user 1 is friends with user 2.
Pythondef friend_distance(friends, userA, userB):
# Your code here...
Examples
In this example, users 0 and 1 are friends, so the entries (0, 1) and (1, 0) are both 1. Users 1 and 2 are also friends, so entries (1, 2) and (2, 1) are also 1. Since they are direct friends, their friend distance is 1. Users 0 and 2 are not friends but are both connected to User 1, so their friend distance is 2.
Pythonfriends = [[0 1 0], [1 0 1], [0 1 0]] friend_distance(friends, 0, 1) # => 1 friend_distance(friends, 1, 2) # => 1 friend_distance(friends, 0, 2) # => 2
Return -1 if there are no connections between the users.
We use Breadth-First Search (BFS) to find the shortest path between two users in an unweighted social network graph. BFS is particularly effective for this task because it explores all nodes at the present "depth" (or distance) before moving on to nodes at the next depth level. This ensures that the first time we reach the target node, we have found the shortest path.
The algorithm follows these steps:
-
Initialization:
- Check if
userAis the same asuserB. If they are, the distance is0. - Initialize a queue for BFS that stores tuples of the current node and the current distance from
userA. - Create a set to keep track of visited nodes to prevent reprocessing the same node.
- Check if
-
BFS Execution:
- While the queue is not empty, dequeue the first element to get the current node and its associated distance.
- If the current node has already been visited, skip it.
- Mark the current node as visited.
- Check if the current node is directly connected to
userB. If it is, return the distance incremented by 1. - Otherwise, enqueue all unvisited neighbors of the current node with their distances incremented by 1.
-
Termination:
- If the queue is exhausted without finding
userB, return-1indicating there is no path betweenuserAanduserB.
- If the queue is exhausted without finding
Time Complexity: The time complexity of this algorithm is O(V + E), where V is the number of users (nodes) and E is the number of connections (edges) in the social network graph. This is because, in the worst case, we may need to visit all nodes and edges.
Space Complexity: The space complexity is O(V) because, in the worst case, we might need to store all nodes in the queue and the visited set. This ensures that our approach remains efficient even for larger graphs.
Related courses
