Java collection question for representing a social network from Testdome-CodePudding

Given a data structure representing a social network, write a function that finds friends of a certain degree. Friends of the first degree are a member's immediate friends, friends of the second degree are friends of a member's friends excluding first degree friends, etc.

This problem url: https://www.testdome.com/questions/java/friends/331

How can I write getFriendsOfDegree(Member member, int degree) method?

 import java.util.ArrayList;
    import java.util.Collection;
    import java.util.List;

class Member {
    private String email;
    private Collection<Member> friends;

    public Member(String email) {
        this(email, new ArrayList<Member>());
    }

    public Member(String email, Collection<Member> friends) {
        this.email = email;
        this.friends = friends;
    }

    public String getEmail() {
        return email;
    }

    public Collection<Member> getFriends() {
        return friends;
    }

    public void addFriends(Collection<Member> friends) {
        this.friends.addAll(friends);
    }

    public void addFriend(Member friend) {
        friends.add(friend);
    }
}

public class Friends {
    public static List<Member> getFriendsOfDegree(Member member, int degree) {
        throw new UnsupportedOperationException("Waiting to be implemented.");
    }

    public static void main(String[] args) {
        Member me = new Member("[email protected]");
        Member myFriend = new Member("[email protected]");
        Member myFriendsFriend = new Member("[email protected]");

        me.addFriend(myFriend);
        myFriend.addFriend(myFriendsFriend);

        for (Member friend : getFriendsOfDegree(me, 2))
            System.out.println(friend.getEmail());
        // Correct output:
        // [email protected]
    }
}

CodePudding user response：

We can implement Breadth First Search to come up with the n(th) degree friends of a member. Create a Queue to store the friends in each layer and create a HashSet to store visited friends. There may be cycles in the graph, i.e. having a friend's friend as friend, therefore we have to keep track of visited friends in set. In each layer, get the friends of the current member and add it to the queue. Don't forget to check if it is visited before.

In each layer, increment the variable deg. If deg is equal to degree, then return the elements in the Queue. You can find the implementation of it below.

public static List<Member> getFriendsOfDegree(Member member, int degree) {
   int deg = 0;
   Queue<Member> q = new LinkedList<>();
   HashSet<Member> visited = new HashSet<Member>();

   q.add(member);
   visited.add(member);

   while(!q.isEmpty()) {
         if(deg == degree) {
             List<Member> friends = new ArrayList<Member>();
             while(!q.isEmpty()) friends.add(q.poll());
             return friends;
         }
         deg  ;
         int size = q.size();
         for(int i=0; i<size; i  ) {
             Member mem = q.poll();
             for(Member friend: mem.getFriends()) {
                 if(!visited.contains(friend)) {
                     q.add(friend);
                     visited.add(friend);
                 }
             }
         }
     }
     return new LinkedList<Member>();  // cover the edge cases
 }

In order to cover the edge cases here, return new LinkedList<Member>() at the very end of your function. It simply returns an empty LinkedList if there are no n(th) degree friends of the given member.

Output when I run on the website.

Simple cases: Correct answer
Complex cases: Correct answer
Edge cases: Correct answer
Performance test: Correct answer

If you are not familiar with graph algorithms or in particular with BFS, you can have a look at this tutorial.