# The Social Graph

> Everyone knows someone.

Canonical URL: <https://datadriven.io/problems/the_social_graph>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a list of groups (each group is a list of person names), compute per-person friend count: for a group [A, B], both A and B gain each other as friends. For a singleton [X], X exists but gains no friend from that row. Friendships are deduplicated: if A and B appear together in multiple groups, it is still one friendship. Return a dict mapping each person to their distinct friend count.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **dict accumulation** from structured input and handling both pair and singleton cases. It probes whether a candidate can parse variable-length groups and correctly initialize counts for isolated nodes.

---

### Break down the requirements

#### Step 1: Initialize every person with a count of 0

Both members of pairs and singletons must appear in the result. Singletons have 0 friends.

#### Step 2: For each pair, increment both members' counts

A friendship is bidirectional: if Alice and Bob are friends, both get +1.

#### Step 3: Return the friend count dict

The dict maps each person's name to their total friend count.

---

### The solution

**Group parsing with bidirectional count**

```python
def count_friends(groups: list) -> dict:
    friends = {}
    for group in groups:
        if len(group) == 1:
            person = group[0]
            if person not in friends:
                friends[person] = 0
        elif len(group) == 2:
            a, b = group[0], group[1]
            if a not in friends:
                friends[a] = 0
            if b not in friends:
                friends[b] = 0
            friends[a] += 1
            friends[b] += 1
    return friends
```

> **Time and Space Complexity**
>
> **Time:** O(g) where g is the number of groups. Each group is processed in O(1).
> 
> **Space:** O(p) where p is the number of unique people.

> **Interviewers Watch For**
>
> Handling singletons correctly. Candidates who only process pairs will miss isolated nodes, returning an incomplete graph representation.

> **Common Pitfall**
>
> Assuming all groups are pairs. The prompt explicitly says singletons exist for people with no connections.

---

## Common follow-up questions

- What if groups could have more than 2 people? _(Tests generating all pairwise friendships within a group.)_
- How would you find connected components? _(Tests BFS/DFS traversal on the adjacency structure.)_
- What if friendships could be repeated in the input? _(Tests whether to count duplicates or deduplicate first.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_social_graph)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.