Entrevista de código: Encontrar el k-ésimo elemento más grande en un arreglo

Enunciado y contexto aplicable

Dado un arreglo de enteros nums y un entero k, devuelve el k-ésimo elemento más grande en ordenamiento secuencial, no el k-ésimo valor distinto. Asume 1 <= k <= nums.length <= 100,000 y -10,000 <= nums[i] <= 10,000.

Por ejemplo, nums = [3, 2, 1, 5, 6, 4] y k = 2 devuelve 5. Para nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] y k = 4, la respuesta es 4: los valores duplicados ocupan posiciones de rango separadas.

Este es un problema representativo de estadísticos de orden en entrevistas de código. Un ordenamiento completo, un min-heap de tamaño k y quickselect son todos válidos bajo diferentes restricciones. La respuesta principal a continuación utiliza quickselect aleatorizado de tres vías porque la entrada es un arreglo mutable en memoria y solo se requiere un rango. Modifica nums; copia el arreglo primero si quien invoca la función requiere la preservación de la entrada.

Qué evalúa el entrevistador

La primera señal es la precisión del contrato. "K-ésimo más grande" significa la posición k en orden descendente ordenado, incluyendo duplicados. No significa el k-ésimo valor distinto, los k valores más grandes ni el índice k en un arreglo basado en cero. En orden ascendente, el elemento solicitado tiene el índice basado en cero n - k.

La segunda señal es si el candidato deduce alternativas en lugar de simplemente recitar quickselect. El ordenamiento es la línea base más segura con O(n log n). Un min-heap de tamaño k toma tiempo O(n log k) y espacio O(k), y también funciona para entradas en flujo continuo (streaming). Quickselect descarta la partición que no puede contener el objetivo y tiene un tiempo esperado de O(n), pero el pivoteo aleatorizado no elimina su peor caso de O(n^2).

La tercera señal es un invariante de partición explícito. El código que "se parece a quicksort" no es suficiente. El candidato debe ser capaz de indicar qué se sabe sobre los elementos antes de lt, entre lt y i, entre i y gt, y después de gt, y luego explicar por qué el siguiente intervalo de búsqueda todavía contiene el rango objetivo.

Finalmente, el entrevistador busca el manejo de duplicados, la divulgación de mutaciones, el comportamiento ante entradas inválidas, el control iterativo para evitar el riesgo de profundidad de recursión y pruebas que comparen el resultado con un oráculo simple. Un algoritmo optimizado sin un límite de prueba o pruebas adversarias está incompleto.

Preguntas para aclarar antes de responder

• ¿El k-ésimo más grande cuenta los duplicados? Esta respuesta sigue las posiciones ordenadas, por lo que [5, 5, 4] con k = 2 devuelve 5. Un requisito de rangos distintos requeriría deduplicación o selección consciente de la frecuencia.
• ¿Se garantiza que k sea válido y puede el arreglo estar vacío? El contrato establecido de la entrevista garantiza 1 <= k <= n. La implementación aún lanza ValueError fuera de ese rango para que su comportamiento independiente sea explícito.
• ¿Puede la función mutar la entrada? La partición in-place ofrece un espacio auxiliar de O(1). Si la mutación está prohibida, copie primero y acepte un espacio adicional de O(n).
• ¿Está la entrada totalmente disponible o en streaming? Quickselect necesita acceso aleatorio y mutación. Para un flujo ilimitado, mantenga en su lugar un min-heap de tamaño k.
• ¿Necesitamos una sola consulta o muchas consultas de rango sobre los mismos datos? Quickselect es atractivo para un solo rango. Ordenar una vez puede ser mejor cuando muchas consultas posteriores justifican el trabajo inicial de O(n log n).
• ¿Es el rango de valores genuinamente pequeño y fijo? El rango establecido tiene solo 20,001 valores enteros posibles, por lo que el conteo es una alternativa válida. Cuesta tiempo O(n + R) y espacio O(R) para un ancho de rango R, pero no debe presentarse como una solución general cuando los valores no están acotados.
• ¿Debe estar acotado el tiempo en el peor de los casos? Quickselect aleatorizado ofrece un tiempo lineal esperado, no un tiempo lineal determinista en el peor de los casos. Si se requiere una garantía estricta para el peor de los casos, analice median-of-medians o elija un heap con un tiempo predecible de O(n log k).

