Microsoft Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Do we need BFS? here is just to find the distance of 2. For two persons A and B, i think we can just check A and B's friend lists and find if there are shared friends or not.
I don't quite understand the last question. if we just define the most influential person has the highest weight (the sum of weights from each connected edge), then this most influential person can be simply found by finding the largest summed weight?
@zyfo2 : yes BFS is good for first question only, what about others
@lxduan :
consider the case when you have two people having equal number of edge connectivity, and there total weight sum are equal, does it mean that they are equally influential person, what if one person (out of two) is connected with the persons having more edge connectivity, and another person connected with persons having less edge connectivity,
for example A, B are two person
A connected with A1 and A2
B connected with B1 and B2
weight(A1) + weight(A2) = weight(B1) + weight(B2)
but A1 and A2 are connected with 10, 15 other people, and B1 and B2 are connected with 5 , 6 other people, then according to you both A and B are same influential person but they are not, actually A is more influential person then B, now to tell us your solution ?
I think a simple Depth Bounded Search (BFS or DFS) should suffice for the 1st part.
If I understand the 2nd part correctly, we have to find the connectivity between 2 persons such that the people with most weight are included in the path. We can inverse the weights and then find the shortest weighted path using Dijstra's Algo.
For the 3rd question,
Maintain a variable which keeps track of the max. value of weight while doing part2.
OR my understanding of the question is wrong :D
second solution is not correct, and for 3rd question please read my comment to "lxduan"
1. best possible connections could be identified as sum of weights of all paths (connections) form a candidate person to the target person divided by number of paths.
a default weight of an edge may be assumed as one in this case, so for example- if a candidate vertices (person) is 2 vertices (person) away from target vertice then the sum of that connection is 2.
2. people with weight reduce the sum of each edge connected to them by a factor of their weights, ideally this would be a factor of weights of both sides of a given edge
3. influence of a person could be a function of sum strength of each connection (which may a function of frequency of contact, number of shared friends, duration of connection etc)
Hey..How many yrs of experience u have??
I am only 2 yrs experienced...and i kind of find these question difficult..do they ask this level of questions from 2 yrs exp also?
is BFS good?
- zyfo2 January 04, 2013