Degrees of Friendship
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.
You could represent this problem with a graph. How do you find the shortest path in a graph?
You can start with userA and use breadth-first search (BFS) to find users of increasing distances.
BFS can be implemented using a queue and a loop.
Make sure not to re-visit the same users or you could end up in an infinite cycle.
What happens if there are multiple 'paths' between the users? Does your function follow the shorter one?
What does your function return when userA == userB?
What does your function return if there is no connection?
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
from collections import deque
def friend_distance(friends, userA, userB):
"""Returns the distance between userA and userB"""
if userA == userB:
return 0
# Create a queue and list of visited users
visited = {}
queue = deque([(userA, 1)]) # (node, distance)
# Iterate through the queue until it is empty
while len(queue) > 0:
curr_node, distance = queue.popleft()
# Skip this user if we've already visited
if curr_node in visited: continue
visited[curr_node] = True
# If this user is friends with userB, return
if friends[curr_node][userB]:
return distance
# Enqueue new friends with increased distance
for i in range(len(friends)):
if friends[curr_node][i]:
queue.append((i, distance + 1))
return -1Time 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.
The time and space complexity of BFS is O(V + E) and O(V) respectively, where V is the number of nodes and E is the number of edges.
def friend_distance(friends, userA, userB): step = 0 total_neighs = set() llen = len(total_neighs) total_neighs.add(userB) while len(total_neighs)!=llen: s = set() step += 1 llen = len(total_neighs) for el in total_neighs: nes = neighbours(friends, userA, el) if userA in nes: return step for p in nes: s.add(p) for el in s: total_neighs.add(el) return -1
def neighbours(A,n1, n2): out = set() for i in range(len(A[n2])): if A[n2][i]: out.add(i) return out