Estructura de respuesta en 30 segundos

"El k-ésimo elemento más grande es el elemento en el índice ascendente n - k, contando los duplicados. Ordenar proporciona una línea base simple de O(n log n), y un min-heap de tamaño k ofrece un tiempo de O(n log k) para entradas en streaming o que no deben mutarse. Dado que este problema solicita un solo rango en un arreglo mutable en memoria, yo usaría quickselect aleatorizado iterativo. Divido el intervalo activo en valores menores, iguales y mayores que un pivote aleatorio. Si n - k se encuentra en la franja de iguales, el pivote es la respuesta; de lo contrario, conservo únicamente el lado que contiene ese índice. La partición de tres vías evita eliminar repetidamente valores iguales uno por uno. El tiempo esperado es O(n), en el peor de los casos O(n^2), y el espacio auxiliar es O(1). Lo verificaría comparándolo con el ordenamiento en arreglos aleatorios más casos con todos los elementos iguales, ordenados, ordenados en orden inverso, con muchos duplicados y casos límite para k."

Respuesta detallada paso a paso

Comience con un oráculo. Ordenar de forma ascendente y devolver sorted(nums)[len(nums) - k] es fácil de explicar y difícil de errar. Establece la conversión de rango y proporciona un resultado de referencia para las pruebas. Su costo es de tiempo O(n log n) y espacio O(n) cuando se preserva la entrada original mediante una copia.

Un heap acotado mejora el trabajo cuando k es pequeño o los datos llegan de forma incremental. Inserte cada valor en un min-heap y elimine el mínimo cada vez que su tamaño exceda k. Después de procesar todos los valores, la raíz es el más pequeño entre los k elementos más grandes, por ende, el k-ésimo más grande. El heap almacena k valores, por lo que el costo es de tiempo O(n log k) y espacio O(k). Si k está cerca de n y todo el arreglo ya está disponible, esta ventaja se reduce.

Quickselect aprovecha el hecho de que solo importa una posición final. Convierta el rango descendente a target = len(nums) - k. En cada intervalo activo [left, right], elija un valor de pivote aleatorio y realice una partición estilo Dutch national flag (bandera nacional holandesa). Durante el escaneo, mantenga:

• [left, lt) contiene valores menores que el pivote.
• [lt, i) contiene valores iguales al pivote.
• [i, gt] está sin clasificar.
• (gt, right] contiene valores mayores que el pivote.

Cuando el escaneo finaliza, [lt, gt] es la franja completa de iguales. Si target < lt, continúe en el lado de los valores menores. Si target > gt, continúe en el lado de los valores mayores. De lo contrario, el objetivo cae dentro de la franja de iguales, por lo que el valor del pivote es la respuesta. Este tratamiento es fundamental para arreglos como [7, 7, 7, 7]: una partición de dos vías puede producir repetidamente un volumen de trabajo casi idéntico, mientras que la versión de tres vías termina tras un solo escaneo.

import random


def find_kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k must be between 1 and len(nums)")

    target = len(nums) - k
    left = 0
    right = len(nums) - 1

    while left <= right:
        pivot = nums[random.randrange(left, right + 1)]
        lt = left
        i = left
        gt = right

        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1

        if target < lt:
            right = lt - 1
        elif target > gt:
            left = gt + 1
        else:
            return pivot

    raise RuntimeError("unreachable for a valid k")

El incremento de i es intencionalmente asimétrico. Después de intercambiar un valor mayor que el pivote con nums[gt], el valor entrante en i no ha sido clasificado, por lo que i permanece en su lugar. Después de mover un valor menor a la izquierda, ambas posiciones intercambiadas tienen clasificaciones conocidas, por lo que tanto lt como i avanzan.

La corrección se deriva del invariante y la eliminación de rangos. La partición preserva cada elemento de entrada y termina con todos los valores menores antes de la franja de iguales y todos los valores mayores después de ella. Por lo tanto, cada índice en [lt, gt] tiene el valor del pivote en orden secuencial. Si el objetivo está fuera de esa franja, el lado descartado y la franja de iguales no contienen ningún elemento que pueda ocupar el índice objetivo; el intervalo conservado todavía lo contiene. Cada iteración devuelve el resultado o reduce estrictamente el intervalo, por lo que eventualmente se devuelve un objetivo válido.

