# The Loudest Voice

> One event type is drowning out the rest. Find it.

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

An event stream pushes one event-type string per record, and during an incident a single type can swamp the feed. Given a list of event type strings `events`, return the type that appears strictly more than half the time (more than `len(events) // 2` occurrences), or `None` when no type clears that bar. The feed can hold up to 500000 records and you cannot afford to keep a separate count for every distinct type, so solve it in O(1) extra space.

## Worked solution and explanation

### What this problem really is

Strip the incident-detection costume and this is a constant-space dominance search: find the element that owns more than half a sequence while holding nothing but a single guess and a tally. The reason it bites is the memory bound. With 500000 records you cannot lean on a `Counter` or a `dict`, so the obvious O(n)-space answer is off the table and you have to cancel events against each other instead. The trap is trusting the survivor. A single pass that pairs off mismatches always leaves you holding some element, but on a stream with no true majority that element is a coincidence, not an answer. Skip the recount and you confidently report a dominant event type on a perfectly healthy feed, flagging an outage that never happened.

---

### Break down the requirements

#### Step 1: Nail down what 'more than half' means

Pin the threshold exactly: an event type qualifies only if it occurs strictly more than `len(events) // 2` times. Because the comparison is `>` and not `>=`, at most one element can clear it, and on some inputs none do.

#### Step 2: Cancel events against each other in one pass

Walk the stream once keeping a single `candidate` and an integer `count`. When `count` is zero, adopt the current event as the candidate. Increment when the event matches the candidate, decrement when it differs. Every non-candidate event cancels one candidate vote, so an element that truly owns more than half the stream cannot be fully cancelled and survives as the candidate.

#### Step 3: Verify the survivor

The cancellation pass always ends with some candidate, but it is only guaranteed correct IF a true majority exists. On a no-majority stream the survivor is arbitrary, so you make a second pass and actually count how many times the candidate appears.

#### Step 4: Return the dominant type or None

Return the candidate only when its verified count is strictly greater than `len(events) // 2`; otherwise return `None`.

---

### The solution

**Cancellation pass plus verification pass**

```python
def majority_event_in_stream(events: list[str]):
    candidate = None
    count = 0
    for event in events:
        if count == 0:
            candidate = event
            count = 1
        elif event == candidate:
            count += 1
        else:
            count -= 1
    if candidate is None:
        return None
    occurrences = 0
    for event in events:
        if event == candidate:
            occurrences += 1
    if occurrences > len(events) // 2:
        return candidate
    return None
```

> **Time and Space Complexity**
>
> **Time:** O(n). One pass to settle on a candidate and one pass to verify it.
> 
> **Space:** O(1). Only a candidate reference and a counter are stored, regardless of stream size. That is the whole point: a `Counter` would be O(distinct types), which the 500000-record bound forbids.

> **Interviewers Watch For**
>
> Whether you include the second verification pass. The cancellation pass alone will happily hand back a non-majority element (for example on `['oom', 'timeout', 'disk']`), so without the recount every 'no majority' case comes back wrong, which in production means crying outage on a balanced feed.

> **Common Pitfall**
>
> Using `>=` instead of `>` when comparing the count to `len(events) // 2`. On an even-length stream a perfect 50/50 split is NOT a majority, and `>=` would incorrectly report one. The threshold must be strict.

---

## Common follow-up questions

- How would you find all events that appear more than n/3 of the time? _(Tests generalizing the cancellation idea to the Misra-Gries / k-candidate variant tracking k-1 candidates.)_
- What if the events arrive as a one-time stream you cannot replay for verification? _(Tests reasoning about a true single-pass streaming setting where you cannot re-read the data.)_
- When would a Counter-based approach actually be the better choice? _(Tests the O(n) space trade-off and why the constraint rules it out here.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_loudest_voice)
- [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.