Friday, January 25, 2013

Interview: Find the Number that repeats the most times in a row in an array of integers

This is another one of these not related to job functions questions that get asked.

The solution is simple:

public static int MaxRepeatInArray(int[] arr)
{
    //Input checks
    if (arr == null || arr.Length < 1)
    {
        throw new DataException("Empty Array");
    }
    int bestChoice = arr[0];
    int bestCounter = 1;
    int currentChoice = arr[0];
    int currentCounter = 1;
    for (int i = 0; i < arr.Length; ++i)
    {
        if (currentChoice == arr[i])
        {
            currentCounter++;                    
        }
        else
        {
            if (currentCounter > bestCounter)
            {
                bestChoice = currentChoice;
                bestCounter = currentCounter;
            }
            currentChoice = arr[i];
            currentCounter = 1;
        }
    }
    // Incase sequence is at end
    if (currentCounter > bestCounter)
    {
        bestChoice = currentChoice;
        bestCounter = currentCounter;
    }
    return bestChoice;   
}

 

It takes just one pass of the data O(n). The time could be shortened a little by seeing if the number of remaining items

if (currentCounter > bestCounter)
  {
      bestChoice = currentChoice;
      bestCounter = currentCounter;
      if (arr.Length - i < bestCounter)
          return bestChoice;
  }
Which needs to be done when the choice changes and not on every pass.

1 comment: