Friend Recommendation System - Expedia Online Assessment IIT Roorkee

Problem Preview

"Given `n` users numbered `0` to `n - 1` and an array `friendships` where `[u, v]` represents an undirected friendship, recommend exactly one new friend for every user. ### Rules For each user: * The recommended user must **not** already be a direct friend. * The recommended user must **not** be the user themselves. * Choose the user with the **maximum number of mutual friends**. * If multiple users tie, choose the user with the **lowest ID**. * If no valid candidate has at least **1 mutual friend**, return `-1`. Return an array `recommendations` where `recommendations[i]` is the recommended friend for user `i`. ### Constraints ```text 1 <= n <= 10^5 0 <= friendships.length <= 2 * 10^5 friendships[i].length == 2 0 <= u, v < n u != v No duplicate friendships ``` ### Example **Input:** ```text n = 5 friendships = [[0,1], [0,2], [1,3], [2,3], [3,4]] ``` **Output:** ```text [3, 2, 1, 0, 1] ``` ### Explanation ```text User 0 → User 3 Mutual friends = {1, 2} → 2 mutual friends User 1 → User 2 Mutual friends = {0, 3} → 2 mutual friends User 2 → User 1 Mutual friends = {0, 3} → 2 mutual friends User 3 → User 0 Mutual friends = {1, 2} → 2 mutual friends User 4 → User 1 User 1 and User 2 both have 1 mutual friend. Choose the lower ID → User 1. ``` **Expected result:** ```text [3, 2, 1, 0, 1] ```"