Interview Question
Country: India
This code is in c#
struct Dom
{
public int Value;
public int Index;
}
Dom[] sDominator;
int Top=-1;
void Pop1()
{
if (Top >= 0)
{
Top--;
}
}
void Push(Dom c)
{
Top++;
sDominator[Top] = c;
}
public int Dominator(int[] A)
{
sDominator = new Dom[A.Length];
for (int i = 0; i <= A.Length - 1;i++ )
{
Dom b= new Dom ();
b.Index =i;
b.Value =A[i];
if (Top<0 )
{
Push(b);
}
else
{
if (A[i]==sDominator[Top].Value)
{
Push(b);
}
else
{
Pop1();
}
}
}
if (Top >= 0)
{
int CanDidate = sDominator[Top].Value;
int Index = sDominator[Top].Index;
int[] counters;
counters = Array.FindAll(A, x => x == CanDidate);
if (counters.Length >( A.Length /2))
{
return Index;
}
}
return -1;
}
This code is in c#
struct Dom
{
public int Value;
public int Index;
}
Dom[] sDominator;
int Top=-1;
void Pop1()
{
if (Top >= 0)
{
Top--;
}
}
void Push(Dom c)
{
Top++;
sDominator[Top] = c;
}
public int Dominator(int[] A)
{
sDominator = new Dom[A.Length];
for (int i = 0; i <= A.Length - 1;i++ )
{
Dom b= new Dom ();
b.Index =i;
b.Value =A[i];
if (Top<0 )
{
Push(b);
}
else
{
if (A[i]==sDominator[Top].Value)
{
Push(b);
}
else
{
Pop1();
}
}
}
if (Top >= 0)
{
int CanDidate = sDominator[Top].Value;
int Index = sDominator[Top].Index;
int[] counters;
counters = Array.FindAll(A, x => x == CanDidate);
if (counters.Length >( A.Length /2))
{
return Index;
}
}
return -1;
}
Check Moore's voting algorithm.
- hulkthedestroyer May 03, 2014