Faces in the Crowd

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

Domain
Python
Difficulty
medium
Seniority
L3

Problem

You are replaying a site's visit log one day at a time, where each entry in daily_visitors is that day's list of visitor names and a name can repeat within a day. For each day, report how many people showed up who had never appeared on any earlier day.

New arrivals keep showing up. Count the ones you have not seen yet.

Example 1

Input:

daily_visitors = [["ann","bo","ann"],["bo","cy"],["cy","dee","ann"]]

Output:

[2,1,1]

Example 2

Input:

daily_visitors = []

Output:

[]

Worked solution and explanation

What this really is

This is a set difference streamed over batches, dressed up as counting new arrivals. Each day the only real question is which of today's visitors you have never seen before. The tempting shortcut is to count the distinct names per day in isolation, or to sum daily head counts, and both quietly recount returning visitors as new, so every number after the first day is inflated. Worse, the single-day example still passes, so the bug sails through review. The fix is one cumulative set: today's new faces are set(today) minus everyone seen so far, and the size of that difference is your answer. Membership and difference are O(1) per name; reach for a list and if name not in seen and the same loop silently becomes O(n^2).

How to get there

Step 1: Carry a cumulative set of seen names

Hold one set of every name you have counted on any earlier day. This is the memory that separates a first appearance from a return, and it is the piece the per-day-only approach throws away.

Step 2: Subtract before you add

For the current day, the new faces are set(day) minus seen. Append the size of that difference, then update seen with the whole day. Order matters: fold the day into seen before you measure it and every visitor already looks old, giving zeros everywhere.

The solution

Cumulative set, one difference per day
def new_faces(daily_visitors):
    seen = set()
    result = []
    for day in daily_visitors:
        new_today = set(day) - seen
        result.append(len(new_today))
        seen.update(day)
    return result
Per-day distinct (wrong)
result = [ len(set(day)) for day in daily_visitors ]
Cumulative set (correct)
seen = set() result = [] for day in daily_visitors: result.append(len(set(day) - seen)) seen.update(day)

Common follow-up questions