💡 Problem Formulation: In the context of social networks, finding mutual followers can be a common task. Given a list of user relationships where each relationship is a tuple of (follower, followee), the problem is to identify all pairs of users who are following each other mutually. For example, if our input is [("alice","bob"),("bob","alice"),("alice","charlie")], the desired output should be [("alice","bob"),("bob","alice")].
Method 1: Using Nested Loops
This method involves iterating over the relations list with nested loops to check for mutual relationships. Although it is straightforward, it has a quadratic complexity O(n^2), which makes it less efficient for large datasets.
Here’s an example:
def find_mutual_followers(relations):
mutuals = []
for follower, followee in relations:
if (followee, follower) in relations:
mutuals.append((follower, followee))
return mutuals
relations = [("alice","bob"),("bob","alice"),("alice","charlie")]
mutual_followers = find_mutual_followers(relations)
print(mutual_followers)
Output: [('alice', 'bob'), ('bob', 'alice')]
This code snippet defines a function find_mutual_followers() that takes a list of relation tuples and returns a list of mutual follower pairs. It uses a nested loop to check if the inverse relationship exists for each tuple in the list. If a mutual relationship is found, it is appended to the mutuals list.
Method 2: Using Set Operations
With set operations, we can improve efficiency. By converting the list of relations to a set, we can perform intersection operations, which are much faster than nested loops, especially on larger data sets with O(n) complexity on average.
Here’s an example:
def find_mutual_followers_set(relations):
relations_set = set(relations)
mutuals = set()
for follower, followee in relations_set:
if (followee, follower) in relations_set:
mutuals.add((follower, followee))
return mutuals
relations = [("alice","bob"),("bob","alice"),("alice","charlie")]
mutual_followers = find_mutual_followers_set(relations)
print(mutual_followers)
Output: {('alice', 'bob'), ('bob', 'alice')}
This code example uses a set to keep track of the relations, enabling the use of set operations to find mutual pairs with better performance. The find_mutual_followers_set() function performs intersection checks in the relations set to locate mutual follower pairs more efficiently.
Method 3: Using Dictionary for Lookup
This method uses a dictionary to track followers for each user, allowing for constant time lookups. It’s efficient and suitable for larger data sets where the reduction in lookup time can significantly decrease overall execution time.
Here’s an example:
def find_mutual_followers_dict(relations):
followers_dict = {}
mutuals = []
for follower, followee in relations:
followers_dict.setdefault(followee, set()).add(follower)
for follower, followee in relations:
if follower in followers_dict.get(followee, set()):
mutuals.append((follower, followee))
return mutuals
relations = [("alice","bob"),("bob","alice"),("alice","charlie")]
mutual_followers = find_mutual_followers_dict(relations)
print(mutual_followers)
Output: [('alice', 'bob'), ('bob', 'alice')]
In this example, find_mutual_followers_dict() creates a dictionary that maps each user to their followers, allowing O(1) lookup time when checking for mutual relationships. The result is a list of tuples with mutual followers.
Method 4: Using List Comprehension
Python’s list comprehensions offer a concise way to express the algorithm for finding mutual followers in a single line of code. However, this method still represents a nested loop under the hood.
Here’s an example:
relations = [("alice","bob"),("bob","alice"),("alice","charlie")]
mutual_followers = [(follower, followee) for follower, followee in relations if (followee, follower) in relations]
print(mutual_followers)
Output: [('alice', 'bob'), ('bob', 'alice')]
The example uses list comprehension to perform the same task as the nested loops from Method 1 but in a more succinct way. The if-condition within the comprehension checks for mutual following, yielding a list of mutual relationships.
Bonus One-Liner Method 5: Using Set Intersection
We can succinctly find mutual relationships by leveraging the intersection operation between two sets in a one-liner code snippet.
Here’s an example:
relations = [("alice","bob"),("bob","alice"),("alice","charlie")]
mutual_followers = list(set(relations).intersection((followee, follower) for follower, followee in relations))
print(mutual_followers)
Output: [('bob', 'alice'), ('alice', 'bob')]
The code snippet performs a set intersection between the relations and a generator expression that swaps the tuple elements, effectively giving us a set of mutual relationships. This set is then converted to a list for the final output.
Summary/Discussion
- Method 1: Nested Loops. Simple and straightforward. Inefficient for large datasets due to O(n^2) complexity.
- Method 2: Sets. Much faster on average using O(n) complexity. May consume slightly more memory.
- Method 3: Dictionary for Lookup. Provides fast lookups with O(1) complexity on average. Ideal for large datasets; however, initialization may take longer for very large sets.
- Method 4: List Comprehension. Concise expression of method 1. Still suffers from O(n^2) complexity under the hood.
- Method 5: Set Intersection One-Liner. Extremely concise and expressive. Efficient if relation list is not extremely large since it still relies on generating a set from a list.