Entrevista técnica de programación: ¿Cómo implementar un iterador reanudable y serializable?

Pregunta y contexto

Implemente un iterador con get_state() y set_state(): comience con una lista, luego extiéndalo a la iteración concurrente sobre múltiples fuentes y lecturas asíncronas. ¿Cómo define el estado, garantiza que no haya duplicados ni omisiones tras la recuperación y maneja la finalización, los fallos y las instantáneas inválidas?

Esto coincide con un registro público de entrevistas de programación de OpenAI cuya progresión abarca un iterador de listas, un iterador compuesto para múltiples archivos y una versión basada en corrutinas. Se adapta a roles de programación general, infraestructura, procesamiento de datos e ingeniería de aprendizaje automático. El desafío no radica en pausar un generador; consiste en codificar "lo que la próxima llamada debe devolver" como un estado verificable y serializable.

Qué evalúa el entrevistador

• ¿Define la semántica de entrada, salida, finalización y errores de next() en lugar de depender de hasNext()?
• ¿Separa los objetos de tiempo de ejecución del estado persistible?
• ¿Puede demostrar que la recuperación no repite ni omite ningún elemento entregado?
• ¿Hace un seguimiento del progreso de cada fuente y del orden de planificación global?
• ¿Maneja lecturas asíncronas, cancelaciones, reintentos y limpieza de recursos?
• ¿Prueba fuentes vacías, instantáneas inválidas, cambios en las fuentes y recuperación idempotente?

Preguntas aclaratorias antes de programar

• ¿Es una fuente una lista inmutable, un archivo de solo adición (append-only) o un flujo externo mutable? Si puede cambiar, la instantánea necesita una versión o una huella digital (fingerprint) de contenido.
• ¿La recuperación repite el último valor devuelto o comienza en el siguiente valor no devuelto? Esta respuesta utiliza lo segundo y avanza el cursor solo después de una entrega exitosa.
• ¿El orden multifuente es round-robin, orden temporal global o la primera fuente lista (any-ready-source-first)? La elección cambia los campos de estado y la prueba de equidad (fairness).
• ¿Debe get_state() sobrevivir a un cambio de proceso o de versión de esquema? Si es así, almacene únicamente escalares con versión e identificadores de fuentes, nunca descriptores de archivos, promesas u objetos generadores.

Una respuesta en 30 segundos

"Primero defino el punto de control como el elemento que devolverá la próxima llamada a next(). Una sola lista almacena un índice y la versión de la fuente; múltiples fuentes almacenan el cursor de cada una más el estado del planificador. next() avanza un cursor solo después de una entrega exitosa, por lo que restaurar el mismo estado devuelve el mismo elemento y no repite uno ya confirmado. La instantánea es un JSON versionado, validado contra las huellas digitales y límites de las fuentes antes de la restauración. La versión asíncrona separa la E/S en curso del estado recuperable, admite cancelación, limpieza y reintentos por fuente, y nunca serializa identificadores de tiempo de ejecución".

Respuesta detallada paso a paso

Paso 1: Definir la interfaz mínima y el punto de control

Utilice next(), get_state() y set_state(state) sin agregar hasNext(). Un iterador finito devuelve un resultado de finalización consistente o lanza la excepción de finalización acordada; los invocadores no deben sondear por adelantado para adivinar el estado.

Ubique el punto de control en el "siguiente elemento", no en el "último elemento". Una fuente de tipo lista puede almacenar {sourceId, version, index, done}. next() lee items[index] e incrementa el índice solo después de que el valor se haya entregado con éxito; un fallo de lectura deja el estado intacto para permitir el reintento.

class ListIterator:
    def __init__(self, items, source_id, version):
        self.items = items
        self.source_id = source_id
        self.version = version
        self.index = 0

    def next(self):
        if self.index == len(self.items):
            return {"done": True}
        value = self.items[self.index]
        self.index += 1
        return {"done": False, "value": value}

    def get_state(self):
        return {
            "schema": 1,
            "sourceId": self.source_id,
            "version": self.version,
            "index": self.index,
        }

    def set_state(self, state):
        if state["schema"] != 1 or state["sourceId"] != self.source_id:
            raise ValueError("incompatible state")
        if state["version"] != self.version or not 0 <= state["index"] <= len(self.items):
            raise ValueError("stale or invalid state")
        self.index = state["index"]

