Entrevista técnica: Implementar un Radix Tree para enrutamiento por prefijos

Planteamiento y contexto

Se te proporcionan claves de cadena como /api, /api/users y /api/users/admin. Implementa un radix tree en el cual cada arista almacene una cadena no vacía y cada nodo pueda contener un valor. Debe admitir insert(key, value), get(key), longestPrefix(key) y delete(key). Las claves vacías solo se permiten como el valor raíz. El entrevistador busca la estructura de datos y el razonamiento, no una llamada a una biblioteca.

Qué evalúa el entrevistador

• ¿Mantienes el invariante de que toda etiqueta de arista que no sea la raíz sea no vacía y que los nodos hermanos tengan caracteres iniciales distintos?
• ¿Puedes dividir una arista en la primera discrepancia sin perder ningún subárbol ni valor?
• ¿Puedes distinguir la búsqueda exacta de la búsqueda por prefijo más largo?
• ¿Comprimes nodos unarios sin valor tras la eliminación y declaras la complejidad real en función de la longitud de la clave?

Preguntas de aclaración para hacer

Pregunta si las claves son bytes o puntos de código Unicode, si la coincidencia distingue mayúsculas de minúsculas, si las inserciones duplicadas reemplazan valores y si se requiere acceso concurrente. Pregunta si longestPrefix devuelve la clave coincidente, el valor o ambos. Una implementación orientada a bytes es más simple y hace que la complejidad dependa de los bytes; la normalización Unicode pertenece al exterior del árbol a menos que se requiera explícitamente. Si se requiere concurrencia, añade sincronización alrededor de la estructura en lugar de afirmar silenciosamente que el algoritmo es seguro para subprocesos.

Marco de respuesta en 30 segundos

Cada nodo almacena una etiqueta de arista, un valor opcional y nodos hijos indexados por su primer byte. Durante la inserción, compara la clave restante con la etiqueta del hijo. Si coinciden por completo, desciende; si coinciden parcialmente, divide el hijo en un nodo de prefijo común y dos nodos de sufijo. La búsqueda exacta tiene éxito solo cuando se consume toda la clave en un nodo con valor. La búsqueda por prefijo más largo recuerda el valor más profundo visto mientras se desciende. La eliminación borra un valor y une un nodo con su único hijo cuando el nodo no tiene valor.

Análisis detallado paso a paso

1. Establecer el invariante. La raíz no tiene etiqueta de arista. Todos los demás nodos tienen una etiqueta no vacía. Ningún par de hijos de un mismo nodo comienza con el mismo byte. Un nodo puede almacenar un valor incluso cuando también tiene hijos, por lo que /api y /api/users coexisten.
2. Insertar por prefijo común más largo. Sea p el prefijo común entre la clave restante y la etiqueta de un hijo. Si p está vacío, elige otro hijo. Si p es igual a la etiqueta del hijo, consúmela y realiza una llamada recursiva. Si p es más corto, crea un nuevo padre etiquetado como p, mueve el hijo antiguo bajo su sufijo y luego adjunta el nuevo sufijo de la clave o reemplaza el valor cuando la clave termina en la división.
3. Búsqueda. La búsqueda exacta consume una arista a la vez y falla ante una discrepancia o un hijo faltante. Para la búsqueda por prefijo más largo, registra primero el valor de la raíz y luego registra cada nodo con valor alcanzado antes de que termine la clave; devuelve el último registro.
4. Eliminar y comprimir. Borra el valor en el objetivo. Si el nodo no tiene valor y tiene un solo hijo, concatena las dos etiquetas y promueve los hijos de dicho hijo. Si tiene múltiples hijos o aún conserva un valor, mantén el nodo. Esto preserva el invariante de los nodos hermanos.
5. Complejidad. Con la selección de hijos mediante un hash map, cada operación compara como máximo los bytes de la clave de entrada, por lo que el tiempo es O(k) más la sobrecarga del hash map y el espacio es O(total de bytes de claves almacenadas). La compresión de rutas reduce los nodos unarios dispersos; no hace que una clave larga sea de tiempo constante.
6. Probar casos adversos. Prueba claves vacías y de un solo carácter, insertar una clave que es prefijo de una clave existente, insertar una clave que extiende una clave existente, dividir en medio de una arista, reemplazo por duplicados, eliminar una hoja, eliminar un valor de prefijo, eliminar la única clave y consultas de prefijo más largo sin coincidencia.

