## Adobe Interview Question for SDE1s

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

``````{1,2,3,2,4 2} has no majority element for sure
{1, 2, 2, 3, 4, 2} might have a majority element(it doesn't)
{2,1,2,3,2,5,2} has a majority element and no pairs(odd)``````

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).
However, I could be wrong and would like to be corrected.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think we can tell in sub-linear time. But I'd love to be corrected if wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.