Entrevista técnica de código: Muestreo uniforme de un cuadrado y escaneo del subarreglo creciente más largo

Enunciado y alcance

El registro público de la entrevista divide el ejercicio en dos tareas breves: llamar a una función rand01() que retorna un valor uniforme entre 0 y 1 para muestrear un punto dentro de un cuadrado de lado side, y luego encontrar el segmento contiguo estrictamente creciente más largo de un arreglo. Este artículo sitúa la esquina inferior izquierda del cuadrado en (0, 0), trata la fuente aleatoria como [0, 1) y retorna un resultado vacío para un arreglo vacío.

Qué está evaluando el entrevistador

El ejercicio combina modelado de probabilidad, mapeo de rangos, un invariante de una sola pasada y una semántica de resultados precisa. Las notas de clase de Cornell explican que dos variables uniformes independientes en [0,1] forman un punto uniforme respecto al área en el cuadrado unitario; el material de probabilidad en cuadrados del MIT ofrece la misma interpretación de área. El escaneo evalúa si el candidato preserva la contigüidad, trata la igualdad como una ruptura y elige un criterio determinista para el desempate.

Preguntas aclaratorias para hacer

1. ¿rand01() es cerrado o semiabierto? Esta respuesta asume [0, 1).
2. ¿Está trasladado el cuadrado? Esta respuesta comienza en el origen; la traslación agrega desplazamientos (offsets).
3. ¿El incremento es estricto? Esta respuesta requiere a[i] > a[i-1].
4. ¿Cuál secuencia más larga gana en caso de empate? Esta respuesta retorna el inicio más temprano.
5. ¿Se requiere deduplicación o aleatoriedad criptográfica? El ejercicio base no requiere ninguna de las dos.

Una respuesta en 30 segundos

“Llamo a rand01() de forma independiente dos veces y multiplico los valores por la longitud del lado. Coordenadas uniformes e independientes hacen que la probabilidad de cada rectángulo pequeño sea igual a su área. Para el arreglo, mantengo el inicio de la secuencia estrictamente creciente actual y los mejores índices de inicio/fin. Un valor no creciente reinicia el inicio actual; actualizo la respuesta solo cuando la secuencia actual es estrictamente más larga. El muestreo es O(1), el escaneo es O(n) y el espacio adicional es O(1). Probaré límites, igualdad, entrada vacía, arreglos monótonos y empates.”

Solución paso a paso

1. Deducir la muestra uniforme

Sean U y V variables uniformes independientes en [0,1). Para cualquier rectángulo alineado con los ejes [a,b) × [c,d), la probabilidad de caer dentro de él es (b-a)(d-c), exactamente su área. Por lo tanto, (side × U, side × V) es uniforme en el cuadrado. Reutilizar una sola extracción haría que las coordenadas estuvieran perfectamente correlacionadas y colocaría cada punto sobre una diagonal.

2. Mantener el invariante del escaneo lineal

En el índice i, currentStart es el inicio de la secuencia estrictamente creciente más larga que termina en i; bestStart y bestEnd describen la mejor secuencia en el prefijo. Si a[i] > a[i-1], extiende la secuencia. De lo contrario, establece currentStart = i. Actualiza solo ante una longitud estrictamente mayor, lo que conserva la secuencia más temprana en caso de empates.

3. Implementación de referencia

from typing import Callable


def sample_square(side: float, rand01: Callable[[], float]) -> tuple[float, float]:
    if side < 0:
        raise ValueError("side must be non-negative")
    u, v = rand01(), rand01()
    if not (0 <= u < 1 and 0 <= v < 1):
        raise ValueError("rand01 must return values in [0, 1)")
    return side * u, side * v


def longest_increasing_run(values: list[int]) -> tuple[int, int] | None:
    if not values:
        return None
    current_start = best_start = best_end = 0
    for i in range(1, len(values)):
        if values[i] <= values[i - 1]:
            current_start = i
        current_length = i - current_start + 1
        best_length = best_end - best_start + 1
        if current_length > best_length:
            best_start, best_end = current_start, i
    return best_start, best_end

4. Complejidad y pruebas

El muestreo realiza dos llamadas a la fuente aleatoria, por lo que el tiempo y el espacio adicional son O(1). El escaneo visita cada elemento una vez, tomando un tiempo de O(n) y un espacio adicional de O(1); materializar los valores retornados costaría adicionalmente O(k). Utiliza una secuencia fija de rand01 para probar el mapeo de coordenadas, [1, 2, 2, 3] para probar la condición estricta y [5, 4, 3] para probar la respuesta de un solo elemento.

Respuesta modelo

“Modelo las dos coordenadas como variables uniformes independientes: llamo a rand01 dos veces y escalo por la longitud del lado. Eso hace que la probabilidad de cualquier rectángulo pequeño sea igual a su área. Encuentro la secuencia creciente con un puntero de inicio y los mejores índices en un escaneo lineal, reiniciando ante un valor no creciente y actualizando solo ante una secuencia estrictamente más larga, de modo que los empates elijan el segmento más temprano. El muestreo es O(1), el escaneo es O(n) y ambos usan O(1) de espacio adicional. Verificaré el contrato de la fuente aleatoria, lados negativos, valores iguales y arreglos vacíos.”

Errores comunes

• Reutilizar una sola extracción aleatoria → las coordenadas quedan correlacionadas y yacen sobre una diagonal → extraer de forma independiente dos veces.
• Asumir un rango arbitrario para rand01 → las coordenadas pueden salir del cuadrado → declarar y validar el contrato de [0,1).
• Ordenar o usar programación dinámica para una secuencia contigua → se pierde el orden o se añade espacio → mantener un único estado de escaneo.
• Usar >= para el incremento → los valores iguales se unen incorrectamente → exigir >.
• Sobrescribir ante longitudes óptimas iguales → el comportamiento ante empates se vuelve accidental → actualizar solo ante una longitud estrictamente mayor.
• Escanear el arreglo de forma recursiva → la profundidad de la pila crece con el tamaño de la entrada → usar iteración.

Preguntas de seguimiento y extensiones

¿Cómo se muestrea un rectángulo o un cuadrado trasladado?

Usa x = xmin + (xmax-xmin)U y y = ymin + (ymax-ymin)V para un rectángulo. Una traslación simplemente agrega un desplazamiento a ambas coordenadas y preserva la independencia.

¿Cómo diagnosticarías la uniformidad?

Divide el cuadrado en celdas de igual área, extrae muchas muestras y compara los recuentos de las celdas. Esto es un diagnóstico, no una demostración; una semilla fija es útil para pruebas de regresión, pero no garantiza uniformidad visual.

¿Qué pasa si se deben retornar todas las secuencias más largas?

Mantén la longitud óptima actual y una lista. Limpia la lista ante una secuencia más larga y agrégala ante una secuencia de igual longitud; el espacio adicional es O(r), donde r es el número de secuencias empatadas.

¿Qué pasa si el arreglo llega como un flujo (stream)?

Conserva únicamente el valor anterior, el inicio actual, los mejores índices y la posición actual. Emite el mejor intervalo al final del flujo, con una memoria independiente de la longitud total de la entrada.