unknown Interview Question for Software Developers
- 0of 0 votes
AnswersConsider a social website SocialX, where friends connect to each other, just as they do on Facebook
- Abhishek.Mathur.CA September 30, 2016 in United States
Friendship on SocialX is symmetric (if X is a friend of Z, then Z is also a friend of X) however not transient (if X and Z are friends and Z and Y are friends, then X and Y are not necessarily friends)
The term "k-joined" is defined as follows. If two people are friends, they are called 1-joined. For k >= 1, two people X and Z are called (k+1)-joined if X and Z are k-joined, or if there exists a person Y such that X and Y are k-joined and Y and Z are friends.
"Approachable Score" is defined as follows. If two people X and Z are not friends, then their Approachable Score is the fewest number of people (other than themselves) who must be removed from the network in order for X and Z to not be 3-joined. The higher the Approachable Score, the more likely it is that X and Z know each other.
Given a set of friends containing exactly K elements, where K is the number of people in the network. People are numbered from 0 to K-1. The j-th character of the i-th element of friends is '1' if i and j are friends, and '0' otherwise. Return the Approachable Score for personX and personZ
Constraints
Set of friends will contain exactly K (1 < K < 41) elements, where each element will contain exactly K characters. Each character will either be '0' or '1'
friends[i][j] will always be equal to friends[j][i] and friends[i][i] will always be equal to 0
friend[personX][personZ] will be equal to 0 and personX will never be equal to personZ
Input Format
Line 1: comma separated K elements representing friends
Line 2: Integer representing personX
Line 3: Integer representing personZ
Output Format
Integer representing Approachable Score
Sample Input
0100,1010,0101,0010
0
3
Sample Output
1
Explanation
Either remove person 1 or person 2 to get an Approachable Score of 1 for person 0 and 3| Report Duplicate | Flag | PURGE
unknown Software Developer