Entrevista técnica: ¿Cómo encontrar el k-ésimo entero positivo faltante con búsqueda binaria?

Qué evalúa el entrevistador

El problema superficial es contar en un arreglo; el núcleo es convertir “cuántos valores faltan hasta el índice i” en un predicado monótono y luego buscar su límite. LeetCode 1539 proporciona el enunciado público del problema y una entrada en el conjunto de problemas de Amazon. La guía para SDE de Amazon enfatiza código ejecutable, robusto, probado y con verificación de casos límite. Estas fuentes respaldan el valor de preparación, no una afirmación de frecuencia fija de entrevistas para ninguna empresa.

• Si escribes missing(i) = arr[i] - i - 1.
• Si demuestras que el conteo de faltantes no es decreciente.
• Si manejas una respuesta más allá del último elemento del arreglo.
• Si comparas el escaneo, la búsqueda binaria y la generación directa por contrato.

Marco de respuesta de 30 segundos

Indica que el arreglo utiliza índices basados en cero. Hasta arr[i], hay arr[i] enteros positivos en el rango de valores pero solo i + 1 elementos observados, por lo que el conteo de faltantes es arr[i] - i - 1. Realiza una búsqueda binaria del primer índice con missing(i) >= k. Si es i, la respuesta es k + i; si ningún índice lo satisface, la respuesta está después del arreglo y es k + n. El escaneo toma O(n), la búsqueda binaria O(log n), y ambos usan O(1) de espacio adicional.

Preguntas aclaratorias antes de responder

1. ¿Se garantiza que el arreglo sea estrictamente creciente y positivo? Si no, ordenar o eliminar duplicados cambia el contrato.
2. ¿Es k positivo y pueden los valores exceder el rango de enteros seguros del lenguaje?
3. ¿Se requiere un solo valor o todos los valores faltantes? Devolver todos los valores tiene un costo de salida.
4. ¿Se puede recibir la entrada como flujo sin acceso aleatorio? Eso puede favorecer un escaneo.
5. ¿Debe permanecer inalterado el arreglo original? La solución de búsqueda binaria no lo muta.

Análisis detallado paso a paso

Paso 1: Construir la fórmula de conteo de faltantes

Si el arreglo fuera continuo, arr[i] sería igual a i + 1. La diferencia es el número de enteros positivos que faltan en [1, arr[i]]:

missing(i) = arr[i] - (i + 1)
           = arr[i] - i - 1

Para arr = [2, 3, 4, 7, 11] e i=3, missing(3) = 7 - 3 - 1 = 3; los valores faltantes son 1, 5 y 6.

Paso 2: Usar la monotonicidad para un límite

El incremento estricto produce arr[i+1] >= arr[i] + 1. Por lo tanto missing(i+1) >= missing(i), de modo que el conteo nunca disminuye. Busca el primer índice con missing(i) >= k: todo lo que está antes de él tiene muy pocos valores faltantes, mientras que ese índice y todo lo posterior tienen al menos k.

Paso 3: Recuperar la respuesta a partir del límite

Sea i el límite. Hay i elementos observados del arreglo antes de él, y menos de k valores faltantes antes del límite. Por lo tanto, el k-ésimo valor faltante es k + i. Si no existe tal límite, el conteo final de faltantes todavía está por debajo de k; todos los n elementos observados se encuentran antes de la respuesta, por lo que el resultado es k + n.

Paso 4: Implementar la búsqueda binaria

function findKthPositive(arr: number[], k: number): number {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const missing = arr[mid] - mid - 1;
    if (missing < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return k + left;
}

Usar right = n permite que el límite quede inmediatamente después del arreglo. Al terminar, left es la primera posición cuyo conteo de faltantes alcanza k, por lo que la misma fórmula k + left maneja ambos casos.

Paso 5: Demostrar la complejidad y probar los límites

Cada iteración reduce a la mitad el intervalo de búsqueda, lo que da un tiempo O(log n) y variables adicionales constantes. Prueba arr = [1,2,3,4], k = 2 para 6, arr = [2,3,4,7,11], k = 5 para 9, una secuencia a la que le falte desde el 1, una cola continua, k=1 y un arreglo de un solo elemento. También verifica los límites de enteros en el lenguaje elegido.

Respuesta modelo de alta calidad

Definiría el número de enteros positivos faltantes hasta el índice i como arr[i] - i - 1. Dado que el arreglo es estrictamente creciente, ese conteo es monótono, por lo que busco binariamente el primer índice cuyo conteo sea al menos k. Si el límite es i, el k-ésimo valor faltante es k + i; establecer el límite derecho en n maneja de forma natural una respuesta posterior al valor máximo del arreglo.

Utilizo un intervalo semiabierto [left, right). Cuando missing(mid) es menor que k, el límite está a la derecha; de lo contrario, conservo mid. El resultado es k + left, en tiempo O(log n) y espacio O(1). Pruebo huecos iniciales, huecos finales, un arreglo continuo, un único elemento y varios valores de k, y comparo contra un oráculo basado en escaneo.

Errores comunes

• Escribir arr[i] - i y omitir el término de restar uno.
• Buscar la última posición falsa pero usar la fórmula de respuesta de primera verdadera.
• Establecer right en n - 1 y manejar mal las respuestas posteriores al arreglo.
• Aplicar la fórmula cuando la entrada no está ordenada o contiene duplicados.
• Probar solo los ejemplos y omitir [1,2,3], [2] o una cola continua.
• Afirmar que la búsqueda binaria siempre es más rápida sin discutir la entrada ordenada y las constantes para n pequeña.

Compensaciones de implementación

Elige el escaneo lineal o la búsqueda binaria a partir del tamaño de los datos y el contrato de límites, luego verifica el invariante con pruebas.

Preguntas de seguimiento y respuestas

¿Por qué el conteo de faltantes es monótono?

El incremento estricto significa que el siguiente valor crece al menos en uno. Cuando el índice crece en uno, el valor también crece al menos en uno, por lo que arr[i] - i - 1 no puede disminuir.

¿Qué pasa si el arreglo no está ordenado o tiene duplicados?

Cambia el contrato primero: ordena, elimina duplicados y retén los valores positivos. Ordenar cuesta al menos O(n log n); solo entonces se aplica la fórmula original de conteo de faltantes. No afirmes O(log n) para una entrada desordenada.

¿Cuándo es preferible un escaneo lineal?

Para un arreglo corto, una sola consulta o un flujo sin acceso aleatorio, el escaneo es más simple. La búsqueda binaria asume una entrada ordenada con acceso aleatorio y tiene costos de configuración y constantes.

¿Cómo devolverías los primeros k valores faltantes?

Encuentra el límite de valor, luego genera los valores con un puntero de arreglo en tiempo de salida O(k). El trabajo de salida no se puede ocultar dentro de una afirmación de O(log n).

¿Cómo evitas el desbordamiento para k o valores grandes?

Usa un tipo de entero seguro o de 64 bits y verifica k + left y arr[i] - i - 1. Si se permite precisión arbitraria, especifica BigInt o la representación equivalente en la interfaz y las pruebas.

Rúbrica de evaluación

Un candidato fuerte deriva el predicado monótono, implementa una búsqueda semiabierta y explica la fórmula de la respuesta. Un candidato que solo recuerda el código y no puede demostrar el límite necesita más preguntas de sondeo.