Sunday, October 16, 2011

Interview question

Question
Got a phone interview recently. The question is how to find out an integer which appears more than 50% times in an array of integers. For example, [1 1 0 1 2] should return 1, while [1 1 0 2 3] should return nothing.

Solution
The basic idea is finding out a candidate before checking if it repeats more than enough times. The algorithm is described in a paper entitled "Finding Repeated Elements" by Misra and Gries. The algorithm consists of two steps. First, it identifies a candidate value. The candidate value either occurs >50% of the time or there is no element in the array that occurs >50% of the time. The second step verifies whether the candidate element does indeed occur >50% of the time. Here's the algorithm, implemented in C:
#define undefined (-1)
int find_element(int array[], int n)
{
    /* Step 1: Find the element that occurs >50% of the time, if there is one.  */
    int c = 0;
    int candidate = undefined;
    for (int i = 0; i < n; i ++)
    {
        if (array[i] == candidate)  /* Match.  */
            c += 2;
        else if (i == c)  /* New candidate.  */
        {
            c += 2;
            candidate = array[i];
        }
    }

    /* Step 2: Verify that the candidate actually occurs >50% of the time.  */
    for (i = 0, c = 0; i < n; i ++)
        if (array[i] == candidate)
            c ++;

    if (c * 2 > n)
        return candidate;
    else
        return undefined;
}

No comments:

Post a Comment