Paso 2: Declarar el invariante y demostrar la recuperación

El invariante principal es que index es igual al número de elementos entregados con éxito; el índice de la instantánea es igual al cursor en memoria; y la versión de la fuente no ha cambiado. next() avanza solo después de devolver un valor, mientras que set_state() acepta solo una versión coincidente y límites válidos, por lo que el mismo punto de control produce el mismo sufijo.

Si el contrato de negocio es de al menos una vez (at-least-once) en lugar de exactamente una vez (exactly-once), repetir el último elemento entre la entrega y el punto de control es aceptable, pero el estado debe incluir un marcador de confirmación (acknowledgement) o una clave de idempotencia. No mezcle ambas semánticas en un mismo contrato de set_state().

Paso 3: Extender a múltiples fuentes

Un iterador compuesto almacena un estado children[sourceId] independiente y el estado del planificador, como una cola round-robin, el conjunto de fuentes completadas y un número de secuencia. El esquema round-robin elige la siguiente fuente no finalizada; el orden global requiere guardar la cabecera precargada (prefetched head) de cada fuente para que las comparaciones puedan reproducirse después de la recuperación.

Una instantánea multifuente puede ser {schema, children: [{id, state}], scheduler: {kind, cursor}, emitted}. Valide primero la pertenencia y el orden de las fuentes, restaure los hijos a continuación y restaure el planificador al final. Un único recuento total no es suficiente porque el progreso de las fuentes diverge.

Paso 4: Hacer que el estado sea serializable y evolutivo

Persista únicamente escalares, arreglos y objetos con estructura JSON junto con una versión de esquema. Los descriptores de archivos, conexiones de red, bloqueos, promesas, pilas de generadores y clausuras son recursos de tiempo de ejecución; vuelva a abrirlos o reconstruirlos durante la recuperación en lugar de escribirlos en la instantánea.

Cuando una nueva versión lee una instantánea antigua, ejecute una migración explícita. Si la compatibilidad es incierta, rechace la recuperación y reinicie desde un límite seguro. Si el contenido de la fuente puede cambiar, almacene un ETag, longitud, suma de verificación de fragmentos o versión lógica para que el mismo índice no pueda hacer referencia silenciosamente a datos diferentes.

Paso 5: Agregar lecturas asíncronas, cancelación y reintentos

Un next() asíncrono devuelve una promesa y puede esperar varias fuentes concurrentemente, pero los compromisos de estado aún siguen el principio de "confirmar tras la entrega exitosa". La cancelación detiene nuevas lecturas, cierra archivos o recursos de red y deja los cursores no confirmados sin cambios.

Clasifique los fallos como E/S reintentable, errores de formato permanentes o cambios en la versión de la fuente. Aplique retroceso (backoff) y conserve el punto de control para errores reintentables; registre el ID de la fuente y el desplazamiento antes de finalizar una fuente con fallos permanentes; exija una revalidación o una nueva instantánea tras un cambio de fuente en lugar de cambiar de contenido silenciosamente.

Paso 6: Diseñar pruebas y complejidad

Para una sola fuente, verifique que next(), guardar, continuar y restaurar produzcan exactamente la misma secuencia. Pruebe con una lista vacía, índice límite, llamada a next después del último elemento, llamadas repetidas a set_state y una versión inválida. Las pruebas multifuente cubren la finalización temprana de una fuente, un orden de finalización diferente al orden de planificación, la cancelación y el fallo de una fuente individual.

Las operaciones next y de lectura/escritura de instantáneas de una sola fuente son O(1), con un tamaño de estado O(1). Con m fuentes, una instantánea es de al menos O(m). Un montículo (heap) o cabeceras precargadas pueden hacer que next sea O(log m); round-robin puede ser O(1) amortizado. La complejidad debe coincidir con el planificador elegido.

