Implementar un Trie con Insert, Search, Prefix y Delete

Prompt y contexto aplicable

Implementa un Trie que almacene un conjunto de palabras con cuatro operaciones:

• insert(word) añade una palabra y es idempotente cuando la palabra ya existe.
• search(word) devuelve si esa palabra completa está almacenada.
• startsWith(prefix) devuelve si esa ruta de prefijo existe; para un prefijo no vacío, esto significa que al menos una palabra almacenada lo contiene.
• delete(word) elimina la palabra completa y devuelve si existía.

Asume que insert, search y delete reciben palabras no vacías en minúsculas en inglés. startsWith también acepta el prefijo vacío, el cual devuelve true porque esta API define la ruta raíz como el prefijo vacío incluso antes de cualquier inserción. La implementación es en memoria, monohilo (single-threaded), y no enumera sugerencias, no clasifica resultados, no persiste datos ni normaliza Unicode. La validación de entradas queda fuera de la clase.

Este es un problema representativo de entrevistas de código para roles de ingeniería de software. La tarea central es modelar prefijos compartidos y distinguir entre “esta ruta existe” y “una palabra termina aquí”. Agregar eliminación expone si el candidato realmente entiende ese modelo: eliminar app debe preservar apple, mientras que eliminar el último sufijo único puede liberar sus nodos.

Qué evalúa el entrevistador

La primera señal es deducir la estructura a partir de las operaciones. Un conjunto hash maneja la pertenencia exacta, pero una consulta de prefijo necesitaría inspeccionar las palabras almacenadas o mantener otro índice. Un Trie convierte cada prefijo en una ruta desde la raíz, por lo que el costo de consulta depende de la longitud de la entrada en lugar del número de palabras almacenadas.

La segunda señal es el marcador terminal. La ruta para app existe después de insertar apple, pero search("app") sigue siendo falso hasta que ese nodo se marque como una palabra completa. startsWith("app") solo necesita la ruta. Una función auxiliar de recorrido puede servir para ambas operaciones mientras sus condiciones finales se mantienen distintas.

La tercera señal es la seguridad en la eliminación. Limpiar un marcador terminal es suficiente para una eliminación lógica. La poda física es opcional y solo puede avanzar hacia arriba mientras el nodo hijo sea no terminal y no tenga hijos. Esta regla preserva tanto las palabras más largas como las más cortas que comparten la ruta eliminada.

Finalmente, el entrevistador busca honestidad en la complejidad y en las pruebas. Un nodo respaldado por un mapa evita asignar 26 posiciones para hijos en cada nodo disperso, pero las operaciones del mapa utilizan las suposiciones de rendimiento promedio del runtime de su lenguaje. La eliminación también mantiene una pila de ruta de O(L); afirmar que usa espacio auxiliar constante contradiría el código.

Preguntas para clarificar antes de responder

• ¿Qué caracteres están permitidos? Las minúsculas de a-z permiten un arreglo de 26 posiciones. Unicode, mayúsculas y minúsculas mixtas o un alfabeto disperso favorecen un mapa y pueden requerir un contrato de normalización.
• ¿Se cuentan las inserciones duplicadas? Este problema almacena un conjunto (set), por lo que una segunda inserción es idempotente. Un multiconjunto (multiset) necesitaría contadores terminales y de prefijos.
• ¿Qué debe reportar la eliminación? Devuelve false para una palabra inexistente y true solo cuando se elimina una palabra completa almacenada.
• ¿Debe la eliminación liberar nodos? Aquí realiza una poda segura. Si las eliminaciones son raras y la memoria no está restringida, limpiar el marcador terminal es más simple y sigue siendo correcto.
• ¿Es válida una palabra vacía? No. Se permite el prefijo vacío, pero la cadena vacía no se puede insertar ni buscar como una palabra en este contrato.
• ¿Los resultados de prefijo se enumeran o simplemente se detectan? Esta API devuelve un booleano. Listar coincidencias añade recorrido de subárboles y un costo sensible a la salida.
• ¿Se requiere concurrencia? No. Lecturas y escrituras concurrentes requerirían un diseño con sincronización o instantáneas inmutables (immutable snapshots).

