Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
We could use Graph Transitive closure property. Which says if A is friends with B and B is friends with C, then A is friends with C. C would be our suggestion to the user. We can come u with a Connection Adjecency Matrix which can be written as
Connec[i][j] = Connection[i][j] | (Connect[i][k] && Connect[k][j])
For a user I we can suggest all the connections J which are already not in its list.
Fixed indention in above post!
Class Person {
string name;
string id;
list <School*> schools;
list<Company*> companies;
list<Person*> friends;
list<Location*> places;
}
list<Person*> FacebookSuggest(Person *p) {
list<Person*> suggestedFriends;
list<Person*> visitedFriends;
list<Person*> toVisit;
toVisit.push_back(p);
while (!toVisit.isEmpty() {
Person *person = toVisit.pop_front();
foreach(friend in p.friends) {
if (!visitedFriends.contains(friend)) {
toVisit.push_back(friend);
visitedFriends.append(friend);
bool added = false;
foreach(school in p.schools) {
if (p.schools.contains(school) {
suggestedFriends.append(friend);
added = true;
break;
}
}
if (added) {
break;
}
foreach(place in p.places) {
if (p.places.contains(place) {
suggestedFriends.append(friend);
added = true;
break;
}
}
if (added) {
break;
}
foreach(school in p.schools) {
if (p.schools.contains(school) {
suggestedFriends.append(friend);
break;
}
}
}
}
}
return suggestedFriends;
}
We can use graph and and BFS to suggest friends.
Class Person {
string name;
string id;
list <School*> schools;
list<Company*> companies;
list<Person*> friends;
list<Location*> places;
}
list<Person*> FacebookSuggest(Person *p) {
list<Person*> suggestedFriends;
list<Person*> visitedFriends;
list<Person*> toVisit;
toVisit.push_back(p);
while (!toVisit.isEmpty() {
Person *person = toVisit.pop_front();
foreach(friend in p.friends) {
if (!visitedFriends.contains(friend)) {
toVisit.push_back(friend);
visitedFriends.append(friend);
bool added = false;
foreach(school in p.schools) {
if (p.schools.contains(school) {
suggestedFriends.append(friend);
added = true;
break;
}
}
if (added) {
break;
}
foreach(place in p.places) {
if (p.places.contains(place) {
suggestedFriends.append(friend);
added = true;
break;
}
}
if (added) {
break;
}
foreach(school in p.schools) {
if (p.schools.contains(school) {
suggestedFriends.append(friend);
break;
}
}
}
}
}
return suggestedFriends;
}
Not sure if this is a good approach.. Essentially you end up suggesting every person on Facebook!
@godofCode.. you are right, we can have a depth parameter ..it should search only to certain depth..?
I would start with friends of friends as potential suggestions. These can all be retrieved by a breadth-first search restricted to a depth of 2. In that same breadth-first search, I would also calculate how many of the user's friends know each potential suggestion and rank the suggestions by this number. Simply put, if you're not friends with someone who is friends with 30 of your friends, that's usually a better person to recommend to you than someone who is friends with only one person you know.
- eugene.yarovoi April 01, 2013We could modify the approach above to be more likely to recommend people that are friends with people you interact with a lot. The BFS would be the same, but the ranking algorithm could, instead of giving each potential suggestion 1 ranking point per mutual friend, vary the points based on how much you interact with the mutual friend.
We might consider being less likely to recommend friends that have been recommended recently and were not added by the user. We might also throw in some element of chance to give lower-ranked recommendations the possibility of showing up occasionally.
We might also consider removing from recommendations people you've un-friended in the past. People that you've blocked definitely shouldn't show up.
I'm sure Facebook's recommendation system is a lot more complicated than that and probably considers tens or hundreds of factors. It might even use machine learning to learn the factors that are most likely to make users add the people recommended to them. These are just some starting thoughts.