Given a friend graph, return friend suggestion for a person.
Suggested friend should be the person who has more number of mutual friends with the given user. If there are multiple such people, return any one of them.

Interviewer asked me to design class to represent this person.

I came up with below class.

class Person {
	int id;
	HashSet<Person> friends;
}

public Person getFriendSuggestion(Person person) { 
	Person result = null;
	HashSet<Person> probableCandidates = new HashSet<>();
	for(Person friend : person.friends) {
		for(Person p : friend.friends) {
			if(!person.friends.contains(p)) {
				probableCandidates.add(p);
			}
		}
	}
	
	int max = 0;
	for(Person cand : probableCandidates) {
		int temp = 0;
		for(Person friend : cand.friends) {
			if(person.friends.contains(friend)) {
				temp++;
			}
		}
		if(temp >= max) {
			max = temp;
			result = cand;
		}
	}
	
	return result;
}

1 <-> 2 <-> 3
1 <-> 4 <-> 3
1 <-> 4 <-> 5
Ans - 3
Explanation - Here 1 has 2 and 4 as direct friends. 3 has 2 and 4 direct friends. Here probable candidates for suggestions are 3 and 5. Out of them, 3 has more number of mutual friends with 1.

I started with putting all the probable person in a hashset. then iterated over the hashset to find out mutual friend with each probable person.
I was able to come up with the solution which runs in O(n^3) TC.

Recruiter later told me that interviewer gave negative feedback because my solution was not the optimized solution.

I have been thinking about different solution but cannot think of any.

Can this problem be solved in better TC?