Coding Problem #3

Este problema fue preguntado en una entrevista por Stripe.

Dado un array de enteros, encuentre el primer entero positivo faltante en el array. En otras palabras, encuentre el entero positivo más bajo que no exista en la matriz. La matriz también puede contener duplicados y números negativos..


Por ejemplo, la entrada [3, 4, -1, 1] debería retornar 2. La entrada [1, 2, 0] debería retornar 3.


Se puede modificar la matriz de entrada.

Como siempre antes de ver la solución intenta resolverlo, te servirá para practicar, vamos a ver que solución se nos ocurre hoy. En el segundo ejemplo el resultado es 3, porque el entero positivo más bajo es el 1, (el 0 no es ni positivo ni negativo) y ya está en el array, por tanto el más bajo que NO se encuentra es el 3.



Solución:

Como siempre empezaremos escribiendo nuestros tests y pasándolos poco a poco, no solo por ser buena técnica, sino que en casos en los que quizás no entendamos el problema demasiado bien nos ayuda a comprobar casos que no se nos habían ocurrido, o a entender mejor el problema y como solucionarlo.


Aquí los tests que he usado, he comprobado casos como que el array llegara vacío, con 1 solo elemento positivo, 1 solo elemento negativo y el resto de casos, hacer TDD me ha ayudado a ver estos casos que no aparecen en el enunciado y que pueden darse, primero te dejo con los tests:


@Test
public void givenAnEmptyArrayShouldReturnZero() {
    int number = Problem.findTheFirstMinimumPositiveInArray(new int[]{});
    assertEquals(0, number);
}

@Test
public void givenAnArrayWithOneElementLargerThanOneShouldReturnTheBeforeNumber() {
    int number = Problem.findTheFirstMinimumPositiveInArray(new int[]{2});
    assertEquals(1, number);
}

@Test
public void givenAnArrayWithOneNegativeElementShouldReturnZero() {
    int number = Problem.findTheFirstMinimumPositiveInArray(new int[]{-2});
    assertEquals(0, number);
}

@Test
public void givenAnArrayWithOneElementEqualToOneShouldReturnTheAfterNumber() {
    int number = Problem.findTheFirstMinimumPositiveInArray(new int[]{1});
    assertEquals(2, number);
}

@Test
public void givenAnArrayWithTwoOrMoreElementsShouldReturnTheMinimumPositiveNumberThatNotExistsInArray() {
    int number = Problem.findTheFirstMinimumPositiveInArray(new int[]{2, 3, 4});
    assertEquals(1, number);
}

@Test
public void givenAnArrayWithTwoOrMoreIncludeTheOneElementsShouldReturnTheMinimumPositiveNumber() {
    int number = Problem.findTheFirstMinimumPositiveInArray(new int[]{3, 4, -1, 1});
    assertEquals(2, number);
}

@Test
public void givenAnArrayWithTwoOrMoreIncludeTheOneElementsShouldReturnTheMinimumPositiveNumberGreaterThanEverNumberInArray() {
    int number = Problem.findTheFirstMinimumPositiveInArray(new int[]{1, 2, 0});
    assertEquals(3, number);
}

Ahora con el código que implementé (y debajo su refactorización) para pasar los tests:


public static int findTheFirstMinimumPositiveInArray(int[] numbers) {
    if (numbers.length == 0) return 0;
    if (numbers.length == 1 && numbers[0] > 1) return numbers[0] - 1;
    if (numbers.length == 1 && numbers[0] == 1) return 2;
    Arrays.sort(numbers);
    numbers = Arrays.stream(numbers).filter(n -> n >= 0).toArray();
    for(int i = 0; i < numbers.length; i++){
        if(numbers[i] > i + 1) return numbers[i] - 1;
    }
    return numbers.length > 0 ? numbers[numbers.length - 1] + 1 : 0;
}

Esta claro que el código esta sucio, vamos a limpiarlo un poco:


public static int findTheFirstMinimumPositiveInArray(int[] numbers) {
    numbers = Arrays.stream(numbers)
            .sorted()
            .filter(n -> n >= 0)
            .toArray();
    
    for(int i = 0; i < numbers.length; i++){
        if(numbers[i] > i + 1) return numbers[i] - 1;
    }
    
    return numbers.length > 0 ? numbers[numbers.length - 1] + 1 : 0;
}

Esta es mi solución final, quizás el for y la última comprobación podrían ser mejores. no he encontrado una forma mejor de hacerlo, si se te ocurre compártela en los comentarios :), ordeno el array, filtro solo los números positivos y lo paso a un array de nuevo, sobre este array si los números van en orden devuelvo el que falta, y si llego al final del array y no he encontrado ninguno que falte, devuelvo el último elemento + 1.


La comprobación del if(numbers[i] > i + 1) quizás es buena idea extraerla a un método para que fuera mas verboso, ¿se te ocurre como se podría llamar el método?


Espero que te haya gustado, nos vemos en la próxima :)

©2020 por Juanma Perez.