FastPrepMaximum Friendship Hops

Maximum Friendship Hops

Google logoGoogle● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

The interview report asks for the largest friendship hop count. For this exercise, assume the supplied graph is one connected, undirected friendship snapshot with n people numbered from 0 to n - 1.

Each row of friendships is [u, v] and represents a link usable in either direction. A hop traverses one link. For each pair of people, use the fewest possible hops between them; return the largest of these shortest distances over all pairs.

For this exercise, assume a person has distance 0 to themselves. Duplicate links and self-links have no effect on the answer. Cycles are allowed: do not return the length of a longest simple route, and do not assume the graph is a tree.

The input already describes the selected snapshot. There are no timestamps or updates to process, and no starting person is supplied. The one-person graph returns 0.

Function

maxFriendshipHops(n: int, friendships: int[][]) → int

Examples

Example 1

n = 5friendships = [[0,1],[1,2],[2,3],[3,4]]return = 4

The endpoints need four links; every other pair needs at most four.

Example 2

n = 4friendships = [[0,1],[1,2],[2,3],[3,0]]return = 2

Opposite vertices need two links. Taking a longer route around the cycle does not increase their shortest distance.

Example 3

n = 3friendships = [[0,1],[0,2],[1,2]]return = 1

Every distinct pair has a direct friendship.

Constraints

  • For this exercise, assume 1 <= n <= 300.
  • 0 <= friendships.length <= 2000 and every row contains exactly two labels in [0, n - 1].
  • The graph is connected and undirected. Duplicate links, self-links and cycles are allowed.

More Google problems

See Google hiring insights
public int maxFriendshipHops(int n, int[][] friendships) {
    // Write your code here.
}
n5
friendships[[0,1],[1,2],[2,3],[3,4]]
expected4
Checking account…