## Interview Question

• 0

Country: India
Interview Type: Written Test

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

I think the previous comments misunderstood the question. The question is to check if the sorted array contains a number that repeats at least n/2 times. The answer to this question is either yes or no (so the array might not contain such a number).

We know that if such a number exists than it will appear in the n/2-th position, so we can search for the first and last occurances of this number to determine if it appears more than n/2 times. This will take O(log n) time using binary search.

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

Yes, I misinterpreted...appologies....it will be O(lg N)

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

The upper bound (for worst case) on number of comparison is log(n) , and lower bound(for best case i.e, when all elements are same) is O(1) , so overall complexity will be O(logn) , NOT theta(n) because its not a tight bound.
Correct me if I am wrong

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

My thinking is log(N) works using a modified binary search. If the central element is not the majority element then we know there's no majority element. If it is, then choose the half-way point for both halves and check whether they are the majority element. If they both are, you're done. If not, then for the half that is not, set the 'upper' bound to the element you're currently at and look in the middle of where you're at and the center, and for the other half set the 'lower' bound and look in the middle. If you now have two majority elements you're done, else keep repeating the process. These two illustrations show what I mean:

x x x x x x x a (a) a a a a a a a x
x x x x >x x x a (a) a a a a< a a a x
x x x x x x >x a (a) a a a a a a< a x
x x x x x x x >a (a) a a a a a a a< x

[x x x x >x a a a] (a) [a a a a< a x x x]
x x x x [x a >a a] (a) a a a a [a x< x x]
x x x x [x >a] a a (a) a a a a [a< x] x x

You're doing 2 * log(N), so should be log(N) all up.

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

yes i think this will work.. thanks

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

No this doesn't work. What if the majority element is in positions 0...n/2 inclusive.
In this case it will not be the majority element in the second half.

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

I think O(logn) will be the answer b/c if no is present it will be at middle pos.Now we hv to count how many times it occurs in array (for that find first occurance and last occurance using binary search in O(logn) time ) if it is more than n/2 then this is the number.so time is O(1) + O(logn) ie O(logn)

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

All the answers only prove an upper bound, i.e. require no more than O(log n).

The question is asking for a tight bound. For instance, why can't the answer be c? (iterated log I believe).

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

yes correct!!

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

If the number appears at middle then we can find the leftmost occurance(l) of element and rightmost occurance(r) in log*n time using Interpolation search .So,if r-l+1>=n/2 we can say it occurs more than n/r times

Comment hidden because of low score. Click to expand.
-1
of 3 vote

The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is:
Theta(1)

This is because since the array is sorted then the number which is repeated more than n/2 times will appear as the middle element in array, that is, it will appear at index n/2 for (both even and odd n).

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

So technically speaking, you don't _need_ any comparisons, do you?

So Theta(1) is incorrect, I guess :)

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

Eg. Array: 1 2 3 5 5 5 5 5 6 9 10 . If it is like in this array, how could you decide in 1 comparison?

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

if i am not wrong the question was about to find whether there is a number which is repeated n/2 times. not to find the number.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

It would take constant time that is theta(1)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

The fact it appears at index n/2 dose not tell us anything about of number of appearances of it.
However two comparisons:

``````x == a[n/4-1]
x == a[3*n/4+1]``````

will give the answer (and it's still O(1)).

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

kish-kush ! The number may be present in the position range of 0 to n/2+1, so it will not be present in the position of 3/4*n.
You have to find the first and last occurance positions using binary search to determine if there are at more than n/2 occurances.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

theta(1) - only 3 comparisons required. If the value is present at n/2, n/4 and 3n/4 positions, we are sure that it is repeated more than n/2 times.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

theta(1) will be the answer ,, since that number will definitely occupy (n/2)th position of array
so just compare with A[n/2].
In any possible permutation A[n/2] will always be one of these numbers.

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.