Cada partición escanea el intervalo actual una vez. Con pivotes aleatorios, el trabajo total esperado a lo largo de los intervalos conservados sucesivamente es O(n). Una secuencia de pivotes consistentemente extremos puede dejar intervalos de tamaños n - 1, n - 2, y así sucesivamente, produciendo un tiempo de peor caso de O(n^2). La implementación es iterativa y particiona in-place, por lo que su espacio auxiliar es O(1). El estado del generador de números aleatorios y el arreglo de entrada en sí no se cuentan como almacenamiento auxiliar.

Pruebe con un oráculo simple basado en ordenamiento en lugar de limitarse a ejemplos fijos:

def oracle(nums: list[int], k: int) -> int:
    return sorted(nums)[len(nums) - k]


cases = [
    ([3, 2, 1, 5, 6, 4], 2),
    ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4),
    ([1], 1),
    ([7, 7, 7, 7], 3),
    ([-5, -1, -3, -1], 2),
    (list(range(1000)), 1),
    (list(range(1000)), 1000),
]

for values, rank in cases:
    assert find_kth_largest(values.copy(), rank) == oracle(values, rank)

Agregue arreglos generados con muchos valores duplicados y compare cada k válido con el oráculo. Asimismo, asegure mediante aserciones que k = 0, k > n y un arreglo vacío lancen el error documentado. Establecer una semilla para el generador aleatorio hace que una prueba de propiedades fallida sea reproducible; ejecutar múltiples semillas pone a prueba diferentes caminos de partición.

Respuesta de muestra de alta calidad

"Trataré los duplicados como posiciones ordenadas independientes y asumiré que k es válido. Si el arreglo estuviera ordenado de forma ascendente, la respuesta estaría en el índice n - k. Mi punto de referencia es ordenar e indexar, lo cual es O(n log n). Un min-heap de tamaño k toma O(n log k) y sería mi elección para datos en streaming.

En este caso tenemos una sola consulta y podemos mutar el arreglo, por lo que usaré quickselect aleatorizado. Dentro del rango activo, elijo un pivote aleatorio y divido los valores en menores, iguales y mayores que el pivote. La división de tres vías es importante porque los duplicados deben ocupar varios rangos y una entrada con todos los elementos iguales debería finalizar en una sola partición. Después de la partición, si n - k está dentro del rango de iguales, devuelvo el pivote. De lo contrario, descarto el lado que no puede contener ese índice y repito de forma iterativa.

El invariante es que todo lo anterior a lt es menor, todo desde lt hasta i es igual, todo lo posterior a gt es mayor, y la sección intermedia desconocida sigue sin clasificar. Esto demuestra que la franja final de iguales tiene su intervalo de rango ordenado correcto. Por lo tanto, el lado conservado todavía contiene la respuesta.

El tiempo de ejecución esperado es O(n) porque un pivote aleatorio generalmente elimina una porción sustancial, aunque el peor de los casos sigue siendo O(n^2). El bucle y la partición in-place utilizan un espacio auxiliar de O(1). Indicaría que la función muta su entrada, la compararía con un oráculo de ordenamiento sobre arreglos generados e incluiría duplicados, datos con todos los elementos iguales, arreglos ordenados y en orden inverso, valores negativos, k = 1 y k = n."

Errores comunes

