Diseña un servicio de autocompletado/typeahead de búsqueda: ¿cómo devuelves sugerencias en milisegundos?

#La restricción que define todo: la consulta ocurre en cada tecla presionada

Un buscador que dispara una request en cada tecla presionada significa que un usuario escribiendo "chicago" genera siete requests en unos dos segundos, y cada una necesita volver antes de que el usuario escriba la siguiente letra o la interfaz se sentirá lenta. Eso descarta cualquier cosa que toque un índice de búsqueda de propósito general o escanee una tabla en el momento de la consulta: el presupuesto es de milisegundos de un solo dígito de trabajo del lado del servidor, lo cual significa que la respuesta debe buscarse, no calcularse, en el momento en que llega la request.

El lado del cliente también importa, y a menudo es por donde empieza la entrevista: hacer debounce de las teclas (esperar ~100-150ms después de que el usuario deja de escribir antes de disparar una request, para que "united" no envíe siete requests cuando el usuario escribe rápido), cancelar las requests en vuelo que ya no corresponden al valor actual del input (de lo contrario, una respuesta más vieja y lenta para "c" puede llegar después de la respuesta más nueva para "ch" y mostrar por un instante la lista equivocada), y cachear en el cliente los resultados de prefijos recientes para que borrar con backspace no vuelva a golpear la red.

#Lado del servidor: precomputar, no buscar

La idea central es un trie (árbol de prefijos): cada nodo representa un carácter, y un camino desde la raíz deletrea un prefijo. En vez de recorrer el trie en el momento de la consulta y luego rankear todas las palabras completas que cuelgan de un nodo —que es justamente la parte lenta—, cada nodo precomputa y almacena sus propias top-K sugerencias, ordenadas por un peso de popularidad/relevancia, construido durante un trabajo de indexación offline o periódico. Una consulta entonces no hace más que caminar hasta el nodo del prefijo escrito y devolver una lista que ya está ordenada.

Ajustar líneas largas
type Suggestion = { term: string; weight: number };

const TOP_K = 8;

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  // Sugerencias precomputadas y ordenadas por peso para el prefijo que termina en este nodo.
  topSuggestions: Suggestion[] = [];
}

class AutocompleteTrie {
  private root = new TrieNode();

  insert(term: string, weight: number): void {
    let node = this.root;
    this.updateTopK(node, term, weight);
    for (const ch of term.toLowerCase()) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
      this.updateTopK(node, term, weight);
    }
  }

  private updateTopK(node: TrieNode, term: string, weight: number): void {
    const existing = node.topSuggestions.find((s) => s.term === term);
    if (existing) {
      existing.weight = weight;
    } else if (node.topSuggestions.length < TOP_K) {
      node.topSuggestions.push({ term, weight });
    } else if (weight > node.topSuggestions[TOP_K - 1].weight) {
      node.topSuggestions[TOP_K - 1] = { term, weight };
    } else {
      return; // no es lo bastante popular como para desplazar nada en este nodo
    }
    node.topSuggestions.sort((a, b) => b.weight - a.weight);
  }

  suggest(prefix: string): string[] {
    let node = this.root;
    for (const ch of prefix.toLowerCase()) {
      const next = node.children.get(ch);
      if (!next) return [];
      node = next;
    }
    return node.topSuggestions.map((s) => s.term);
  }
}

// Construido (o reconstruido) periódicamente a partir de pesos agregados del log de consultas.
const trie = new AutocompleteTrie();
trie.insert("chicago bulls", 9800);
trie.insert("chicago weather", 15200);
trie.insert("chick-fil-a near me", 42000);

console.log(trie.suggest("chi"));
// -> ["chick-fil-a near me", "chicago weather", "chicago bulls"]

Una búsqueda ahora es O(L + K log K) donde L es la longitud del prefijo escrito y K es la pequeña constante de sugerencias guardadas por nodo: en la práctica, O(L), independiente de cuántos términos totales conozca el sistema. Ese es todo el truco: pagar el costo de rankear una sola vez, offline, por prefijo, en vez de una vez por cada tecla, por cada usuario.

#El camino de la request de punta a punta

El cacheo de borde con TTL corto absorbe el hecho de que los prefijos comunes ("a", "el", "cómo") se piden constantemente y de forma idéntica por muchos usuarios: un acierto de caché ahí no cuesta nada y nunca llega a tocar el servicio del trie.

#Mantener el trie fresco, y las partes que son genuinamente difíciles

El trie descrito arriba es una instantánea optimizada para lectura; no está pensado para actualizarse transaccionalmente en cada consulta. En la práctica, un job en segundo plano lo reconstruye (o reconstruye solo los subárboles afectados) periódicamente —cada pocos minutos para un feed de temas de tendencia que cambia rápido, cada hora o cada día para un catálogo de productos estable— a partir de una fuente de pesos agregada: logs de clics de búsqueda, conteos de ventas, o una lista de refuerzo curada a mano. El servicio sigue respondiendo desde la instantánea anterior mientras se construye la siguiente, y luego cambia atómicamente a la nueva, así que los usuarios nunca ven un trie a medio construir.

Las partes genuinamente difíciles, más o menos en el orden en que los entrevistadores las indagan: tolerancia a errores de tipeo (el trie descrito aquí requiere una coincidencia exacta de prefijo; el matching difuso necesita una capa separada de distancia de edición o un índice de n-gramas, y suele ser un camino de respaldo distinto y más lento, no algo incorporado en el camino caliente); personalización (el historial propio de un usuario reordenando o inyectando sugerencias por encima del ranking global, normalmente combinado del lado del cliente o en una capa delgada por request, en vez de mantener un trie por usuario); matching de varias palabras y en orden distinto ("pizza cdmx" probablemente también debería mostrar "pizza en cdmx", algo que un trie de prefijos puro no puede hacer sin indexar adicionalmente por cada palabra, no solo por la cadena completa); y la memoria a escala web genuina (un trie sobre miles de millones de consultas distintas no cabe en una sola máquina, así que se shardea, comúnmente por el primer carácter o un hash de los primeros caracteres, con una capa de enrutamiento delante).

🧠 Check your understanding
0/2 · 0/2 answered
1. ¿Por qué cada nodo del trie almacena sus propias top-K sugerencias precomputadas en vez de rankear en cada request?
Usa menos memoria que almacenar los términos una sola vezElimina la necesidad de un log de consultasMueve el trabajo costoso de ranking a un proceso offline, así que una consulta en vivo es solo un lookup O(L)Permite que el trie también soporte matching difuso de errores de tipeo
2. Un trie de prefijos plano, como el descrito, tiene más dificultades con cuál requisito?
Devolver resultados en menos de 50msAlmacenar un peso de popularidad por términoHacer match de una consulta donde las palabras se escriben en un orden distinto, como "pizza cdmx" vs "pizza en cdmx"Manejar millones de términos de búsqueda distintos