CareerCup

Moore's voting algorithm, seems a pretty standard problem asked in the tech interviews.

#include <stdio.h>

int findmajelement(int arr[], int size)
{
    int count = 1, i = 0, m_index= 0;
	for(i = 1; i < size; i++)
	{
		if(arr[m_index] == arr[i])
			count++;
		else
			count--;
		if( count == 0)
		{
			m_index = i;
			count = 1;
		}
	}
	return arr[m_index];
}

void ismajelement(int arr[], int maj_elem, int size)
{
	int i = 0, count = 0;
	for(i = 0; i< size; i++)
	{
		if(arr[i] == maj_elem)
			count++;
	}
	printf("count = %d\n");
	if(count > size/2)
		printf("majority element = %d\n", maj_elem);
	else
		printf("no majority element present\n");
}

int main()
{
	int arr[6] = {2,4,2,2,4};
	int majority_element  = 0;
	majority_element = findmajelement(arr, 6);
	ismajelement(arr, majority_element, 6);
	return 0;
}

1. Sort the array 2. pick the n/2th element

#include <stdio.h>
#include <stdio.h>
int find(int *a ,int n)
{   
	int target = a[0];
	int num = 1;
	int i;
	for( i=1; i< n; i++)
	{
		if(num == 0)
		{
			target = a[i];
			num++;
		}
		else if(target == a[i])
		{
			num++;
		}
		else
		{
			num--;
		}
	}

	return target;
}

int main()
{
	int a[5] = {0,1,2,1,1};
	printf("%d", find(a,5));
	
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Problem1
{
    class Program
    {
        static void Main(string[] args)
        {
            /*
             * Find the majority element which occurs more than n/2 times in an array of n size, 
             * which contains duplicate elements in minimum time and space complexity.
             */
            int[] arr = { 2, 2, 2, 3, 4 };

            Dictionary<Int32, Int32> dict = new Dictionary<int, int>();

            int majItem = 0;
            foreach (int item in arr)
            {
                if (dict.ContainsKey(arr[item]))
                {
                    dict[arr[item]] = ++dict[arr[item]];

                    if (dict[arr[item]] > (arr.Length / 2))
                    {
                        majItem = item;
                    }
                }
                else
                {
                    dict[arr[item]] = 1;
                }
            }

            System.Console.WriteLine(majItem.ToString() + " has occurred more than half the length of the array!");
        }

    }
}

How about

public void findElement(int[] elements) {
		Moore m = new Moore();
		int candidate = m.findMajority(elements);
		int count = 0;
		for(int i=0; i<elements.length; i++) {
			if(elements[i] == candidate)
				count++;
		}
		
		if(count > (elements.length/2)) {
			System.out.println("Element "+candidate);
		} else {
			System.out.println("No such element");
		}
		
	}

where the class Moore is a vanilla version of the Moore majority algorithm.

If the array is an array of ints, why don't we just sort the array and iterate through the sorted array. This is pretty simple cuz in the sorted array, the same ints should all be right next to each other. This takes O(n) time and almost no space.

candidate = 0
count = 0
for value in input:
if count == 0:
candidate = value
if candidate == value:
count +=1
else:
count -= 1