Quick Overview

The question evaluates competency in graph traversal, set operations, and adjacency-list manipulation for social-network style data. Commonly asked in Coding & Algorithms interviews for Data Engineer roles, it gauges the ability to reason about relationship aggregation, duplicate elimination, and algorithmic efficiency when computing friends-of-friends, representing a practical application of algorithmic and data-structure knowledge rather than a purely conceptual exercise.

Recommend friends-of-friends

Company: Meta

Role: Data Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question Given a dictionary such as {A:[B,C], B:[C,D], C:[E]}, return for a user U all people followed by U’s followees but not already followed by U. Order is irrelevant and duplicates must be removed.

Quick Answer: The question evaluates competency in graph traversal, set operations, and adjacency-list manipulation for social-network style data. Commonly asked in Coding & Algorithms interviews for Data Engineer roles, it gauges the ability to reason about relationship aggregation, duplicate elimination, and algorithmic efficiency when computing friends-of-friends, representing a practical application of algorithmic and data-structure knowledge rather than a purely conceptual exercise.

You are given a directed "follows" graph as a dictionary mapping each user to the list of users they follow. For a given user `U`, return everyone followed by `U`'s followees (the friends-of-friends) who is NOT already followed by `U` and is NOT `U` themselves. Duplicates must be removed and order does not matter. For deterministic output, return the recommendations sorted in ascending order. Example: given `{A: [B, C], B: [C, D], C: [E]}` and user `A`: - A follows B and C. - B follows C and D; C follows E. - Candidates from followees = {C, D, E}. - Remove C (A already follows C) and A itself. - Result = [D, E].

Constraints

  • Each key in the graph maps to a (possibly empty) list of followees.
  • A user may appear as a followee without being a key in the graph (they follow no one).
  • Self-loops and mutual follows are possible and must be handled.
  • The recommended set excludes the user themselves and anyone the user already directly follows.
  • Results contain no duplicates.

Examples

Input: ({'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['E']}, 'A')

Expected Output: ['D', 'E']

Explanation: A follows B,C. B->C,D and C->E give candidates {C,D,E}; drop C (already followed) leaving D,E.

Input: ({'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['E']}, 'B')

Expected Output: ['E']

Explanation: B follows C,D. C->E and D has no followees; E is not already followed by B, so result is [E].

Hints

  1. First collect the set of users that `U` directly follows so membership checks are O(1).
  2. Iterate over each direct followee, then over the people that followee follows.
  3. Skip any candidate that equals `U` or is already in `U`'s direct-follow set; collect the rest in a set to dedupe.

Loading coding console...