Consigna y contexto
Implementa un ART que almacene claves de bytes de longitud variable y valores con inserción, búsqueda exacta, coincidencia del prefijo más largo y eliminación. Los nodos se adaptan entre Node4, Node16, Node48 y Node256; la compresión de rutas debe preservar la semántica de las claves. Esta es una pregunta de coding sobre árboles comprimidos, índices y diseño de memoria.
Qué evalúa el entrevistador
- Manejo de rutas comprimidas, terminación de claves y bytes arbitrarios en lugar de solo caracteres.
- Mantenimiento de transiciones ascendentes y descendentes entre los cuatro tipos de nodo.
- Implementación de coincidencia del prefijo más largo y distinción de coincidencias exactas respecto de valores de ancestros.
- Demostración de que la eliminación preserva los invariantes de compresión.
- Explicación de la complejidad, los balances de memoria y la concurrencia.
Preguntas aclaratorias para hacer
- ¿Son las claves cadenas de bytes opacas y pueden contener bytes cero?
- ¿Puede un nodo interno contener un valor, o solo las hojas?
- ¿Qué longitud de prefijo y resto debe devolver la búsqueda del prefijo más largo?
- ¿Debe la eliminación reducir el tamaño inmediatamente o se puede diferir la liberación de memoria?
- ¿Se requiere lectura lock-free o publicación de snapshots?
Una respuesta en 30 segundos
“Comparo bytes opacos y almaceno un prefijo comprimido más un valor de terminación en los nodos internos. Los nodos dispersos usan Node4/16; los densos ascienden a Node48/256. La eliminación desciende de tipo y fusiona una ruta de un solo hijo sin valor. La búsqueda exacta consume la clave completa; la búsqueda del prefijo más largo registra el nodo con valor más cercano. Demostraría los invariantes de un solo hilo contra un mapa de referencia antes de agregar bloqueos o snapshots inmutables.”
Respuesta detallada
Paso 1: Definir nodos y hojas
Un nodo interno almacena un prefijo comprimido, su longitud, un valor opcional y los hijos indexados por el siguiente byte. Una hoja almacena la clave completa o una referencia de valor única, lo que maneja el caso de que una clave sea prefijo de otra.
Node { prefix, prefixLen, hasValue, value, children }
Leaf { key, value }La longitud del prefijo es explícita porque las claves son bytes arbitrarios, no cadenas terminadas en null.
Paso 2: Insertar y dividir
Compara el prefijo del nodo con la clave restante. Si coincide, continúa o actualiza el valor. Si diverge, crea un padre que contenga el prefijo común y vincula el nodo antiguo y la nueva hoja bajo sus bytes divergentes. Si la nueva clave termina en el prefijo común, activa la bandera de valor del padre.
Paso 3: Elegir estructuras adaptativas
Node4 y Node16 mantienen arreglos compactos de claves y punteros; la búsqueda puede escanearlos o usar comparación vectorial. Node48 mapea los 256 bytes posibles a 48 ranuras de punteros, evitando 256 punteros residentes. Node256 indexa directamente por byte. Asciende copiando hijos sin perder el estado del prefijo o del valor.
Paso 4: Búsqueda exacta y del prefijo más largo
La búsqueda exacta debe consumir cada byte de la clave y coincidir con hasValue o una clave de hoja igual. La búsqueda del prefijo más largo registra un candidato cada vez que un nodo tiene un valor, luego continúa a través del siguiente byte hasta fallar o agotarse y devuelve el último candidato y su longitud.
Paso 5: Eliminar y reducir
Después de eliminar un valor, remueve un nodo que no tenga hijos. Si un nodo sin valor tiene un hijo, fusiona su prefijo y el byte de arista en el hijo. Desciende Node256, Node48, Node16 y Node4 según los umbrales de conteo de hijos documentados. Preserva la clave completa de la hoja durante las fusiones.
Paso 6: Invariantes y complejidad
Concatenar prefijos, bytes de arista y una hoja a lo largo de cualquier ruta de raíz a hoja debe reproducir la clave original. Un nodo interno no puede tener bytes de arista duplicados; hasValue significa que una clave termina exactamente allí. Con una longitud de clave L, la búsqueda es O(L); las estructuras adaptativas evitan asignar 256 ranuras para nodos dispersos.
Paso 7: Probar y añadir concurrencia
Compara operaciones aleatorias de inserción, búsqueda, eliminación y prefijo más largo con un mapa de referencia. Incluye claves vacías, bytes cero, claves con prefijos compartidos y las 256 ramas. Comienza versiones concurrentes con un bloqueo de lectura/escritura; solo después considera copy-on-write, epochs o RCU, ya que la liberación debe ser segura antes de exponer punteros lock-free.
Respuesta modelo
“Trato las claves como cadenas de bytes opacas. Los nodos llevan prefijos comprimidos, valores de terminación opcionales e hijos. Las coincidencias parciales dividen a un padre de prefijo común; los conteos de hijos ascienden a Node4, 16, 48 y 256, mientras que la eliminación desciende y fusiona rutas de un solo hijo. La búsqueda exacta consume toda la clave; la búsqueda del prefijo más largo recuerda el nodo con valor más cercano.
Cada ruta debe reconstruir la clave original. Las pruebas aleatorias se comparan contra un mapa y cubren bytes cero, claves vacías, claves prefijo y ramas densas. Tras la corrección monohilo, usa un bloqueo; un diseño copy-on-write o lock-free también necesita epoch o una liberación segura equivalente.”
Errores comunes
- Tratar claves como caracteres → fallan claves binarias y bytes cero → compara longitudes de bytes y valores.
- Olvidar valores internos → las claves que son prefijos no coinciden → mantén
hasValue. - Dar 256 punteros a Node48 → se pierden los ahorros de memoria dispersa → usa un mapa de índices.
- Limpiar valores sin fusionar → deja rutas vacías → reduce el tamaño según los umbrales.
- Ignorar candidatos ancestros → la búsqueda del prefijo más largo pierde coincidencias → recuerda el último nodo con valor.
- Publicar punteros directos sin liberación segura → los lectores usan memoria liberada → comienza con bloqueos, luego epochs/RCU.
Preguntas de seguimiento y respuestas
Pregunta de seguimiento 1: ¿Por qué no usar siempre Node256?
La mayoría de los nodos son dispersos, por lo que 256 ranuras desperdician memoria. Las estructuras adaptativas equilibran las regiones dispersas y densas.
Pregunta de seguimiento 2: ¿Qué sucede si una clave es prefijo de otra?
Almacena el valor de la clave más corta en el nodo interno y mantén los hijos para la clave más larga.
Pregunta de seguimiento 3: ¿Cuándo se fusiona tras una eliminación?
Fusiona un nodo sin valor que tenga un solo hijo concatenando su prefijo y el byte de arista, preservando la clave de la hoja.
Pregunta de seguimiento 4: ¿Cómo publicarías snapshots concurrentes?
Usa copy-on-write para una nueva raíz inmutable y libera árboles antiguos con epochs o conteo de referencias.