Find the Value That Fills More Than Half of an Integer Array
Company: ByteDance
Role: Site Reliability Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Overview: A coding question asking for the value that occupies more than half of the positions in an integer array, where such a value is guaranteed to exist. It tests array traversal, counting and reasoning about running time and extra space.
Constraints
- 1 <= len(nums) <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9
- A qualifying value always exists: exactly one value v has 2 * count(v) > len(nums)
- Every element and the answer fit in a signed 32-bit integer; no value can exceed 2^31 - 1
Examples
Input: ([4, 7, 4],)
Expected Output: 4
Explanation: Source example 1: 4 occurs twice among three positions and 2 * 2 = 4 > 3.
Input: ([9, 9, 3, 9, 3, 3, 9],)
Expected Output: 9
Explanation: Source example 2, narrowest odd margin: 9 occurs 4 of 7 times while 3 occurs 3 times.
Hints
- The qualifying test is 2 * count > len(nums); at most one value can pass it, and the input guarantees that one does.
- Think about what the guaranteed value implies for all the other values combined: together they fill fewer than half of the positions.
- Return the value itself, not its index or how many times it occurs.