Prompt y alcance
Implementa una cola de prioridades con add(task, priority), update(task, priority), remove(task) y pop(). Las prioridades iguales deben devolverse en orden de inserción; update y remove deben ser O(log n) amortizado. Explica cómo se manejan las entradas obsoletas del heap.
Esto evalúa la corrección de una cola de prioridades mutable, no solo si puedes llamar a una API de heap. La documentación de heapq de Python destaca el ordenamiento estable, las tareas no comparables, las actualizaciones de prioridad y la eliminación pendiente como las partes difíciles. Un diseño común utiliza un contador para los desempates, un mapa para la ubicación y eliminación perezosa para preservar el invariante del heap.
Qué está evaluando el entrevistador
Primero, ¿puedes escribir la clave completa del heap: prioridad, secuencia de inserción y tarea? Segundo, ¿pueden las actualizaciones y eliminaciones evitar corromper directamente el heap? Tercero, ¿puedes manejar tareas duplicadas, una cola vacía, una raíz obsoleta y entradas de basura de larga duración?
Preguntas para clarificar antes de responder
- ¿Son las prioridades números u objetos comparables? Asume enteros comparables, con los valores más pequeños primero.
- ¿Son únicos los ID de tarea? Asume que sí; un
addduplicado es una actualización o un error explícito. - ¿Se requiere un ordenamiento estable? Asume que las prioridades iguales utilizan el orden de primera inserción.
- ¿Puede la eliminación perezosa retener memoria temporalmente? Sí, con una política de limpieza y reconstrucción.
- ¿Son las llamadas concurrentes? Asume un solo hilo; la concurrencia necesita un bloqueo externo o un contenedor seguro.
Un marco de respuesta de 30 segundos
“Almacenaría [priority, sequence, task] en un min-heap y mapearía cada ID de tarea a su entrada válida actual. Una actualización marca la entrada antigua como eliminada e inserta una nueva entrada con una nueva secuencia; remove también marca una entrada como obsoleta. pop omite las entradas obsoletas hasta que encuentra la actual. La secuencia proporciona desempates estables, el mapa proporciona búsqueda O(1), las operaciones de heap son O(log n) y la reconstrucción periódica limita el espacio de las entradas perezosas.”
Análisis detallado paso a paso
Paso 1: Definir invariantes y contratos de operación
La raíz debe ser el menor (priority, sequence) entre las entradas válidas. El mapa almacena la entrada actual para cada tarea. Una tarea tiene como máximo una entrada válida; las entradas obsoletas pueden permanecer en el heap pero nunca pueden devolverse. Define si un pop vacío genera un error o devuelve un valor vacío.
Paso 2: Elegir entradas de heap comparables
Usa [priority, sequence, task]. El sequence monotónico hace que las prioridades iguales sean comparables sin comparar objetos de tarea. Si la dirección de prioridad del negocio se invierte, niégala o envuelve un comparador de manera consistente; no mezcles reglas entre operaciones.
Paso 3: Implementar add y update
El primer add asigna una secuencia y escribe la entrada tanto en el mapa como en el heap. update verifica la existencia, marca la entrada antigua como REMOVED, inserta una nueva entrada y reemplaza el puntero del mapa. No hay búsqueda en el heap ni sift manual, por lo que la operación sigue siendo O(log n).
add(task, priority):
if task is active: mark old entry removed
entry = [priority, next(sequence), task]
current[task] = entry
heappush(heap, entry)Paso 4: Implementar remove con eliminación perezosa
remove elimina la tarea del mapa y reemplaza el campo de tarea en su entrada de heap con REMOVED. Eliminar directamente del arreglo rompería el heap y requeriría una reparación adicional. La eliminación perezosa toca una entrada conocida por mutación, a costa de basura temporal.
Paso 5: Hacer que pop omita las entradas obsoletas
Extrae repetidamente la raíz con pop. Si está marcada como REMOVED, continúa. Si el mapa no apunta a la entrada exacta que se está extrayendo, fue reemplazada por una actualización, así que omítela. Para una entrada válida, elimina la clave del mapa y devuelve la tarea. Genera el error de cola vacía solo después de que el heap se haya agotado.
Paso 6: Demostrar la complejidad y los límites amortizados
add, update y remove realizan una inserción en el heap o una marca en tiempo constante, lo que da O(log n) o un marcado O(1). Cada entrada obsoleta se extrae como máximo una vez, por lo que el trabajo omitido se amortiza a la actualización o eliminación que la creó. Si las actualizaciones continúan sin operaciones pop, el espacio crece y se requiere una reconstrucción.
Paso 7: Diseñar la reconstrucción y el control de espacio
Cuando la longitud del heap supera un múltiplo fijo de entradas válidas, como 2x, o las entradas obsoletas pasan un umbral, retén las entradas actuales del mapa y reconstruye el heap. La reconstrucción cuesta O(n), pero los activadores de baja frecuencia mantienen el costo amortizado acotado. Con un límite de tareas conocido, la limpieza también se puede ejecutar después de un lote de actualizaciones.
Paso 8: Cubrir pruebas de límites
Prueba una cola vacía, prioridades iguales estables, actualizaciones repetidas, remove seguido de pop, una entrada antigua actualizada que llega a la raíz, todas las entradas volviéndose obsoletas, objetos de tarea no comparables y resultados idénticos antes y después de la reconstrucción. Realiza pruebas diferenciales de operaciones aleatorias contra un modelo simple de diccionario más lista ordenada.
Compensaciones y límites
Compensación 1: Eliminación perezosa o heap indexado
La eliminación perezosa es corta y de bajo riesgo para una implementación general. Un heap indexado elimina de inmediato y controla el espacio, pero mantener las posiciones durante los intercambios es más propenso a errores. Elige un heap indexado solo cuando la tasa de eliminación y los límites de memoria lo justifiquen.
Compensación 2: ¿Puede desbordarse la secuencia?
Los enteros de ancho fijo pueden desbordarse y romper el ordenamiento estable. Usa un entero no acotado o vuelve a numerar todas las entradas activas durante una reconstrucción segura. Nunca reinicies el contador mientras las entradas activas aún dependan de valores antiguos.
Compensación 3: Error o valor vacío
Las bibliotecas comúnmente generan una excepción clara de cola vacía, lo que permite a los llamadores distinguir "ninguna tarea" de una tarea cuyo valor es nulo. Si una API devuelve un valor vacío, documenta la ambigüedad y no permitas un valor de tarea en conflicto.
Simulacros de fallos y plan de evolución
Simulacro 1: Actualizar repetidamente una tarea
Actualiza una tarea 10,000 veces, luego haz pop y verifica que la última prioridad se devuelva exactamente una vez. Observa el crecimiento de entradas obsoletas, activa una reconstrucción y vuelve a verificar el invariante del heap.
Simulacro 2: Operaciones mixtas aleatorias
Genera operaciones aleatorias de add, update, remove y pop y compáralas con un modelo de diccionario más lista ordenada. Concéntrate en el orden de secuencia para prioridades iguales y en asegurarte de que las entradas antiguas actualizadas nunca se filtren.
Simulacro 3: Errores y límites de recursos
Llama a update/remove para tareas inexistentes, haz pop en una cola vacía y activa la reconstrucción en un umbral de memoria. Verifica tipos de error estables, que no haya tareas perdidas y que no se exponga ningún estado parcialmente reconstruido a los llamadores.
Errores comunes y seguimiento
Error 1: Almacenar solo prioridad y tarea
Los objetos de tarea pueden no ser comparables, lo que hace que fallen las comparaciones de igual prioridad. Agrega una secuencia estable o un contenedor no comparable.
Error 2: Mutar una entrada del heap in situ para update
La entrada puede no estar ya en la posición correcta, violando el invariante del heap. Marca la entrada antigua como obsoleta e inserta una nueva.
Error 3: Llamar a remove de arreglo para la eliminación
La búsqueda es O(n), seguida de la reparación del heap. Usa el mapa para ubicar la entrada y marcarla como obsoleta.
Error 4: Verificar solo el campo de tarea en pop
Una entrada antigua actualizada aún puede llevar el mismo ID de tarea. Confirma que el objeto extraído sea la entrada actual del mapa.
Error 5: Ignorar el espacio de entradas obsoletas
La eliminación perezosa todavía consume memoria. Establece un umbral de reconstrucción y monitorea la longitud del heap, el recuento de entradas válidas y la proporción de obsoletas.
Error 6: Dejar la dirección de prioridad implícita
Un min-heap devuelve el valor más pequeño primero. Si los números más grandes significan una mayor prioridad comercial, define la conversión en el contrato para que add y pop coincidan.