Ejemplo de respuesta de alta calidad

Representaría una arista como una cadena de bytes no vacía y mantendría los hijos ordenados por su primer byte. La única operación no trivial es la inserción: compara la etiqueta del hijo con la clave restante y divide en la primera discrepancia. Dicha división crea un nodo de prefijo común, conserva el sufijo y subárbol antiguos y adjunta el nuevo sufijo. La búsqueda sigue etiquetas completas; la búsqueda por prefijo más largo recuerda el nodo más profundo que posee un valor. La eliminación borra el valor y une un nodo sin valor con su único hijo. Aquí está la forma central de la división en pseudocódigo estilo Go:

type node struct {
    label string
    value any
    hasValue bool
    child map[byte]*node
}

// When common is shorter than child.label:
parent := &node{label: common, child: map[byte]*node{}}
oldSuffix := child.label[len(common):]
child.label = oldSuffix
parent.child[oldSuffix[0]] = child
parent.child[newSuffix[0]] = &node{label: newSuffix, value: v, hasValue: true}

En código de producción manejaría el caso en el que newSuffix esté vacío almacenando el valor en parent, y haría que la eliminación realice la unión solo cuando hasValue sea falso y exista exactamente un hijo. Probaría el invariante después de cada mutación, en lugar de simplemente asegurar que las búsquedas de ejemplo pasen.

Errores comunes

• Tratar un radix tree como nodos de trie de un solo carácter → se pierde la compresión de rutas → almacena etiquetas de aristas no vacías y compara la etiqueta completa.
• Dividir una arista pero descartar su valor antiguo o sus hijos → las claves existentes desaparecen → mueve el nodo antiguo bajo su sufijo antes de adjuntar el nuevo sufijo.
• Devolver el primer valor coincidente para la búsqueda por prefijo más largo → una ruta más específica pierde → mantén actualizada la opción candidata en cada nodo con valor.
• Unir un nodo que aún posee un valor → una clave más corta se elimina accidentalmente → une únicamente nodos unarios sin valor.
• Afirmar que la búsqueda es O(1) → la clave aún debe compararse → declara O(k) en función de la longitud de la clave y explica los costos del mapa de hijos.

Preguntas de seguimiento y respuestas

¿Qué cambia si las claves no distinguen mayúsculas de minúsculas?

Normaliza las claves antes de la inserción y la búsqueda utilizando una regla documentada, como minúsculas ASCII. No normalices únicamente durante la búsqueda; de lo contrario, dos grafías pueden ocupar rutas inconsistentes. El plegamiento de mayúsculas/minúsculas y la normalización de Unicode deben ser una política independiente y especificada.

¿Cómo admitirías segmentos de ruta con comodines?

Añade una regla de precedencia explícita, por ejemplo: arista estática antes que arista de parámetro y esta antes que arista comodín universal (catch-all). El invariante del radix aún maneja prefijos literales, pero la coincidencia se convierte en una búsqueda sobre tipos de aristas, así que especifica el número máximo de ramas con comodines y prueba rutas ambiguas.

¿Se puede hacer que el árbol sea seguro para lecturas y escrituras concurrentes?

Utiliza un bloqueo de lectura-escritura (read-write lock) o instantáneas copy-on-write. Una solución libre de bloqueos (lock-free) requiere un diseño de recuperación de memoria; el simple uso de una raíz atómica no hace que las divisiones y uniones in situ sean seguras. Mantén separados el invariante algorítmico y la política de sincronización.