The Loudest Voice

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
L4

Problem

Our incident alerts keep firing on feeds where one event type seems to swamp everything else, and we want a check that settles it. Given events, one event-type string per record, return the type that makes up strictly more than half the records, or None when no type does, an empty feed included. Feeds run to 500000 records, too many to keep a separate count for every distinct type, so the check may hold only a fixed handful of values no matter how long the feed is.

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

Example 1

Input:

events = ["timeout","timeout","oom","timeout","disk"]

Output:

"timeout"

Example 2

Input:

events = ["oom","timeout","disk"]

Output:

null

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: Get the empty feed out of the way first

An empty feed has no dominant type, so return None before anything else. That guard is what lets the rest of the function seed its guess from events[0] without ever indexing into nothing.

Step 2: Nail down what 'more than half' means

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 3: 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 4: Verify the survivor before you report it

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 make a second pass, count how many times the candidate appears, and return it only when that count beats len(events) // 2.

The solution

Cancellation pass plus verification pass
def majority_event_in_stream(events: list[str]):
    if not events:
        return None

    candidate = events[0]
    count = 0
    for event in events:
        if count == 0:
            candidate = event
            count = 1
        elif event == candidate:
            count += 1
        else:
            count -= 1

    occurrences = 0
    for event in events:
        if event == candidate:
            occurrences += 1

    if occurrences > len(events) // 2:
        return candidate
    return None

Common follow-up questions