Degrees of Separation Between Members

Run a breadth-first search from both members at once, always expanding the smaller frontier, and stop as soon as the frontiers meet or the two depths add up to three. Searching from both ends explores about b + b² members instead of b³ for b connections each. Return 1, 2 or 3 hops, and -1 for anything further.

hardPattern: Graphs·From Devana's LinkedIn question set

Problem

A profile page shows whether the viewer is a 1st, 2nd or 3rd degree connection of the member they are looking at. It runs on every profile view, over a graph where some members have tens of thousands of connections.

Write connection_degree(graph, member_a, member_b), where graph maps each member to their connections, which are mutual. Return the number of hops on the shortest path between the two members if it is 1, 2 or 3, and -1 if they are further apart or not connected at all.

def connection_degree(graph: dict[str, list[str]], member_a: str, member_b: str) -> int:

This is one of Devana's own questions, written in the style of LinkedIn's interviews. It is not a question leaked from LinkedIn, and Devana is not affiliated with LinkedIn.

Constraints

• Connections are mutual: if B is in A's list, A is in B's.
• member_a and member_b are different members.
• Return 1, 2 or 3 for the hop count, and -1 for anything further or unreachable.
• The search must stop at depth 3 rather than exploring the whole network.
• A member can have up to 30,000 connections.

Examples

Input:  graph = {"A": ["C"], "C": ["A", "B"], "B": ["C"]}, member_a = "A", member_b = "B"
Output: 2

Input:  a path A, B, C, D, E; member_a = "A", member_b = "E"
Output: -1

Hints

Open one at a time, and try the problem again after each.

Approach: from brute force to optimal

How to say it in the interview

Say BFS first, then do the arithmetic for depth three on a dense graph out loud; that number is what justifies searching from both ends. Explain the meeting check and the stopping rule, and bring up the member with 30,000 connections as the case that makes expanding the smaller frontier matter.

Solution

Python

def connection_degree(graph, member_a, member_b, max_degree=3):
    dist = ({member_a: 0}, {member_b: 0})      # distance from each end
    frontier = [[member_a], [member_b]]
    depth = [0, 0]
    while frontier[0] and frontier[1] and depth[0] + depth[1] < max_degree:
        side = 0 if len(frontier[0]) <= len(frontier[1]) else 1   # the smaller one
        mine, other = dist[side], dist[1 - side]
        depth[side] += 1
        best, grown = None, []
        for member in frontier[side]:
            for friend in graph.get(member, []):
                if friend in other:                # the two searches meet
                    hops = depth[side] + other[friend]
                    best = hops if best is None else min(best, hops)
                if friend not in mine:
                    mine[friend] = depth[side]
                    grown.append(friend)
        if best is not None:
            return best
        frontier[side] = grown
    return -1

JavaScript

function connectionDegree(graph, memberA, memberB, maxDegree = 3) {
  const dist = [new Map([[memberA, 0]]), new Map([[memberB, 0]])]; // distance from each end
  const frontier = [[memberA], [memberB]];
  const depth = [0, 0];
  while (frontier[0].length > 0 && frontier[1].length > 0 && depth[0] + depth[1] < maxDegree) {
    const side = frontier[0].length <= frontier[1].length ? 0 : 1; // the smaller one
    const mine = dist[side];
    const other = dist[1 - side];
    depth[side] += 1;
    let best = null;
    const grown = [];
    for (const member of frontier[side]) {
      for (const friend of graph[member] ?? []) {
        if (other.has(friend)) { // the two searches meet
          const hops = depth[side] + other.get(friend);
          best = best === null ? hops : Math.min(best, hops);
        }
        if (!mine.has(friend)) {
          mine.set(friend, depth[side]);
          grown.push(friend);
        }
      }
    }
    if (best !== null) return best;
    frontier[side] = grown;
  }
  return -1;
}

Both versions are tested against the same cases, including every example on this page.

• Expanding the smaller frontier is what protects you from the member with 30,000 connections: their side is expanded last, if at all.
• The whole level finishes before returning, so the shortest of several meetings at that level is the one reported.
• max_degree is a parameter, so the same code answers a cheaper "within two" check.

Follow-up questions

Common mistakes

• A single-sided BFS to depth three on a dense graph.
• Returning 4 or more instead of -1.
• Returning at the first meeting inside a level instead of finishing the level, which can report a longer path than the shortest.
• Exploring the whole connected component to prove that two members are far apart.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Related problems

• Recalculate a Spreadsheet After a Cell Changes: Find everything downstream of the change, then topologically sort just that part of the graph.
• Design a News Feed: Push to most followers, pull from the few huge accounts, and rank the merged candidates.
• Graphs: the pattern guide, with more practice questions.