The Runaway Leader

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

We're cleaning a batch of sensor readings where noise scatters around one true value that was recorded more often than any other reading. Return that value from the list of integers; you can assume the most frequent value is unique.

Noise scatters in every direction; the true reading is the one that keeps coming back.

Example 1

Input:

readings = [2,4,4,2,4,5]

Output:

4

Example 2

Input:

readings = [7,7,1,2,3,7,4]

Output:

7

Worked solution and explanation

What this really is

Under the sensor-cleaning costume this is a mode problem: which value shows up more often than any other? The skill being probed is whether you count. Almost everyone who counts gets it right, so the real tell is the candidate who tries to skip counting: return the max, the first reading, or the classic trick of sorting and grabbing the middle element. That median trick is seductive because it returns the answer for a strict majority, but you were never promised a majority here, only the most common value. Reach for it and you get the wrong reading on any batch where the true value is not the smallest, the largest, or the middle of the sort, which is most batches.

Why the shortcuts lie

Sorted middle / Boyer-Moore
Both return the correct value ONLY when one value owns more than half the list. Take [7, 7, 1, 2, 3, 7, 4]: the winner is 7, but the sorted middle is 4. The shortcut silently returns a rival.
Frequency tally
Count every value and pick the maximum count. This does not care whether the winner is a majority or just the most common, so it holds on [7, 7, 1, 2, 3, 7, 4] and every other batch.

The distinction is majority versus mode. A majority element appears strictly more than n/2 times and can be found in O(1) space by Boyer-Moore or by the sorted-median trick. A mode just appears more than any other value, possibly with a small plurality, and the only general way to find it is to count. This problem is the second kind, so counting is not one option among several: it is the requirement.

The solution

Tally into a dict, then pick the top key
def dominant_element(readings):
    counts = {}
    for value in readings:
        counts[value] = counts.get(value, 0) + 1

    winner = readings[0]
    for value, count in counts.items():
        if count > counts[winner]:
            winner = value
    return winner
The tempting one-liner, and why it is worse
def dominant_element(readings):
    return max(set(readings), key=readings.count)

Correct, but readings.count rescans the whole list for every distinct value, so this is O(n * k). On 100,000 readings with many distinct values it crawls; the single dict pass stays linear.

Common follow-up questions