Ejemplo de respuesta de alta calidad

"Primero declararía el contrato de recuperación: la instantánea nombra el elemento que la siguiente llamada a next() debe devolver, y el cursor avanza solo después de una entrega exitosa. Un iterador de listas almacena el ID de la fuente, la versión y el índice, y luego valida el índice; un fallo de lectura no confirma el cursor, por lo que el reintento es seguro.

Para múltiples fuentes, cada hijo conserva su propio estado, mientras que el compuesto almacena un cursor round-robin, las fuentes completadas y la secuencia de salida. Si se requiere un orden global, también almacena la cabecera precargada de cada fuente. La instantánea es un JSON versionado; los descriptores de archivos, promesas y pilas de generadores se reconstruyen tras la recuperación.

El next asíncrono puede esperar E/S de forma concurrente, pero las confirmaciones de estado siguen ocurriendo tras la entrega. La cancelación cierra recursos y preserva el estado no confirmado. Los errores se clasifican como reintentables, permanentes o cambios de versión de la fuente. Las pruebas demuestran que una misma instantánea produce el mismo sufijo sin duplicados ni omisiones, y que cambiar el orden de finalización sigue cumpliendo el contrato de planificación. Las operaciones de una sola fuente son O(1), mientras que una instantánea de m fuentes es O(m), con una complejidad de next determinada por la planificación round-robin o mediante montículo".

Errores comunes

• Guardar el índice devuelto como el siguiente índice → la recuperación repite u omite un elemento → defina la semántica del punto de control y avance después de la entrega.
• Serializar descriptores de archivo u objetos generadores → los objetos no sobreviven al reinicio de un proceso → almacene escalares con versión y reconstruya los recursos.
• Sondear con hasNext() → una fuente asíncrona puede cambiar entre el sondeo y el consumo → permita que next() devuelva un valor o un resultado de finalización atómicamente.
• Guardar solo un recuento total para múltiples fuentes → el progreso por fuente y la posición del planificador desaparecen → guarde el estado de cada hijo y el estado del planificador.
• Avanzar tras un fallo de lectura → el reintento pierde datos → confirme únicamente después de una entrega exitosa.
• Restaurar sin comprobar la versión de la fuente → el mismo desplazamiento puede identificar contenido diferente → valide una huella digital, longitud o versión lógica y rechace el estado obsoleto.

Preguntas de seguimiento y respuestas

¿Qué sucede si se escribe una instantánea después de que una lectura tiene éxito pero antes de que se confirme la entrega?

Defina el límite de confirmación (acknowledgement boundary). Si la instantánea puede registrarse primero, el sistema es de al menos una vez (at-least-once) y cada elemento necesita una clave de idempotencia o marcador de confirmación. Para un comportamiento de exactamente una vez (exactly-once), coloque la confirmación de entrega y la confirmación del cursor en una única transacción recuperable o en un registro de confirmación externo.

¿Cómo mantener la equidad entre varias fuentes asíncronas listas?

Persista el último cursor seleccionado en un planificador round-robin y aváncelo después de cada entrega exitosa; la fuente más rápida no debe monopolizar la salida. Para un orden temporal global, utilice un min-heap de cabeceras de fuentes e incluya la cabecera del montículo y la regla de comparación en la instantánea.

¿Se puede reanudar de forma segura un archivo al que se le han añadido datos mientras estaba en pausa?

Solo si el comportamiento de adición exclusiva (append-only) forma parte del contrato. Almacene la versión, la longitud consumida y las sumas de verificación de fragmentos, y luego reanude desde la longitud anterior. Si el archivo puede ser reescrito o reordenado, rechace la discrepancia de versiones y cree una nueva instantánea.

¿Cómo cancelar next() mientras espera en varias operaciones de E/S?

Pase una señal de cancelación, detenga las lecturas que no hayan comenzado y cierre los recursos abiertos. Ninguna promesa no resuelta debe avanzar un cursor. Un next() posterior reintenta desde el punto de control original o devuelve un estado de cancelación explícito.