National Instruments Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
I am not sure I understand the problem that well but hopefully this more general solution should cover some of the parts I don’t quite get.
If all Robots are unique choose one of the N and then chose one of the remaining N-1 robots
So you get n*(n-1) possible sets of 2
If there is a set of size M you could make up M*(M-1) pares with just the robots in this set.
So given N robots and an list of sets M[0]…. M[P] you have:
n*(n-1) - sum M[i]*(M[i] -1)
It should be 4* nC2, where n= number of pairs formed. In the example given n=3 (3 pairs...(4,2),(0,1),(2,3). There is a problem here though. If 4 and 2 are same type and 2,3 are same type then 4,2,3 are all same type. that should not be the case. Let's replace 2,3 with 5,3. Then the solution which I have proposed is correct.
/*
Name
Brief description of algorithm :
*/
#include <iostream>
#define MAXN 100000
#define MAXP 100000
using namespace std;
typedef unsigned long ulong;
ulong CountNoOfWays(ulong N, ulong P, ulong pairs[][2])
{
ulong combi=0;
ulong count=0,sum=0,x=0,count1=0;
ulong check[N];
for (int i=0;i<N;i++)
{
check[i]=0;
}
for (int i=0;i<P;i++)
{
if(check[pairs[i][0]]!=0||check[pairs[i][1]]!=0)
{
if(check[pairs[i][0]]!=0)
{
check[pairs[i][1]]=check[pairs[i][0]];
}
if(check[pairs[i][1]]!=0)
{
check[pairs[i][0]]=check[pairs[i][1]];
}
}
if(check[pairs[i][0]]==0 && check[pairs[i][1]]==0)
{
count++;
check[pairs[i][0]]=count;
check[pairs[i][1]]=count;
}
}
/*
for (int i=0;i<N;i++)
{
cout<<check[i]<<" ";
}
cout<<endl;
*/
for (int i=0;i<N;i++)
{
if(check[i]>0)
count1++;
}
ulong max=check[0];
for (int i=1;i<N;i++)
{
if(max<check[i])
max=check[i];
}
ulong headache[max+1];
for (int i=0;i<=max;i++)
{
headache[i]=0;
}
for (int i=0;i<N;i++)
{
if(check[i]>0)
headache[check[i]]++;
}
/*
for (int i=0;i<=max;i++)
{
cout<<headache[i]<<" ";
}
cout<<endl;
*/
ulong result=1;
for (int i=0;i<=max;i++)
{
if(headache[i]>0)
result=result*headache[i];
}
// cout<<result<<endl;
x=N-count1;
sum=x*count1;
sum=sum+(x*(x-1)/2);
combi=combi+sum+result;
return combi;
}
int main()
{
ulong N, P;
cin >> N >> P;
ulong pairs[MAXP][2];
for(ulong i = 0; i < P; i++)
{
cin >> pairs[i][0] >> pairs[i][1];
}
cout << CountNoOfWays(N, P, pairs);
}
/*
10 4
2 8
1 3
0 2
5 8
2,5,8,0 in one group
1,3 in another
(2,1)(2,3)(2,5)(8,1)(8,3)(8,0)(1,0)(1,5)(3,0)(3,5)(0,5)
1 2 3 4 5 6 7 8 9
*/
using System;
using System.Collections.Generic;
namespace Test
{
class Graph
{
int V; //Vertices of the graph
public int no_nodes = 0;
List<int>[] adj_node; //adjacent node fof each vertices
Graph(int V) // Constructor
{
this.V = V;
adj_node = new List<int>[V];
for (int i = 0; i < V; i++)
{
adj_node[i] = new List<int>();
}
}
void AddEdge(int x, int y)
{
adj_node[x].Add(y);
adj_node[y].Add(x);
}
void dfs(int a, bool[] vis)
{
vis[a] = true;
no_nodes++;
//Console.WriteLine(" " + a);
foreach (int x in adj_node[a])
{
if (!vis[x])
{
dfs(x, vis);
}
}
}
void Connection()
{
bool[] vis = new bool[V];
List<int> nodes = new List<int>();
for (int v = 0; v < V; v++)
{
if (!vis[v])
{
no_nodes = 0;
dfs(v, vis);
nodes.Add(no_nodes);
}
}
List<int> ans = new List<int>();
while(nodes.Count > 0)
{
int sum = 0;
for (int i = 1; i < nodes.Count; i++)
{
sum = sum + nodes[i];
}
ans.Add(nodes[0] * sum);
nodes.RemoveAt(0);
}
int res = 0;
foreach(int y in ans)
{
res = res + y;
}
Console.WriteLine(res);
}
public static void Main(String[] args)
{
Graph g = new Graph(4);
g.AddEdge(0, 1);
g.AddEdge(2, 3);
g.Connection();
Console.ReadLine();
}
}
}
The number of ways to select 2 robots such that both belong to separate models are:
- ashu1.220791 July 03, 2015pC2 * 2 * 2 + pC1 * 2 * (n-2p)C1 + (n-2p)C2
if n is total number of bots and p are distinct pairs.