## Practo Interview Question for SDE1s

Country: India
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public class Rods {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int res;
int n;
n = Integer.parseInt(in.nextLine());

int pairsCount = 0;
pairsCount = Integer.parseInt(in.nextLine());
String[] pairs = new String[pairsCount];
String pair;
for (int i = 0; i < pairsCount; i++) {
pair = in.nextLine();
pairs[i] = pair;
}

res = calcCost(n, pairs);
System.out.println(res);
}

private static int calcCost(int n, String[] pairs) {
int[] rank, parent, count;
rank = new int[n + 1];
parent = new int[n + 1];
count = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
count[i] = 1;
}
for (String pair : pairs) {
String[] xy = pair.split(" ");
int x = Integer.parseInt(xy[0]);
int y = Integer.parseInt(xy[1]);
union(x, y, parent, rank, count);
}
int res = 0;
for (int z : count) {
if (z > 1) {
res += (int) Math.ceil(Math.sqrt(z));
} else {
res += z;
}
}
return res;
}

private static int find(int x, int[] parent) {
if (parent[x] != x) {
parent[x] = find(parent[x], parent);
}
return parent[x];
}

private static void union(int x, int y, int[] parent, int[] rank,
int[] count) {
int xRoot = find(x, parent), yRoot = find(y, parent);
if (xRoot == yRoot)
return;
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
count[yRoot] += count[xRoot];
count[xRoot] = 0;
} else if (rank[yRoot] < rank[xRoot]) {
parent[yRoot] = xRoot;
count[xRoot] += count[yRoot];
count[yRoot] = 0;
} else {
parent[yRoot] = xRoot;
count[xRoot] += count[yRoot];
count[yRoot] = 0;
rank[xRoot] = rank[xRoot] + 1;
}
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Didn't get the meaning of the question. could you explain more?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find all connected rods using union find algorithm of disjoint set. Determine the cost accordingly.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import math

class Data(object):
def __init__(self, name):
self.__name = name

@property
def name(self):
return self.__name

@property

# The function to look for connected components.

def connected_components(nodes):
# List of connected components found. The order is random.
result = []

# Make a copy of the set, so we can modify it.
nodes = set(nodes)

# Iterate while we still have nodes to process.
while nodes:

# Get a random node and remove it from the global set.
n = nodes.pop()

# This set will contain the next group of nodes connected to each other.
group = {n}

# Build a queue with this node in it.
queue = [n]

# Iterate the queue.
# When it's empty, we finished visiting a group of connected nodes.
while queue:
# Consume the next item from the queue.
n = queue.pop(0)

# Fetch the neighbors.

# Remove the neighbors we already visited.
neighbors.difference_update(group)

# Remove the remaining nodes from the global set.
nodes.difference_update(neighbors)

# Add them to the group of connected nodes.
group.update(neighbors)

# Add them to the queue, so we visit them in the next iterations.
queue.extend(neighbors)

# Add the group to the list of groups.
result.append(group)

# Return the list of groups.
return result

# The test code...

def minimalCost(n, pairs):
nodes_map = {x: Data(x) for x in xrange(1, n + 1)}

for pair in pairs:
p, q = int(pair.split(' ')[0]), int(pair.split(' ')[1])

# Find all the connected components.
cost = 0
for components in connected_components(nodes_map.values()):
# names = sorted(node.name for node in components)
# print names
cost += math.ceil(math.sqrt(len(components)))
return long(cost)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <bits/stdc++.h>
using namespace std;
void bfs(vector<vector<int>> &graph,vector<int> &visited,int source)
{
queue<int> q;
q.push(source);
visited[source]=source;
while(!q.empty())
{
int curr=q.front();
q.pop();
for(int i=0;i<graph[curr].size();i++)
{
if(visited[graph[curr][i]]==-1)
{
q.push(graph[curr][i]);
visited[graph[curr][i]]=source;
}
}
}
}

int main() {
int n,m;
cin>>n;
cin>>m;
vector<vector<int>> graph(n);
for(int i=0;i<m;i++)
{
int x,y;
cin>>x;
cin>>y;
x--;
y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
int result=0;
vector<int> visited(n,-1);
for(int i=0;i<n;i++)
{
if(visited[i]==-1)
{
bfs(graph,visited,i);
int count=0;
for(int j=0;j<n;j++)
{
if(visited[j]==i)
{
count++;
}
}
result+=ceil(sqrt(count));
}
}
cout<<result<<endl;
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <bits/stdc++.h>
using namespace std;
void bfs(vector<vector<int>> &graph,vector<int> &visited,int source)
{
queue<int> q;
q.push(source);
visited[source]=source;
while(!q.empty())
{
int curr=q.front();
q.pop();
for(int i=0;i<graph[curr].size();i++)
{
if(visited[graph[curr][i]]==-1)
{
q.push(graph[curr][i]);
visited[graph[curr][i]]=source;
}
}
}
}

int main() {
int n,m;
cin>>n;
cin>>m;
vector<vector<int>> graph(n);
for(int i=0;i<m;i++)
{
int x,y;
cin>>x;
cin>>y;
x--;
y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
int result=0;
vector<int> visited(n,-1);
for(int i=0;i<n;i++)
{
if(visited[i]==-1)
{
bfs(graph,visited,i);
int count=0;
for(int j=0;j<n;j++)
{
if(visited[j]==i)
{
count++;
}
}
result+=ceil(sqrt(count));
}
}
cout<<result<<endl;
return 0;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.