Stupid edge-cases!

While doing some testing for coming up with a better version for the First missing positive question, I added a bunch of more test cases and compared several different methods with each other. Then I found the following problems:

Input [-5] returned 2147483647 but expected 1
Input [-5, -4, -3] returned 2147483647 but expected 1
Input [0, 0, 0, 0] returned 2147483647 but expected 1
Input [] returned 2147483647 but expected 1

To correct these problems, I added some edge-case checking; to check for array where there are no positive integers. As these really are edge-cases, I haven't decided how to handle these. As there technically isn't a. If I would have handled 7 8 9 as return 1 then I would have returned 1 for these edge cases also, but I feel that wouldn't be expected behavior from this algorithm so therefore I decided to throw an exception.

The new code is:

public int simonNew(int[] array) {
    boolean[] foundIntegers = new boolean[array.length];
    int smallestPositive = Integer.MAX_VALUE;

    for (int i : array) {
        if (i > 0 && i < smallestPositive)
            smallestPositive = i;
    }
    if (smallestPositive == Integer.MAX_VALUE)
        throw new IllegalArgumentException("Array must not be null and must contain at least one positive integer");

    for (int i : array) {
        if (i < smallestPositive)
            continue;

        int index = i - smallestPositive;
        if (index < foundIntegers.length)
            foundIntegers[index] = true;
    }

    for (int i = 0; i < foundIntegers.length; i++) {
        if (!foundIntegers[i])
            return i + smallestPositive;
    }
    return foundIntegers.length + smallestPositive;
}

1. if (i > 0 && i < smallestPositive)
       smallestPositive = i;
   

   could be

   if (i > 0)
       smallestPositive = Math.min(smallestPositive, i);
   

   I think it's a little bit easier to read.

2. At work I'd use parametrized tests which help defect localization. Anyway, you could extract out a verifier method to remove some duplication:

   @Test
   public void test() {
       verifyMissingInt(3, 1, 2, 0);
       verifyMissingInt(4, 1, 2, 3);
       verifyMissingInt(2, 3, 4, -1, 1);
       verifyMissingInt(10, 7, 8, 9);
       verifyMissingInt(5, 3, 4, 2, 7, 6, 1);
       verifyMissingInt(5, 3, 4, 2, 7, 6, 1, -4);
   }
   
   private void verifyMissingInt(int expected, int... data) {
       assertEquals(expected, missingInt(data));
   }
   

   Unfortunately, every parameter is integer, so it's not easy to separate expected output from input data. Two other ways:

   verifyMissingInt(3, new int[] { 1, 2, 0 });
   

   and

    verifyMissingInt(3, array(1, 2, 0));
   

   with

   private int[] array(int... data) {
       return data;
   }
   

It might be possible to solve this problem without using a bitfield or boolean array at all. In an interview, it's important to ask questions to clarify the requirements.

Assuming that the positive inputs always consist of a consecutive range of numbers with no duplicates and exactly one missing number, the answer can be obtained by arithmetic in a single pass. The following solution passes all of the tests in the question.

public static int missingInt(int[] array) {
    int min = Integer.MAX_VALUE, max = 0, count = 0;
    long sum = 0;

    for (int i : array) {
        if (i <= 0)  continue;
        count++;
        sum += i;
        if (i < min) min = i;
        if (i > max) max = i;
    }

    int range = max - min;
    if (count == 0) {
        // No positive inputs
        assert sum == 0;
        return 1;
    } else if (range == count) {
        // Probably one missing element between min and max.
        // Calculate expected sum of all integers from min to max, inclusive.
        long rangeSum = ((long)max + min) * (max - min + 1) / 2;
        return (int)(rangeSum - sum);
    } else if (range == count - 1) {
        // Probably all consecutive numbers.  As defined in the
        // question, we want max + 1.
        assert sum == ((long)max + min) * (max - min + 1) / 2;
        return max + 1;
    } else {
        throw new IllegalArgumentException();
    }
}

The caveat is that if the input array contains duplicate entries, or if it is missing multiple entries between the smallest and largest positive number, then the behaviour is undefined. It is sometimes possible to detect such unexpected inputs, but not always.

As indicated by the assertions, there is some redundancy in the statistics. If you don't want to perform the consistency check (which is pretty weak anyway), you could eliminate count.

Since there are multiple ways to solve this problem, and you don't know which solution your interviewer prefers to see, it's important to ask and clarify what the requirements are.