Adobe Interview Question
SDE1sCountry: United States
Not without further conditions. Here's a special case though: let's suppose that all elements not part of the majority are unique. Then we can find the majority element in O(1) expected time if we allow randomization.
Here's how. Select pairs of distinct indices uniformly at random. If two distinct indices have the same value, then you've found the majority element. This happens with probability at least 1/2 * 1/2 = 1/4, since the majority element comprises at least half the elements. If you didn't find the majority element, start over and try again. In the expectation, you try only 4 times or less, considering the probability of success is at least 1/4. Each try takes O(1) time, so the entire algorithm is O(1) in the expectation.
Outside of some additional condition like that, the problem isn't possible in less than O(n). That's because you can't really distinguish between the case of 52 0s, 51 1s and the case of 51 0s, 52 1s without looking at a large fraction of all the elements.
I'd like to know as well. I doubt it since the algorithm to find the majority element is O(n). If you look through the array, and it's even length, then the only way to know it doesn't have a majority element is if no adjacent pairs are equal but some pairs may be equal and it still might not have a majority element. Thus in the best case(no pairs) you need to scan to find pairs which is still O(n).
If it's odd then the majority element is either one of the paired elements of the n-1 subarray, or the last element. Which means no matter what you have to check the last element which is O(n).
- SycophantEve June 19, 2015However, I could be wrong and would like to be corrected.