Estructura de respuesta en 30 segundos

“Representaré cada prefijo como una ruta desde una raíz. Cada nodo mapea el siguiente carácter a un hijo y tiene un flag isWord. Insert crea los nodos faltantes y marca el nodo final. Search recorre la ruta y verifica ese flag; la búsqueda por prefijo solo requiere la ruta. Delete primero registra la ruta, limpia el flag final y luego elimina nodos hacia atrás solo mientras no tengan hijos y no sean el final de otra palabra. Cada operación toma un tiempo esperado de O(L) con hijos basados en mapas, el almacenamiento total es O(C) y delete utiliza O(L) de espacio auxiliar.”

Respuesta detallada paso a paso

Una lista o conjunto no ordenado de palabras hace que una consulta de prefijo dependa del número de palabras. Un arreglo ordenado puede encontrar la primera coincidencia de prefijo posible con búsqueda binaria y resulta atractivo para un diccionario estático de solo lectura, pero la inserción y la eliminación requieren desplazamientos o reconstrucción. Un Trie asume la sobrecarga de nodos por carácter para soportar directamente las cuatro operaciones en línea.

Usa este invariante:

Para cada palabra almacenada, sus caracteres forman una ruta de la raíz al nodo, y isWord es verdadero en un nodo exactamente cuando la ruta que deletrea ese nodo es una palabra completa almacenada.

El invariante explica todas las operaciones. Insert extiende una ruta y activa su marcador final. Search requiere tanto la ruta como el marcador. Prefix search requiere únicamente la ruta. Delete desactiva exactamente un marcador y elimina un sufijo solo cuando ninguna palabra restante pueda usarlo.

class TrieNode {
  readonly children = new Map<string, TrieNode>()
  isWord = false
}

class Trie {
  private readonly root = new TrieNode()

  insert(word: string): void {
    let node = this.root

    for (const character of word) {
      let child = node.children.get(character)
      if (!child) {
        child = new TrieNode()
        node.children.set(character, child)
      }
      node = child
    }

    node.isWord = true
  }

  search(word: string): boolean {
    return this.walk(word)?.isWord ?? false
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== undefined
  }

  delete(word: string): boolean {
    let node = this.root
    const path: Array<[TrieNode, string, TrieNode]> = []

    for (const character of word) {
      const child = node.children.get(character)
      if (!child) return false

      path.push([node, character, child])
      node = child
    }

    if (!node.isWord) return false
    node.isWord = false

    for (let index = path.length - 1; index >= 0; index -= 1) {
      const [parent, character, child] = path[index]
      if (child.isWord || child.children.size > 0) break
      parent.children.delete(character)
    }

    return true
  }

  private walk(text: string): TrieNode | undefined {
    let node = this.root

    for (const character of text) {
      const child = node.children.get(character)
      if (!child) return undefined
      node = child
    }

    return node
  }
}

La eliminación es más fácil de verificar con dos contraejemplos. Si app y apple están almacenados, eliminar app limpia el marcador en la segunda p pero detiene la poda porque ese nodo tiene como hijo a l. apple sigue siendo buscable. Si app y apt están almacenados, eliminar app elimina solo la p final; la poda luego se detiene en el nodo compartido ap porque todavía tiene como hijo a t.

La corrección se deduce por inducción. El Trie vacío satisface el invariante. Insert modifica solo una ruta y su marcador final. Search y prefix search no mutan el estado. Una eliminación exitosa primero remueve exactamente el marcador objetivo. Cada nodo podado es no terminal y no tiene hijos, por lo que no puede representar una palabra almacenada ni conducir a una. Eliminarlo preserva todas las rutas almacenadas restantes; detenerse en el primer nodo terminal o de ramificación preserva el prefijo compartido.

Sea L la longitud de la entrada y C el número de nodos de caracteres asignados actualmente. Bajo la búsqueda promedio en mapas, insert, search y prefix search toman un tiempo esperado de O(L). Delete recorre hacia adelante y poda como máximo las mismas L aristas, por lo que también toma un tiempo esperado de O(L). El Trie utiliza un espacio de O(C), acotado por la suma de caracteres de prefijos distintos almacenados; la ruta de delete utiliza un espacio auxiliar de O(L).

