Process Restricted Friend Requests

Hard

Asked by:

6 views

Topics:

ArraysGraphsDynamic Programming

You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n - 1.

You are also given a 0-indexed 2D integer array restrictions, where restrictions[i] = [x_i, y_i] means that person x_i and person y_i cannot become friends, either directly or indirectly through other people.

Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests, where requests[j] = [u_j, v_j] is a friend request between person u_j and person v_j.

A friend request is successful if u_j and v_j can be friends. Each friend request is processed in the given order (i.e., requests[j] occurs before requests[j + 1]), and upon a successful request, u_j and v_j become direct friends for all future friend requests.

Return a boolean array result, where each result[j] is true if the j^th friend request is successful or false if it is not.

Note: If u_j and v_j are already direct friends, the request is still successful.

Example 1:

Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
Output: [true,false]
Explanation:
Request 0: Person 0 and person 2 can be friends, so they become direct friends. 
Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).

Example 2:

Input: n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
Output: [true,false]
Explanation:
Request 0: Person 1 and person 2 can be friends, so they become direct friends.
Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).

Example 3:

Input: n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
Output: [true,false,true,false]
Explanation:
Request 0: Person 0 and person 4 can be friends, so they become direct friends.
Request 1: Person 1 and person 2 cannot be friends since they are directly restricted.
Request 2: Person 3 and person 1 can be friends, so they become direct friends.
Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).

Constraints:

2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= x_i, y_i <= n - 1
x_i != y_i
1 <= requests.length <= 1000
requests[j].length == 2
0 <= u_j, v_j <= n - 1
u_j != v_j

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the size constraints for the number of users and the number of restricted pairs and requests? Will they fit in memory?
Can a user request to become friends with themselves? Can a restricted pair involve the same user twice?
If a request violates multiple restrictions, should it still be processed if the restrictions are later removed? Or is it rejected outright?
Are user IDs guaranteed to be consecutive integers starting from 0 or 1? If not, what is the range of possible user IDs?
Is the graph of users guaranteed to be connected? If not, how should requests between unconnected components be handled?

Brute Force Solution

Approach

The brute force approach to processing friend requests involves checking each request individually to see if it violates any restrictions. If a request is allowed, it's processed. This continues until all requests have been examined.

Here's how the algorithm would work step-by-step:

Take the first friend request.
Check if making this friend connection violates any of the listed restrictions.
If it does violate a restriction, reject the request and move on to the next friend request.
If it does not violate any restrictions, approve the friend request, making the two people friends.
Move on to the next friend request and repeat the process.
Keep doing this until all the friend requests have been processed.

Code Implementation

def process_restricted_friend_requests(number_of_people, friend_requests, restrictions):
    are_friends = [False] * number_of_people
    friendships = set()
    result = []

    for request in friend_requests:
        person_a, person_b = request
        violates_restriction = False

        # Check if the current friend request violates any restrictions
        for restriction in restrictions:
            blocker, person_x, person_y = restriction
            if (person_a == person_x and person_b == person_y) or \
               (person_a == person_y and person_b == person_x):
                if are_friends[blocker]:
                    violates_restriction = True
                    break

        if violates_restriction:
            result.append(False)
        else:
            # Only add as friends if no restrictions are violated
            friendships.add(tuple(sorted((person_a, person_b))))
            are_friends[person_a] = True
            are_friends[person_b] = True
            result.append(True)

    return result

Big(O) Analysis

Time Complexity

O(n * m) – The algorithm iterates through each of the 'n' friend requests. For each friend request, it checks against all 'm' restrictions to see if the request violates any of them. Therefore, in the worst-case scenario, each of the 'n' friend requests requires examining all 'm' restrictions. This results in a time complexity of O(n * m).

Space Complexity

O(N) – The algorithm needs to maintain a record of which people are friends. Since the plain English description doesn't specify how friendship is tracked, we must consider the worst-case scenario where we use an adjacency matrix to represent the friend connections. An adjacency matrix for N people requires N x N space to store friendship relations. We can optimize this with a Union-Find data structure which takes O(N) space to store the parent pointers for each person. Thus the algorithm uses O(N) auxiliary space for the Union-Find data structure to keep track of connected components, where N is the number of people involved in the friend requests.

Optimal Solution

Approach

We need to process friend requests while respecting some restrictions, meaning certain friendships are not allowed. The efficient way is to check for conflicts *before* establishing a friendship, and only proceed if it's safe. This way, we avoid unnecessary steps and potential problems.

