The Social Graph

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Meta

Problem

You're filling the friend-count column from a social graph export, where each record is either a pair of names, meaning those two people are mutual friends, or a single name, meaning a person who has shown up with no connections. Return a mapping from every person who appears to how many friends they have, where each pair adds one to both of its names and anyone who only ever appears alone lands at 0.

Everyone knows someone.

Example

Input:

groups = [["Ana","Ben"],["Ana","Cleo"],["Ben","Dan"],["Ben","Cleo"],["Ray","Mia"],["Sam"],["Pat"],["Ana"]]

Output:

{"Ana":2,"Ben":3,"Cleo":2,"Dan":1,"Ray":1,"Mia":1,"Sam":0,"Pat":0}

Worked solution and explanation

What this really is

Strip the friend-group costume off and this is a degree count over an undirected edge list, plus one initialization gotcha. Anyone can bump two counters per pair. What actually separates candidates is remembering that a name's FIRST appearance is what puts it in the dict at all. A person who only ever shows up alone, or as the silent second name in a pair, has to be seeded at 0 before any increment. Miss that and isolated people vanish from the output entirely, which is exactly the case an interviewer is checking.

The two cases

Step 1: Seed every name you see at 0

Loop the names in each group and setdefault each one to 0. This single line is what guarantees singletons and second-in-pair names actually exist as keys before you ever touch a counter.

Step 2: A two-name group is one bidirectional friendship

If the group has two names, add one to each. Undirected means both endpoints gain a friend, not just the first name listed.

Step 3: Return the map

The keys are everyone who appeared; the values are their friend totals. Singletons and pair members are already present from step 1.

The solution

Seed-then-increment
def count_friends(groups: list[list[str]]) -> dict[str, int]:
    friends: dict[str, int] = {}
    for group in groups:
        for person in group:
            friends.setdefault(person, 0)
        if len(group) == 2:
            a, b = group
            friends[a] += 1
            friends[b] += 1
    return friends

Seeding every name first is what folds the singleton case into the same loop as the pairs.

Only counts pairs
Iterating just the len == 2 groups and bumping counters never creates a key for [Sam] or [Pat]. They disappear, and Dan, who only appears as a second name, is fine only because the increment creates him by luck.
Seeds then counts
The setdefault pass creates a 0 entry for every name on sight, so a lone person and a second-name-in-a-pair both exist before any math. The increment then just adds to keys that are guaranteed present.

Common follow-up questions