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.

- SycophantEve June 19, 2015 | Flag Reply
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.

- Naph June 23, 2015 | Flag Reply
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.

- Anonymous June 27, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More