I was asked this question and I tried with both bfs and dfs approach, but couldn't come to conclusion. Can anyone point me to right solution.
Problem: Given Interface and the Implementation.
package sample.sixdegrees;
import java.util.Collection;
public interface SocialNetworkService {
/**
* Returns a set of Ids of the immediate friends of the Person with the given Id.
*/
Collection<String> findFriends(String personId);
/**
* Creates a new Person in the social network with the given name and returns the unique Id of the Person.
*/
void addPerson(String personId);
/**
* Adds a friend relationship between the given two Person Ids
*/
void addFriend(String personId, String friendId);
}package sample.sixdegrees;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
public class SNSImpl implements SocialNetworkService {
HashMap<String, Collection<String>> relationships = new HashMap<>();
/**
* Returns a list of Ids of the immediate friends of the Person with the given Id.
*/
@Override
public Collection<String> findFriends(String personId) {
return relationships.get(personId);
}
/**
* Creates a new Person in the social network with the given name and returns the unique Id of the Person.
*/
@Override
public void addPerson(String personId) {
relationships.put(personId, new ArrayList<>());
}
/**
* Adds a friend relationship between the given two Person Ids
*/
@Override
public void addFriend(String personId, String friendId) {
// Ensure that both persons exist in the map for convenience.
if (!relationships.containsKey(personId)) {
addPerson(personId);
}
if (!relationships.containsKey(friendId)) {
addPerson(friendId);
}
relationships.get(personId).add(friendId);
relationships.get(friendId).add(personId);
}
}Solution to write in the Class
package sample.sixdegrees;
import java.util.List;
/**
* Implement the function in this class that will
*/
public class FriendFinder {
private final SocialNetworkService sns;
FriendFinder(SocialNetworkService socialNetworkService) {
sns = socialNetworkService;
}
/**
* Returns an ordered list of connectivity if the given personAId has a connection of friend relationships to personZId
* within the specified degreesOfSeparation, otherwise return null.
*/
public List<String> findShortestPath(String personAId, String personZId, int degreesOfSeparation) {
// TODO: Implement this function by calling the 'injected' SocialNetworkService to search friends of the Person Ids...
return null;
}
}And to test your solution:
package sample.sixdegrees;
import org.junit.Assert;
import org.junit.Test;
import java.util.Arrays;
public class FriendFinderTest {
@Test
public void findRelationshipPathBonusQuestionTest() {
SNSImpl sns = new SNSImpl();
sns.addFriend("Kevin", "UserB");
sns.addFriend("Kevin", "UserS");
sns.addFriend("UserB", "UserC");
sns.addFriend("UserA", "UserD");
sns.addFriend("UserX", "UserC");
sns.addFriend("UserY", "UserX");
sns.addFriend("Bacon", "UserY");
FriendFinder ff = new FriendFinder(sns);
Assert.assertEquals(ff.findShortestPath("Kevin", "Bacon", 5),
Arrays.asList("Kevin", "UserB", "UserC", "UserX", "UserY", "Bacon"));
// Create a shorter path that will be accessed later in the return collection (list in this test case) of friends
sns.addFriend("UserS", "Bacon");
Assert.assertEquals(ff.findShortestPath("Kevin", "Bacon", 6),
Arrays.asList("Kevin", "UserS", "Bacon"));
}
}Factors to consider...
Your solution should be optimal for time and space complexity. You can assume the average number of friends a user will have is ~300. Assume there is no limit to the number of people in the database.
Consider the size of the search space of your solution. How does the search space grow as you search deeper into the connections? What is the factor that affects the growth in the search space the most? Think of a solution that can reduce that factor by half...
Imagine two points on a perfectly flat lake. You drop a stone into the lake at point A and the ripple represents your search for point Z. When the ripple reaches point Z, you have found a connection. Now imagine dropping a stone at point Z. The ripple represents the search from point Z and when it reaches point A, you have found the connection to point A. If the crest of the ripple represents your search from a point so far, and the area of the entire ripple represents the search space (𝝅(r^2)), how can you drastically reduce the search space?
Once you have found a connection, how can you reconstruct the connection path from your searched person-IDs to give the actual list of shortest connecting IDs? What information do you need to store to be able to do this?