# The Runaway Leader > Noise scatters in every direction; the true reading is the one that keeps coming back. Canonical URL: Domain: Python · Difficulty: easy · Seniority: L3 ## 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. ## 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. > **Trick to solving** > > Tally every value into a dict in one pass, then return the key with the highest count. That is O(n) time. There is no positional shortcut, because once the winner is not guaranteed to be a majority it can sit anywhere in the list. --- ### 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** ```python 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 ``` > **Time and space** > > **Time:** O(n). The first loop builds the tally in one pass over the readings; the second walks only the distinct values (never more than n) to read off the largest count. Both are linear. > > **Space:** O(k) for the k distinct values. On a noisy sensor batch k is small, so this is effectively constant next to the input. > **In production...** > > In production you would reach for collections.Counter: `Counter(readings).most_common(1)[0][0]` is these same two passes under the hood, one to build the tally and one to find the top key. The explicit dict loop above is worth knowing because it shows exactly what that one-liner is doing. **The tempting one-liner, and why it is worse** ```python 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 pitfall** > > Assuming a majority. The word 'dominant' makes people picture a value that owns the list, so they reach for Boyer-Moore or the median trick and add a majority verification pass that this problem does not need and that gives the wrong answer anyway. The value is only the most common. Count, do not vote. --- ## Common follow-up questions - What if two values could tie for the most frequent? How would you decide the winner? _(Tests handling a rule for ties, since a plain highest-count scan silently keeps whichever value it saw first.)_ - How would you return the three most common readings instead of just one? _(Tests generalizing from top-1 to top-k, sorting the distinct values by count.)_ - How would you compute this over data split across many machines? _(Tests merging partial tallies, since per-partition counts combine by summing per key.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_runaway_leader) - [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.