Abs india pvt. ltd. Interview Question
Computer ScientistsCountry: United States
Interview Type: Written Test
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
Assumption: One person can be connected to only one other person
- Shahnath December 01, 2014T(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)