## 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

**Country:**India

**Interview Type:**Written Test

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

- Anonymous April 11, 2016