Para un alfabeto fijo en minúsculas, TrieNode | undefined[26] proporciona acceso indexado directo y trabajo predecible por carácter, pero reserva 26 referencias por nodo. Un mapa almacena solo las aristas existentes y maneja un alfabeto más amplio, con la sobrecarga de hashing y de objetos. La respuesta debe elegir según el alfabeto y la densidad, sin afirmar que una representación siempre gana.

La validación debe verificar transiciones de estado, no solo una búsqueda. Comienza con startsWith("") === true, search("") === false y la eliminación en un Trie vacío. Inserta app, apple y apt; reinserta app; distingue search("ap") de startsWith("ap"); elimina app mientras preservas apple; rechaza una segunda eliminación; luego elimina las palabras restantes y confirma que sus prefijos desaparezcan. Una prueba aleatorizada puede comparar todas las operaciones con una referencia simple basada en Set<string> y escanear el conjunto para consultas de prefijo.

Si el requisito es solo la pertenencia exacta, un conjunto hash es más corto y generalmente preferible. Si el diccionario es estático y está ordenado, la búsqueda binaria puede responder la existencia de un prefijo sin un almacenamiento pesado en nodos. Si cadenas largas de un solo hijo dominan la memoria, un radix tree comprime esas cadenas a costa de una lógica de división y fusión más compleja.

Respuesta de muestra de alta calidad

“Primero confirmaría el alfabeto, la semántica de duplicados y si la eliminación debe liberar memoria. Asumiré palabras no vacías en minúsculas, semántica de conjuntos, un prefijo vacío que coincide y poda segura al eliminar.

Cada nodo del Trie almacena sus aristas salientes de caracteres y un flag terminal. La ruta de la raíz al nodo es un prefijo; el flag indica si esa misma ruta es también una palabra completa almacenada. Insert crea los hijos faltantes y marca solo el nodo final. Search comprueba el flag final, mientras que startsWith solo verifica si el recorrido tiene éxito.

Para delete, registro cada padre, arista e hijo mientras recorro la palabra. Si la ruta no existe o el nodo final no es terminal, devuelvo false sin cambiar el estado. De lo contrario, limpio el marcador y recorro hacia atrás. Elimino una arista solo cuando su hijo no tiene hijos y no es terminal, deteniéndome en el primer nodo que aún sea necesitado por otra palabra. Eso es lo que mantiene intacto a apple al eliminar app.

Con hijos basados en mapas, todas las operaciones toman un tiempo esperado de O(L). El almacenamiento total es de O(C) nodos de caracteres, y delete utiliza una pila de ruta de O(L). Probaría casos vacíos y faltantes, inserción duplicada, una palabra que es prefijo de otra, dos palabras que se ramifican y poda completa después de eliminar la última palabra. Si la búsqueda exacta fuera la única operación, usaría un conjunto hash en su lugar.”

Errores comunes

• Tratar cada ruta alcanzable como una palabra → search("app") se vuelve verdadero después de insertar únicamente apple → requiere isWord para la búsqueda exacta.
• Hacer que startsWith compruebe isWord → los prefijos válidos se rechazan a menos que se hayan insertado por separado → devuelve éxito cuando la ruta existe.
• Limpiar o eliminar toda la ruta durante la eliminación → eliminar app destruye apple → limpia primero el marcador terminal y poda únicamente las hojas no terminales.
• Podar más allá de un nodo de ramificación → una palabra no relacionada como apt desaparece → detén la poda cuando el hijo todavía tenga hijos.
• Podar más allá de otro nodo terminal → eliminar una palabra más larga remueve su palabra de prefijo más corta → detén la poda cuando el hijo sea terminal.
• Devolver verdadero cuando solo existe la ruta de eliminación → eliminar app después de insertar únicamente apple muta o reporta erróneamente el estado → requiere que el nodo final sea terminal.
• Contar inserciones duplicadas por accidente → la semántica de conjunto se convierte en un multiconjunto oculto → usa un único marcador booleano o cambia explícitamente el contrato a contadores.
• Afirmar que las cuatro operaciones toman tiempo constante → el trabajo crece con la longitud de la entrada → declara el tiempo esperado O(L) y la suposición sobre el mapa.
• Afirmar que la eliminación no usa espacio extra → la implementación almacena la ruta para la poda hacia atrás → reporta el espacio auxiliar O(L) o utiliza una alternativa recursiva justificada con el mismo límite de pila.
• Asignar siempre 26 hijos → datos dispersos o en Unicode desperdician espacio o rompen el contrato del alfabeto → elige entre arreglo y mapa tras clarificar el conjunto de caracteres.
• Usar un Trie solo para búsquedas exactas → la sobrecarga de nodos compra una funcionalidad de prefijo que el producto nunca usa → prefiere un conjunto hash para la pertenencia exacta por sí sola.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Cómo cambiarían el diseño las palabras duplicadas y la semántica de eliminar una instancia?

