As the final question in one of my interviews a while ago, I was asked to compute the average degrees of separation in social networking site. If you don’t know what degree of separation, here’s an example.

Amy is a friend of Robert. Therefore, Amy and Robert are 1st degree friend. Robert is a friend of James. Therefore, Amy and James are 2nd degree friend through their common friend Robert. Below is a small example of 5 people identified by number 0 – 4.

A ←→ D
A ←→ C
B ←→ D
B ←→ E
B ←→ C
C ←→ E
C ←→ D

In the above case, A and D are separated by one degree. A and E are separated by 2 degree since they are both friends of C. A and E can also be connected through A ←→ D ←→ B ←→ E for 3 degreees separation. However, we want to know the closest separation. Now calculating all the relationship degree on the above example, the average degree of separation is 1.3. Consult the table below and add the numbers, you’ll end up with 13. There are 10 connections. So average is 1.3. Actually, if you add the numbers, it adds up to 26 for 20 connections for the same average of 1.3. However, if you calculate all the numbers, you’ll be double counting as you’re counting the degree of A ←→ B and B ←→ A.

Ok now that the stage is set, find the average degree of separation on the following user data. The user is identified by user 0 to 99.

Once again, the question is, what is the average degree of separation on the social network relationship on the above table? Well, try to work on it first … then go to page 2 for one possible solution.