Here's how the algorithm would work step-by-step:

For each friend request, first, check if adding that friendship would violate any restrictions.
To check for violations, see if a direct restriction exists that forbids the requested friendship.
If a restriction exists that prevents the friendship, reject the request.
If there are no restrictions directly forbidding the friendship, then grant the friend request and establish the friendship.
Continue processing friend requests one at a time, always checking for restrictions before adding the friendship.

Code Implementation

def process_friend_requests(number_of_users, requests, restrictions):
    friendships = [[] for _ in range(number_of_users)]
    results = []

    for request in requests:
        user_id_1, user_id_2 = request[0], request[1]
        violation_found = False

        # Check if adding the friendship violates restrictions
        for restriction in restrictions:
            restricted_user_1, restricted_user_2 = restriction[0], restriction[1]
            if (user_id_1 == restricted_user_1 and user_id_2 == restricted_user_2) or \
               (user_id_1 == restricted_user_2 and user_id_2 == restricted_user_1):
                violation_found = True
                break

        if violation_found:
            results.append(False)
        else:
            # Only add friendship if no restriction is violated
            friendships[user_id_1].append(user_id_2)
            friendships[user_id_2].append(user_id_1)
            results.append(True)

    return results

Big(O) Analysis

Time Complexity

O(m*n) – Let n be the number of friend requests and m be the number of restrictions. For each of the n friend requests, the algorithm iterates through all m restrictions to check for potential violations. If there is no violation, the friendship is granted. Thus, for each friend request, we have to do at most m restriction checks. Therefore the total time complexity is proportional to m*n.

Space Complexity

O(1) – The provided explanation describes processing friend requests and checking for direct restrictions. It doesn't mention creating any auxiliary data structures like lists, sets, or hashmaps to store intermediate results or visited nodes. Therefore, the algorithm appears to use only a constant amount of extra space, likely for a few boolean flags or temporary variables to hold request information during the check. The space usage is independent of the number of friend requests or restrictions, denoted by N. Thus, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty friends list or no restrictions provided	If the friends list or the restrictions list is empty, all requests can be processed, so return a list of True values with the same length as the friend requests.
Friends and restrictions list have different lengths	Raise an error or return a specific error code because this indicates invalid input.
Cyclic restrictions exist (A restricts B, B restricts C, C restricts A)	Use a proper graph algorithm to check for cycles in the restriction graph to avoid infinite loops during processing.
Large number of friends and requests causing potential memory issues	Consider using generators or iterative approaches instead of recursion to reduce memory consumption for very large inputs.
Friend indices are out of bounds for the number of friends	Check if friend indices are within the valid range (0 to N-1, where N is the number of friends) and return False or throw an exception if invalid.
Restriction indices are out of bounds for the number of friends	Check restriction indices are within the valid range and return False or throw an exception if invalid.
Conflicting restrictions regarding the same pair of friends	Handle these conflicts by either prioritizing one restriction over another (e.g., based on order in the input list) or by flagging these requests as invalid.
Extremely large number of requests causing performance bottleneck	Optimize the restriction checking process using data structures like hash maps or sets to achieve faster lookups and improve the overall performance.

Empty friends list or no restrictions provided

How to Handle:

If the friends list or the restrictions list is empty, all requests can be processed, so return a list of True values with the same length as the friend requests.

Friends and restrictions list have different lengths

How to Handle:

Raise an error or return a specific error code because this indicates invalid input.

Cyclic restrictions exist (A restricts B, B restricts C, C restricts A)

How to Handle:

Use a proper graph algorithm to check for cycles in the restriction graph to avoid infinite loops during processing.

Large number of friends and requests causing potential memory issues

How to Handle:

Consider using generators or iterative approaches instead of recursion to reduce memory consumption for very large inputs.

Friend indices are out of bounds for the number of friends

How to Handle:

Check if friend indices are within the valid range (0 to N-1, where N is the number of friends) and return False or throw an exception if invalid.

Restriction indices are out of bounds for the number of friends

How to Handle:

Check restriction indices are within the valid range and return False or throw an exception if invalid.

Conflicting restrictions regarding the same pair of friends

How to Handle:

Handle these conflicts by either prioritizing one restriction over another (e.g., based on order in the input list) or by flagging these requests as invalid.

Extremely large number of requests causing performance bottleneck

How to Handle:

Optimize the restriction checking process using data structures like hash maps or sets to achieve faster lookups and improve the overall performance.