# Faces in the Crowd

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

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

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.

## 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**

```python
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)

> **Why it stays cheap**
>
> Time is O(total names across all days): building set(day), the difference, and the update are each linear in that day's size. Space is O(distinct visitors) for the cumulative set plus the result list. There is no cheaper exact answer: deciding novelty requires remembering who you have already seen.

> **Common pitfall**
>
> The correctness trap is measuring before you update, or never carrying the seen set at all. The performance trap is a list with `not in`, which is O(n) per name and turns a long replay into O(n^2). Both pass the tiny example, then break in different ways at scale.

> **Interviewers watch for**
>
> The tell is whether the candidate reaches for a cumulative set and a set difference immediately. Someone who counts distinct names per day, or uses a list membership scan, usually does not notice the double-count or the quadratic blow-up until you hand them a log with returning visitors or a few million rows.

---

## Common follow-up questions

- How would you handle a stream so large you cannot keep every distinct visitor in memory? _(Tests bloom filters or HyperLogLog-style estimators when the exact seen set no longer fits in memory.)_
- What changes if novelty is scoped to a sliding window of the last k days instead of all history? _(Tests maintaining a Counter of live values and decrementing as days leave the window, so a visitor becomes new again once they age out.)_
- How would you compute this new-faces-per-day count in SQL? _(Tests expressing first-appearance detection in SQL, for example ROW_NUMBER over visitor ordered by day and counting the day-one rows per day.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/faces_in_the_crowd)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.