Reemplaza isWord por wordCount, y mantén prefixCount en los nodos si se consultan conteos de prefijos. Insert incrementa los conteos a lo largo de la ruta. Erase primero confirma wordCount > 0, decrementa la misma ruta y poda solo cuando los conteos relevantes lleguen a cero. La implementación booleana no puede distinguir una inserción de cinco.

Pregunta de seguimiento 2: ¿Cómo devolverías los K mejores resultados de autocompletado?

Encontrar el nodo del prefijo sigue costando O(L), pero enumerar su subárbol es sensible a la salida y al subárbol. Para un volumen bajo de consultas, recorre y clasifica bajo demanda. Para un volumen alto de consultas, almacena en caché una lista acotada y clasificada de candidatos en cada nodo y actualízala en las escrituras, sacrificando memoria adicional y amplificación de escritura a cambio de una menor latencia de lectura. La puntuación de clasificación y la regla de desempate deben ser explícitas.

Pregunta de seguimiento 3: ¿Cómo funcionarían Unicode y las coincidencias que no distinguen entre mayúsculas y minúsculas?

Define la normalización antes de elegir una representación. Por ejemplo, normaliza a una forma Unicode y aplica una política de mayúsculas/minúsculas dependiente de la configuración regional tanto al insertar como al consultar. Itera por la unidad acordada (code points o grapheme clusters) y usa aristas respaldadas por mapas. Normalizar solo las consultas o solo las inserciones crea rutas que nunca podrán coincidir.

Pregunta de seguimiento 4: ¿Cómo harías que el Trie sea seguro para hilos (thread-safe)?

Un único bloqueo de lectura/escritura (read-write lock) alrededor de todo el Trie es la respuesta correcta más simple: insert y delete adquieren el bloqueo de escritura, mientras que search y prefix search adquieren el bloqueo de lectura. Bloqueos más granulares a nivel de nodo requieren un orden de adquisición fijo y una protección cuidadosa de la poda. Instantáneas inmutables o raíces con copy-on-write simplifican los lectores cuando las actualizaciones son infrecuentes.

Pregunta de seguimiento 5: ¿Qué pasa si la memoria es el recurso limitante?

Mide primero la densidad de nodos. Los arreglos fijos pueden dominar la memoria en datos dispersos, mientras que los mapas conllevan su propia sobrecarga de objetos y hashing. Un radix tree comprime cadenas de un solo hijo; un árbol de búsqueda ternario (ternary search tree) reduce el almacenamiento de hijos; una estructura de estados finitos mínima puede comprimir aún más un diccionario estático. Estas opciones cambian la complejidad de actualización y el riesgo de implementación.

Pregunta de seguimiento 6: ¿Cómo cambiarían el recorrido las coincidencias con comodines o del prefijo más largo?

La coincidencia del prefijo más largo (longest-prefix matching) recorre la consulta mientras recuerda el nodo terminal más profundo, manteniéndose lineal respecto a la longitud de la consulta. Un comodín como . se ramifica a cada hijo en esa posición, por lo que el trabajo en el peor de los casos puede expandirse con el subárbol explorado. La API debe especificar la sintaxis del comodín y si devuelve existencia, un resultado o todos los resultados.