• Devolver el k-ésimo valor distinto → los duplicados son posiciones separadas en el contrato → Convierta directamente al índice ascendente n - k sin deduplicar.
• Usar el índice k o k - 1 en orden ascendente → la conversión de dirección es errónea → Verifique que k = 1 mapee a n - 1 y k = n mapee a 0.
• Afirmar que una solución con min-heap es O(n log n) → el heap nunca excede los k elementos → Indique tiempo O(n log k) y espacio O(k).
• Hacer recursión en ambas particiones → eso realiza el trabajo de quicksort e ignora el objetivo de un solo rango → Continúe únicamente en el intervalo que contiene target.
• Elegir siempre el primer o el último elemento como pivote → una entrada ordenada o manipulada puede crear repetidamente intervalos de tamaño n - 1 → Aleatorice el pivote y mantenga la advertencia del peor caso.
• Usar una partición de dos vías sin discutir los duplicados → los arreglos con muchos elementos iguales pueden avanzar muy lentamente → Cree una franja de iguales y devuelva el resultado cuando el objetivo caiga dentro de ella.
• Incrementar i tras intercambiar con gt → el valor entrante permanece sin clasificar y podría ser omitido → Mantenga i fijo hasta que dicho valor se clasifique.
• Afirmar que la aleatorización garantiza tiempo lineal → los pivotes desfavorables siguen existiendo → Especifique O(n) esperado, O(n^2) en el peor caso.
• Ocultar la mutación de la entrada → quienes invocan la función pueden depender del orden original → Indique el contrato de mutación o copie y rinda cuentas del espacio O(n).
• Probar solo dos ejemplos → los errores por un elemento (off-by-one), con duplicados y de partición permanecen ocultos → Compare contra el ordenamiento en casos límite, casos estructurados y entradas generadas.

Preguntas de seguimiento y cómo manejarlas

Pregunta de seguimiento 1: ¿Qué cambia si la entrada es un flujo continuo ilimitado (unbounded stream)?

Quickselect ya no es adecuado porque no existe un arreglo completo con acceso aleatorio. Mantenga un min-heap de como máximo k valores. Inserte elementos hasta que alcance k; a partir de ahí, reemplace la raíz solo cuando llegue un valor mayor. La raíz es el k-ésimo valor más grande visto hasta el momento. Las actualizaciones cuestan O(log k), las consultas cuestan O(1) y la memoria es O(k). Si k en sí cambia arbitrariamente, este estado puede ser insuficiente y el contrato necesitaría una estructura ordenada más rica o retener los datos.

Pregunta de seguimiento 2: ¿Qué sucede si la función debe preservar la entrada?

La adaptación más simple es working = nums.copy() y aplicar quickselect sobre working, lo que cambia el espacio auxiliar a O(n). Un heap de tamaño k preserva la entrada con un espacio de O(k) y puede ser mejor cuando k es pequeño. Ordenar completamente una copia es más sencillo cuando n es moderado o cuando muchas consultas de rango reutilizarán el resultado ordenado.

Pregunta de seguimiento 3: ¿Se puede garantizar tiempo lineal en el peor de los casos?

Median-of-medians elige un pivote que descarta una fracción constante en el peor de los casos, logrando una selección determinista en O(n). Su implementación y constantes son mayores, por lo que quickselect aleatorizado suele ser la opción práctica en entrevistas a menos que el requisito exija explícitamente un límite para el peor caso. Un heap acotado ofrece una alternativa predecible y más simple en O(n log k).

Pregunta de seguimiento 4: ¿Cómo aprovecharía el rango reducido de enteros?

Cree un arreglo de frecuencias para los valores desde -10,000 hasta 10,000, escanee nums, y luego recorra las frecuencias de mayor a menor mientras resta los conteos a k. El primer contenedor (bucket) que contenga el rango restante es la respuesta. Con un ancho de rango R = 20,001, esto cuesta tiempo O(n + R) y espacio O(R). Es determinista y maneja duplicados de forma natural, pero resulta inadecuado cuando el rango es grande o no está acotado.

Pregunta de seguimiento 5: ¿Qué pasa si el entrevistador pide los k elementos más grandes, ordenados?

Un solo estadístico de orden ya no constituye la salida completa. Un heap de tamaño k seguido del ordenamiento del heap cuesta tiempo O(n log k + k log k) y espacio O(k). Quickselect puede particionar alrededor del rango n - k, tras lo cual ordenar los k valores seleccionados cuesta un tiempo esperado de O(n + k log k). Elija según los requisitos de mutación, memoria, límites de peor caso y la necesidad de ordenar la salida.

Pregunta de seguimiento 6: ¿Cómo hacer que las fallas en pruebas aleatorizadas sean reproducibles?

Acepte un generador de números aleatorios inyectado o fije la semilla del generador antes de cada prueba. Registre la semilla, la entrada y k en caso de falla. Ejecute la misma entrada con varias semillas fijas y compare cada respuesta con el oráculo de ordenamiento. Esto separa un error algorítmico de una ruta de pivote particular mientras mantiene la reproducibilidad en integración continua.