Interview Question


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.

- Anonymous April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pavi April 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- codeAddict February 15, 2014 | Flag
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.

- Anonymous April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes i think this will work.. thanks

- scylla April 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gen-y-s April 08, 2013 | Flag
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)

- abhishek21 September 19, 2015 | Flag Reply
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).

- Anonymous April 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

yes correct!!

- Anonymous October 18, 2013 | Flag Reply
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

- Anonymous August 11, 2014 | Flag Reply
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).

- pavi.8081 April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

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

- Anonymous April 07, 2013 | Flag
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?

- BVarghese April 07, 2013 | Flag
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.

- Anonymous April 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

It would take constant time that is theta(1)

- ashirwad94 April 07, 2013 | Flag Reply
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)).

- Mabooka-Mabooka April 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- gen-y-s April 07, 2013 | Flag
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.

- paddy April 08, 2013 | Flag Reply
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.

- Anonymous April 10, 2013 | 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