The Crowd Pleaser

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
Alcon

Problem

Given a list of integers, return the element appearing strictly more than n//2 times (where n is the list length). You may assume such an element always exists.

One value shows up more than all others combined.

Example 1

Input:

nums = [3,2,3]

Output:

3

Example 2

Input:

nums = [2,2,1,1,1,2,2]

Output:

2

Worked solution and explanation

Why this problem exists in real interviews

This tests whether a candidate knows Boyer-Moore majority vote, an O(n) time, O(1) space algorithm for finding a majority element. It distinguishes candidates who rely on sorting or hash maps from those who know optimal algorithms.

Break down the requirements

Step 1: Initialize candidate and count

Start with no candidate and count 0.

Step 2: Scan through the list updating the vote

If count is 0, adopt the current element as candidate. If it matches, increment; otherwise decrement.

Step 3: Return the surviving candidate

Since the problem guarantees a majority exists, the final candidate is the answer.

The solution

Boyer-Moore majority vote
def majority_element(nums: list) -> int:
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
    return candidate

Common follow-up questions