In this HackerRank Friend Circle Queries Interview preparation kit problem You will be given q queries. After each query, you need to report the size of the largest friend circle (the largest group of friends) formed after considering that query.


HackerRank Friend Circle Queries Interview preparation kit solution


Problem solution in Python programming.

#!/bin/python3

import math
import os
import random
import re
import sys

def init_cmp(mp,x,y):
    if x not in mp:
        mp[x]=x
    if y not in mp:
        mp[y]=y

def init_cc(cc,x,y):
    if x not in cc:
        cc[x]=1
    if y not in cc:
        cc[y]=1

def get_parent(mp,x):
    while mp[x]!=x:
        x=mp[x]
    return x

# Complete the maxCircle function below.
def maxCircle(queries):
    mp = {}
    cc = {}
    max_gp = 0
    res = []
    for q in queries:
        init_cmp(mp,q[0],q[1])
        init_cc(cc,q[0],q[1])
        p1 = get_parent(mp,q[0])
        p2 = get_parent(mp,q[1])
        if p1!=p2:
            if cc[p1]>cc[p2]:
                mp[p2]=p1
                cc[p1]=cc[p1]+cc[p2]
            else:
                mp[p1]=p2
                cc[p2]=cc[p1]+cc[p2]
            max_gp = max(max_gp,max(cc[p1],cc[p2]))
        res.append(max_gp)
    return res 

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(input())

    queries = []

    for _ in range(q):
        queries.append(list(map(int, input().rstrip().split())))

    ans = maxCircle(queries)

    fptr.write('\n'.join(map(str, ans)))
    fptr.write('\n')

    fptr.close()


Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {
    static class UnionFind {
        Map<Integer, Integer> parents;
        Map<Integer, Integer> sizes;
        int max;
        public UnionFind() {
            parents = new HashMap<>();
            sizes = new HashMap<>();
            max = 0;
        }
        
        public void union(int v1, int v2) {
            if (!parents.containsKey(v1)) {
                parents.put(v1, v1);
                sizes.put(v1, 1);
            }
            
            if (!parents.containsKey(v2)) {
                parents.put(v2, v2);
                sizes.put(v2, 1);
            }
            
            int p1 = find(v1), p2 = find(v2);
            if (p1 == p2) return;
            int s1 = sizes.get(p1), s2 = sizes.get(p2);
            if (s1 < s2) {
                parents.put(p1, p2);
                sizes.put(p2, s1 + s2);
                if (s1 + s2 > max) max = s1 + s2;
            }else {
                parents.put(p2, p1);
                sizes.put(p1, s1 + s2);
                if (s1 + s2 > max) max = s1 + s2;
            }
        }
        
        public int find(int v) {
            while (parents.get(v) != v) {
                parents.put(v, parents.get(parents.get(v)));
                v = parents.get(v);
            }
            return v;
        }
    }

    // Complete the maxCircle function below.
    static int[] maxCircle(int[][] queries) {
        UnionFind uf = new UnionFind();
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            uf.union(queries[i][0], queries[i][1]);
            res[i] = uf.max;
        }
        return res;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int q = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        int[][] queries = new int[q][2];

        for (int i = 0; i < q; i++) {
            String[] queriesRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int j = 0; j < 2; j++) {
                int queriesItem = Integer.parseInt(queriesRowItems[j]);
                queries[i][j] = queriesItem;
            }
        }

        int[] ans = maxCircle(queries);

        for (int i = 0; i < ans.length; i++) {
            bufferedWriter.write(String.valueOf(ans[i]));

            if (i != ans.length - 1) {
                bufferedWriter.write("\n");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}


Problem solution in C++ programming.

#include<bits/stdc++.h>
using namespace std;

const int MAX=500005;

int a[MAX], s[MAX];
set<int> sz;

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        a[i]=i;
        s[i]=1;
    }
}

int root(int x)
{
    while(a[x]!=x)
    {
        a[x]=a[a[x]];
        x=a[x];
    }
    return x;
}

void join(int x,int y)
{
    int rx=root(x);
    int ry=root(y);
    if(rx==ry)
        return;
    if(s[rx]>s[ry])
    {
        s[rx]+=s[ry];
        a[ry]=rx;
        sz.insert(-s[rx]);
    }
    else
    {
        s[ry]+=s[rx];
        a[rx]=ry;
        sz.insert(-s[ry]);
    }
}

int main()
{
    int q;
    vector<pair<int,int> > queries;
    map<int,int> m;
    vector<int> aux;

    scanf("%d",&q);
    
    for(int i=0;i<q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        queries.push_back(make_pair(x,y));
        aux.push_back(x);
        aux.push_back(y);
    }
    sort(aux.begin(),aux.end());
    int curr=1;
    for(int i=0;i<aux.size();i++)
    {
        if(i==0||aux[i]!=aux[i-1])
        {
            m[aux[i]]=curr++;
        }
    }
    for(int i=0;i<q;i++)
    {
        queries[i].first=m[queries[i].first];
        queries[i].second=m[queries[i].second];
    }

    init(curr);

    for(int i=0;i<q;i++)
    {
        join(queries[i].first,queries[i].second);
        printf("%d\n",-*(sz.begin()));
    }
    return 0;
}