An array A[1....n] is said to

Yahoo Interview Question for Software Engineer / Developers

0

of 0 votes

13
Answers
An array A[1....n] is said to have a majority element if more than half of its entries are the same.
Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element,
and, if so, to find that element.
The elements of the array are not necessarily from some ordered domain like the integers, and so there can be
no comparisons of the form "is A[i] > A[j]?".
However you can answer questions of the form: "is A[i] = A[j]?" in constant time.
- gullu September 12, 2010 | Report Duplicate | Flag | PURGE
Yahoo Software Engineer / Developer Algorithm

Email me when people comment.

An error occurred in subscribing you.

More Questions from This Interview

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 0 vote

Note that if there exist a majority element in an array then that element must occur at A[n/2](convince yourself). So, if we can find element with rank n/2(say 'X') in the input array we can just scan the array to count the no .of times 'X' appears in it. If this count is greater than n/2 then it's the majority element else there's no majority element. It will be O(N). But the main problem is how do we find X??

For that there exists an O(N) time algorithm to find the element with a given rank in an array(Google for "linear time order statistic" or refer to CLRS).

- cool September 13, 2010 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

This is one of the solution, there is another simplier solution called "majority algorithm". It's quite simple the trick is if there exist a majority element, it will always be the candidate that return by the method "FindMajorityCandidate", in this case, we just need to look through the list again to see if that's a true Majority element or not (same as the second step mentioned above)

public int FindMajority(int* arr, int n)
{
int majorityCandidate = FindMajorityCandidate(arr,n);
// count whether the candidate is a real majority element;
int count = 0;
for(int i=0; i<n ;i++)
{
if( arr[i]==majorityCandidate )
{
count++;

}
}
if(count>n/2)
{
return majorityCandidate;
}
return -inf;
}

public int FindMajorityCandidate(int* arr, int n)
{
int majority;
int count = 0;

for(int i=0; i< n; i++)
{
if(majority == arr[i])
{
count++;
}else if(--count <= 0)
{
// change the majority candidate when the count for the current candidate become 0;
majority = arr[i];
count = 1;
}
}
}

- Nat September 13, 2010 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

- Nat September 13, 2010 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

dude @cool..given that the elements may not be integers too in that the greater or less than comparison will not be possible..is it via ascii comparison????

- dinesh March 02, 2011 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

A minor mistake in your code...

if(count>n/2)
{
return majorityCandidate;
}

should be

if (count >= ((n-1) / 2) +1 ) {
return majorityCandidate;
}

considering the odd and even number of elements.

- Delon August 15, 2011 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

@cool: Ur solution is not convincing ,coz there mi8 be a possibility that majority element's all the occurrences are in first and last quarter of array and some other element at A[n/2].. so it need not be necessary that majority element if accurs will be surely at A[n/2] position....

- saumils1987 September 20, 2010 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

<blockquote><code>int getit(int *ar, int num)
{
  int full_pairs = (num + 1) / 2;
  bool odd_num_of_pairs = full_pairs % 2 ? true : false;
  int midle_index = num >> 1;
  int midle_item = ar[midle_index];
  bool left(false);
  
  if(ar[midle_index - 1] == midle_item)
    left = false;
  else if(ar[midle_index + 1] == midle_item)
    left = true;
  else return midle_item;

  if((left && odd_num_of_pairs) || (!left && !odd_num_of_pairs))
    getit(ar + midle_index, num - midle_index);
  else getit(ar, midle_index);

}

int main()
{
  const int N = 3;
  int ar[N] = {1, 2, 2};//, 2, 3, 3, 4, 4, 5, 6, 6};  
  std::cout << getit(ar, N);
}

</blockquote>

- Anonymous October 30, 2010 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

- Anonymous October 30, 2010 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

Use Hash Table. Start from index 0 and hash the elements one by one.
When ever u change the count of a element, check whether the new count is greater than n/2 or not. If yes, then this is your majority element.
Time Complexity O(n).

- neeraj.fullwithattitude September 18, 2011 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

if we remove 2 different elements from array say a and b and a != b then ans of remaining element i.e ans of array of size N-2 will be same as ans of N element array.
we can do this using one counter. and one variable.

int majority(int *a){
     temp ;
     count = 0;
     for( int i = 0; i< N; i++){
           if( count == 0) temp = a[i];
            if( a[i] == temp)
                    count++;
           else{
                    count--;
          }
         
   }
   if(count > 0) return temp;

}

- jigs February 18, 2012 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

This would fail for array 3,2,2,3,2,3,2,3,5. Algo would give 5 as majority element.
To complete your solution, I would take the projected solution from Algo (5 in this case) and verify that frequency of 5 is more than 9/2. If not, there is no number in majority.

- saket September 16, 2013 | Flag

Comment hidden because of low score. Click to expand.

of 0 vote

If number is in majority then at least two of them are adjacent. Therefore using a[i]=a[i+1] we can find the majority number in O(n).

- vivs0766 July 26, 2012 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 vote

@vivs,

your algo will fail for this test case : 6 1 6 2 6 3 6

- Anonymous October 29, 2012 | Flag Reply

CareerCup

Yahoo Interview Question for Software Engineer / Developers

Books

Videos

Resume Review

Mock Interviews