I thought of turning my solution in comments to post here.
Original post https://leetcode.com/discuss/interview-question/1615045/Google-or-Phone-Interview-or-Suggested-Friend

We have to suggest best friend for A.
Answer is D (D has most common friends here i.e. 2)

A -- B
|    |
C -- D
|
E

For such questions, first ask all your clarifying questions related to constraints to interviewer. Think first and do not jump into BFS or DFS on seeing the above connections.

Constarints are important. Lets say if the count of users are small say 10 only. Then we can avoid single linked list and map below for friends and can use only adjacency matrix only.

The solution I would go for:
Step 1:
Maintain a list of friends of

A: B -> C
B: A -> D
C: A -> D -> E
D: C
E: C

Step 2:
Maintain hash map like isFriends[pair(A,B)] = 1 if friends for checking friends in O(1) time

Step3:
Now we will maintain a doubly link list and will store pointers to each node (in Hash Map) for the O(1) move operation.
Friends of A are B and C
At start the doubly linked list is empty with start and end node only:
null<- start <-> end -> null
Iterate over friends of B except for A and its friend.
------ We get D.
------ D is not present in the doubly link list. Create node D with count 1. In another Hash map store link to this node of D. Links[D] = nodeD
null <- start <-> D(1) <-> end -> null

Iterate over C.
------ We get E
------ As E is not present, create E. Is E's count greater than D's? No (we will not move it to start). Add node E to hash map also. Links[E] = nodeE
null <- start <-> D(1) <-> E(1) end ->null.
------ We get D. D is present in hash map (so it is present in doubly link list). Get nodeD as currNode = Links[D]. Increment count to 2.
------ It is already present at the start, so no need to move.
null <- start <-> D(2) <-> E(1) end ->null.

Like this, the best-suggested friend will be at start->next.

Now say, if the count of E becomes 3.
currNode = Links[E]
we now move this currNode to after start in O(1).
How?

//remove E from current position
currNode->prev->next = currNode->next;
currNode->next->prev = currNode->prev;
//move E to start now.
currNode->next = start->next;
start->next->prev = currNode;
currNode->prev = start;
start->netx = currNode;

:: Remember, we move to start only if its count is highest.
Similar strategies could be applied for the top 5 or 10 friends. Move and maintain sorted order only for the top 5 or 10 friends.
This approach could be used for best recommend movies or song genre to a user.