Question

Microsoft | OA Coding Questions and Solutions | Set - 40 | 2022

Answer 1

Images Of Ques

Answer 2

Simple application of UnionFind.

 

Time: O(N^2) where N is the number of Landmarks connections. Union requires O(N) to connect the components.
Space: O(N)

 

 

 

public (int, int) MaximumNumberOfLandmarks(int N, int[][] connectedRoads)
{
	// N = total number of landmarks
	// Test case:
	// N=10, cr=[[1,2],[2,3],[3,4],[4,5],[6,7],[9,10]]

	// Islands
	// 1: 1,2,3,4,5
	// 2: 6,7
	// 3: 9,10

	var landMarks = connectedRoads.SelectMany(r => r).Distinct();

	var unionFind = new UnionFind<int>(landMarks);
    foreach (var road in connectedRoads)
    {
		unionFind.Union(road[0], road[1]);
    }

	var largestComponentSize = int.MinValue;
	foreach (var landMark in landMarks)
	{
		var parentComponent = unionFind.Find(landMark);
		largestComponentSize =
			Math.Max(largestComponentSize, unionFind.sizes[parentComponent]);
	}

	return (largestComponentSize, NthPrime(largestComponentSize));
}

const int MaxPrime = 100000;
public int NthPrime(int n)
{
	var sievesMap = new bool[MaxPrime];
	for (var i = 2; i * i < MaxPrime; i++)
    {
		if (sievesMap[i])
			continue;

        for (int j = i*i; j < MaxPrime; j += i)
			sievesMap[j] = true;
    }

	int k, count = 0;
    for (k = 2; k < MaxPrime && count < n; k++)
    {
		if (!sievesMap[k])
			count++;
    }

	return k - 1;
}

// Runner
var res1 = sol.MaximumNumberOfLandmarks(10, new int[][] {
    new int[2]{ 1, 2 },
    new int[2]{ 2, 3 },
    new int[2]{ 3, 4 },
    new int[2]{ 4, 5 },
    new int[2]{ 6, 7 },
    new int[2]{ 9, 10 },
});
Debug.Assert(res1.Item1 == 5);
Debug.Assert(res1.Item2 == 11);