Practo Interview Question for SDE1s
- 0of 0 votes
AnswersStrong relation group
- rayasamharish October 04, 2015 in India
A group of social network experts are searching for an algorithm to find
"Strong relation groups" among people. A group of people form a strong
relation group if each of them know everyone else in the group. The
problem seemed very tough to them, so they want to attack a smaller
problem. If there are n people in a network and there are m pairs of
relationship among them, what will be the minimum size of the largest
"Strong relation group" in the network? If you know about graphs, you
can think of people as nodes and their relationship as edges.
Parameters:
Complete a function strongRelation which takes two integers n and m
as parameters.
Input Format:
First line contains a single integer denoting N.
Second line contains a single integer denoting M.
Return value:
Return the answer to the problem.
Constraints
1 <= T <= 100000
2 <= N <= 10000
1 <= M <= N*(N-1)/2
Sample Input:
3
2
Sample Output 1:
2
Sample input 2:
4
6
Sample Output 2:
4
Sample input 3:
5
7
Sample Output 3:
3
Explanation
1
2
3
4
5
"Strong relation group" cannot be smaller than 4.
For the third sample, it is easy to verify that any graph with 5 nodes and
7 edges will surely have a "Strong relation groups" of size 3 or more| Report Duplicate | Flag | PURGE
Practo SDE1
Interview Type: Written Test
- Anonymous April 11, 2016