## Abs india pvt. ltd. Interview Question for Computer Scientists

• 0

Country: United States
Interview Type: Written Test

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

Assumption: One person can be connected to only one other person

T(n): Number of ways n people can be connected

If we fixed a person X from a group of n person, then the other (n-1) person (except X) can be connected in T(n-1) ways where X is not connected to any person.

If X become connected to any person of the group of (n-1) persons, then rest (n-2) person can be connected in T(n-2) ways. And there are (n-1) ways that X can be connected to any person of the group of (n-1) persons. So, there is (n-1)T(n-2) ways where X is connected.

So, T(n) is the sum of above two parts. i.e.
T(n) = T(n-1) + (n-1)T(n-2)

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

Is that true that for this problem we make an assumption that one person may be connected to only one other person? I see it from examples but not from statement of the problem.

Because of that we have (n-1)*T(n-2) as second part
T(n) is actually factorial, isn't it? I see the thing behind it like we get all connections without new person {T(n-1)} and also get additional connections as they were with previous person {T(n-2)} connections for any other person {(n-1)} with new person
We can show it like that :

``````T(0) = {}

T(1) = {} //T(0) + 1st person

T(2) =
{},         //T(1)
{(1,2)} //T(0) + 2nd person

T(3) =
{}, {(1,2)}, //T(2)
{(1,3)}, //(T(1) for 1st person) + 3rd person
{(2,3)}  //(T(1) for 2nd person) + 3rd person

T(4) =
{}, {(1,2)}, {(1,3)}, {(2,3)}, //T(3)
{(1,4)}, {(1,4), (2,3)}, //(T(2) for 1st person) + 4th person
{(2,4)}, {(2,4), (1,3)}, //(T(2) for 2nd person) + 4th person
{(3,4)}, {(3,4), (1,2)}  //(T(2) for 3rd person) + 4th person``````

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

T(n) is a recursive function ...

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

T(n) is a function that is used in combination? because it is pretty obvious from the question that it is recursive (it is calling himself -1 and -2...) so I am not sure that I understood what you mean.

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.