Diseñar una estructura de datos para los K elementos más frecuentes y dinámicos (Dynamic Top-K)

La pregunta y cuándo usarla

Llega un flujo interminable de IDs enteros, un elemento a la vez. add(x) registra una ocurrencia más del ID x. topK(k) devuelve hasta k IDs distintos con las frecuencias actuales más altas y sus recuentos; los IDs empatados pueden aparecer en cualquier orden y k puede cambiar entre consultas. Diseñe soluciones exactas para cargas de trabajo con predominio de lecturas y con predominio de escrituras, y analice sus costos de tiempo y espacio. Si el número de IDs distintos puede crecer sin límite mientras que la memoria es fija, proporcione un diseño aproximado y defina qué significa su margen de error.

Esta pregunta es adecuada para entrevistas de ingeniería de software y algoritmos. El contrato exacto solo permite incrementos de frecuencia: sin eliminaciones, ventanas deslizantes ni fusiones distribuidas. Sea N el número de actualizaciones hasta el momento y D el número de IDs distintos, siendo k << D el caso típico. Las versiones públicas de este problema solicitan explícitamente diseños dependientes de la carga de trabajo y una extensión para flujos con memoria acotada, por lo que “hash map más min-heap” es solo el comienzo de la respuesta.

Qué evalúa el entrevistador

Primero, ¿establece el candidato el contrato de las operaciones y la proporción de la carga de trabajo? Un procesamiento por lotes que consulta una sola vez tras finalizar el flujo no debería pagar el mismo costo de mantenimiento que una tabla de clasificación online consultada tras cada actualización.

Segundo, ¿coinciden las complejidades declaradas con el estado mantenido? Contar en un hash map y construir un min-heap de tamaño k en el momento de la consulta da un costo esperado de O(1) para add y O(D log k) para topK. Afirmar un mantenimiento del heap de O(log k) por actualización también requiere rastrear las posiciones dentro del heap y explicar cuándo un elemento fuera del heap ingresa a él.

Tercero, ¿puede el candidato demostrar que una estructura dinámica es correcta? Una respuesta sólida establece tres invariantes: cada ID pertenece exactamente a un bucket de frecuencia; las frecuencias de los buckets son estrictamente crecientes y ningún bucket está vacío; y la frecuencia del bucket de un ID es igual a su recuento acumulado real. El argumento de complejidad debe derivarse de estas invariantes.

Cuarto, ¿puede el candidato distinguir entre top-k exacto, heavy hitters y estimación de frecuencia? Space-Saving retiene claves candidatas con límites de conteo bajo un presupuesto fijo de contadores. Count-Min Sketch estima principalmente la frecuencia de una clave suministrada y no retiene por sí mismo un conjunto enumerable de IDs. Tratar un sketch por sí solo como una lista top-k deja sin explicar el descubrimiento de candidatos.

Preguntas para aclarar antes de responder

• ¿Es k fijo o varía por consulta? Un K fijo permite un heap indexado de tamaño K. Un k arbitrario favorece una estructura ordenada a través de todas las frecuencias.
• ¿Cuál es la proporción entre actualizaciones y consultas? Un sistema con predominio de escrituras puede diferir el trabajo hasta el momento de la consulta. Las consultas frecuentes justifican mantener el orden en cada add.
• ¿Deben los empates tener un orden determinista? Este contrato permite cualquier orden, por lo que un hash set dentro de cada bucket es suficiente. Exigir IDs en orden ascendente requiere un conjunto ordenado y elimina las actualizaciones con tiempo esperado O(1).
• ¿Se requieren eliminaciones o ventanas de tiempo? Con solo incrementos, un elemento se mueve de la frecuencia f a la frecuencia adyacente f + 1. La eliminación agrega movimiento inverso; una ventana también necesita gestionar el estado de expiración.
• ¿Cabe D en memoria? Una respuesta exacta para una distribución sin restricciones retiene el recuento de cada ID distinto. Una memoria fija requiere aproximación o una segunda pasada reproducible.
• ¿Qué margen de error es aceptable? “Aproximadamente correcto” no es verificable. Especifique un error aditivo en el recuento, un conjunto de candidatos con incertidumbre o una condición de separación de frecuencias que certifique el top-k.
• ¿Pueden desbordarse los contadores? Un servicio de larga duración necesita contadores de 64 bits o más amplios. El ejemplo utiliza number de JavaScript y solo es exacto dentro del rango de enteros seguros.

Estructura de respuesta en 30 segundos

“Primero aclararía si k varía, la relación lectura-escritura, el orden de los empates y el límite de memoria. Para un tráfico con muchas escrituras y pocas consultas, usaría un hash map para inserciones en tiempo esperado O(1), y luego escanearía los D recuentos en un min-heap de tamaño k en O(D log k) por consulta. Si las consultas con k arbitrario son frecuentes, mantendría una lista doblemente enlazada creciente de buckets de frecuencia junto con un mapa ID → bucket. Una actualización mueve un ID solo del bucket f al bucket adyacente f + 1, logrando actualizaciones en tiempo esperado O(1); recorrer hacia atrás para obtener k resultados cuesta O(min(k, D)), con espacio O(D). Si D no cabe en memoria, usaría contadores fijos con Space-Saving con límites de error y certificaría el top-k solo cuando los límites se separen. Count-Min Sketch aún necesitaría un conjunto de candidatos para enumerar los IDs”.

Solución paso a paso

Paso 1: Comparar diseños exactos según la carga de trabajo

“Hash map más min-heap” no es una solución óptima universal. Traslada deliberadamente el trabajo de ordenamiento a la ruta de consulta, lo cual es apropiado cuando predominan las escrituras. Si el producto renderiza una tabla de clasificación tras cada add, escanear repetidamente las D claves se convierte en el cuello de botella, justificando la estructura más compleja de buckets de frecuencia.

Paso 2: Establecer los invariantes de los buckets de frecuencia

Mantenga una lista doblemente enlazada de buckets en orden creciente de frecuencia. Cada bucket posee un conjunto de IDs con esa frecuencia, mientras que un hash map localiza el bucket de un ID directamente. Un nuevo ID se une al bucket de frecuencia 1. Un ID existente se mueve del bucket f al bucket f + 1. Como una actualización incrementa exactamente en uno, solo se puede insertar un nuevo bucket entre el origen y su sucesor; no se necesita búsqueda en la lista. Elimine el bucket de origen en cuanto quede vacío.

Tres invariantes demuestran la corrección del resultado:

1. Cada ID en locations aparece en exactamente un conjunto de bucket.
2. El valor frequency de cada bucket no vacío es igual al recuento real de cada ID que contiene.
3. Las frecuencias aumentan estrictamente desde head hasta tail.

Por lo tanto, recorrer hacia atrás desde tail no puede dejar atrás ningún ID de mayor frecuencia, mientras que los empates pueden devolverse en cualquier orden. Cada bucket visitado produce al menos un resultado, por lo que el número de buckets visitados no supera el tamaño de salida y el tiempo de consulta es O(min(k, D)).

Paso 3: Implementar consultas exactas con k arbitrario

interface Bucket {
  frequency: number;
  values: Set<number>;
  prev: Bucket | null;
  next: Bucket | null;
}

interface TopKEntry {
  value: number;
  count: number;
}

class FrequencyIndex {
  private readonly locations = new Map<number, Bucket>();
  private head: Bucket | null = null;
  private tail: Bucket | null = null;

  add(value: number): void {
    const source = this.locations.get(value);

    if (!source) {
      let target = this.head;
      if (!target || target.frequency !== 1) {
        target = this.insertBefore(this.head, 1);
      }
      target.values.add(value);
      this.locations.set(value, target);
      return;
    }

    let target = source.next;
    if (!target || target.frequency !== source.frequency + 1) {
      target = this.insertAfter(source, source.frequency + 1);
    }

    source.values.delete(value);
    target.values.add(value);
    this.locations.set(value, target);

    if (source.values.size === 0) {
      this.removeBucket(source);
    }
  }

  topK(k: number): TopKEntry[] {
    if (!Number.isInteger(k) || k < 0) {
      throw new RangeError("k must be a non-negative integer");
    }

    const result: TopKEntry[] = [];
    let bucket = this.tail;

    while (bucket && result.length < k) {
      for (const value of bucket.values) {
        result.push({ value, count: bucket.frequency });
        if (result.length === k) break;
      }
      bucket = bucket.prev;
    }

    return result;
  }

  private insertBefore(next: Bucket | null, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev: next?.prev ?? null,
      next,
    };

    if (bucket.prev) bucket.prev.next = bucket;
    else this.head = bucket;

    if (next) next.prev = bucket;
    else this.tail = bucket;

    return bucket;
  }

  private insertAfter(prev: Bucket, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev,
      next: prev.next,
    };

    if (prev.next) prev.next.prev = bucket;
    else this.tail = bucket;

    prev.next = bucket;
    return bucket;
  }

  private removeBucket(bucket: Bucket): void {
    if (bucket.prev) bucket.prev.next = bucket.next;
    else this.head = bucket.next;

    if (bucket.next) bucket.next.prev = bucket.prev;
    else this.tail = bucket.prev;
  }
}

La complejidad utiliza las suposiciones habituales de tiempo constante esperado para Map y Set, no una garantía estricta del peor caso de O(1) según la especificación de JavaScript. topK(0) devuelve un array vacío, k > D devuelve todos los IDs y un valor de k negativo o no entero lanza una excepción.

Paso 4: Definir la garantía de aproximación bajo memoria acotada

El hash map exacto crece con D. Space-Saving mantiene en su lugar solo m contadores que contienen un ID, un recuento estimado y un error máximo; se requiere m > k para comparar contra el candidato límite k + 1. Un ID observado que ya está siendo rastreado incrementa su contador. Cuando llega un ID no rastreado después de que todos los contadores están ocupados, reemplaza al ID con el recuento estimado mínimo c_min; la nueva estimación pasa a ser c_min + 1, con un error registrado de c_min.

Para cada ID monitoreado, la frecuencia real se encuentra en [estimate - error, estimate], y el artículo original acota la sobreestimación máxima en N / m. El conjunto top-k puede certificarse cuando el límite inferior más pequeño entre los primeros k candidatos no sea menor que el límite superior estimado del candidato k + 1. Si esos intervalos se solapan, devuelva candidatos aproximados en lugar de presentar el orden estimado como exacto. Cuando todo el flujo tiene D <= m, no se produce ningún reemplazo y los recuentos permanecen exactos.

Count-Min Sketch utiliza un arreglo fijo de contadores de tamaño width × depth. Con width = ceil(e / ε) y depth = ceil(ln(1 / δ)) en un flujo de solo incrementos, una estimación para un ID dado nunca cae por debajo de su recuento real y, con una probabilidad de al menos 1 - δ, no es mayor que true count + εN. El sketch no retiene IDs, por lo que aún necesita un heap de candidatos, un conjunto de candidatos o un dominio enumerable. Un sketch por sí solo no puede responder "¿qué IDs pertenecen al top-k?".

Paso 5: Verificar contra un oráculo, no solo con un ejemplo

Comience con [1, 2, 1, 3, 2, 1] y verifique que topK(2) devuelva los dos IDs con frecuencias 3 y 2. Luego cubra una estructura vacía, k = 0, k > D, todos empates, un elemento frecuente más muchos elementos únicos, y un ID moviéndose a través de múltiples buckets.

Finalmente, genere un flujo de actualizaciones aleatorias y use un conteo naive con hash map más ordenamiento completo como oráculo. A intervalos, verifique que la longitud del resultado sea min(k, D), que los IDs sean únicos, que cada recuento reportado sea exacto y que ningún ID excluido tenga un recuento superior al recuento seleccionado más pequeño. La implementación anterior superó esta comprobación diferencial a lo largo de 10,000 actualizaciones aleatorias deterministas y varios valores de k.

Ejemplo de una respuesta sólida

“Limitaré el contrato exacto a actualizaciones de solo incremento, k específico por consulta y orden de desempate arbitrario. Para un escenario con muchas escrituras y pocas consultas, mantendría solo un hash map ID → count para inserciones con tiempo esperado O(1). Una consulta escanea D IDs mediante un min-heap de tamaño k, costando O(D log k) de tiempo y O(k) de espacio extra.

Para consultas frecuentes de clasificación, utilizaría buckets de frecuencia doblemente enlazados. Los buckets se ordenan de menor a mayor frecuencia y contienen los IDs empatados en esa frecuencia; un hash map localiza el bucket de cada ID. Un add mueve un ID solo de f a f + 1, por lo que examina un bucket adyacente y elimina un bucket de origen vacío. Las actualizaciones toman tiempo esperado O(1), recorrer hacia atrás desde la cola devuelve resultados en O(min(k, D)), y el espacio total es O(D). La corrección se deriva de la pertenencia única a buckets, los recuentos exactos por bucket y el orden estrictamente creciente de los buckets.

Si D no cabe en memoria, el contrato exacto debe cambiar. Retendría m contadores de Space-Saving con intervalos de error para los candidatos; la sobreestimación máxima está acotada por N / m, y certificaría el conjunto solo cuando los límites inferiores de los primeros k se separen de los límites superiores posteriores. Count-Min Sketch puede estimar un ID suministrado, pero aún requiere un mecanismo para descubrir candidatos. Antes de producción, ejecutaría pruebas diferenciales aleatorias contra ordenamiento completo y probaría explícitamente empates, valores de k inválidos y desbordamientos de contadores”.

Errores comunes

• Elegir un min-heap antes de preguntar sobre la carga de trabajo → Las consultas frecuentes escanean los D IDs, mientras que las consultas raras pueden no justificar un mantenimiento continuo → Distribuya el costo en la ruta de actualización o de consulta según la proporción real.
• Mantener un K fijo cuando k varía → Una consulta mayor que el K mantenido no tiene un conjunto completo de candidatos → Acote k explícitamente o use buckets de frecuencia o una estructura ordenada que admita un k arbitrario.
• Modificar una clave del heap in situ → Un heap ordinario no conoce la posición de un elemento, por lo que su orden se rompe o se acumulan registros obsoletos → Mantenga ID → heap index, o elimine y vuelva a insertar la clave antigua con la complejidad declarada.
• Dejar buckets de frecuencia vacíos enlazados → Una consulta puede recorrer huecos desde la frecuencia 1 hasta el recuento máximo → Desenlace un bucket inmediatamente después de que su último ID se mueva.
• Afirmar un hash estricto de O(1) → Map y Set admiten el análisis habitual de complejidad esperada, no una garantía estricta del lenguaje → Declare el supuesto de hash; use un árbol balanceado y acepte O(log D) cuando los límites del peor caso sean prioritarios.
• Devolver top-k directamente desde Count-Min Sketch → El sketch responde a consultas sobre claves suministradas y no puede enumerar IDs desconocidos → Mantenga el descubrimiento de candidatos por separado o use Space-Saving, que retiene claves candidatas.
• Reportar aproximaciones sin margen de error → El entrevistador no puede saber si los rangos k y k + 1 son distinguibles → Devuelva estimaciones, límites inferiores y superiores, y si el conjunto está certificado.
• Probar solo el ejemplo básico → Los enlaces rotos, buckets vacíos y límites de empates a menudo aparecen solo tras secuencias largas de actualizaciones → Realice pruebas diferenciales contra un oráculo de ordenamiento completo y valide las invariantes.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: Si topK siempre utiliza K = 100, ¿se siguen necesitando los buckets de frecuencia?

No necesariamente. Un mapa de recuentos, un min-heap de tamaño 100 y ID → heap index pueden ajustar un miembro del heap o comparar contra el mínimo después de cada actualización en O(log 100). Puede ser más simple en código y disposición de memoria, pero no puede responder a topK(1000). Los buckets de frecuencia justifican su complejidad cuando k es arbitrario y las actualizaciones en tiempo constante esperado son críticas.

Pregunta de seguimiento 2: ¿Qué cambia si los IDs empatados deben estar en orden ascendente?

Reemplace el Set de cada bucket con un conjunto ordenado, o bien ordene solo el bucket del límite que es parcialmente consumido por una consulta. La primera opción añade O(log s) a cada movimiento para un bucket de tamaño s; la segunda asume un costo de ordenamiento en el límite solo en el momento de la consulta. Elija en función de con qué frecuencia se requiere un orden determinista.

Pregunta de seguimiento 3: ¿Cómo añadiría remove(x)?

Mueva un ID de la frecuencia f a f - 1 verificando simétricamente el bucket predecesor, eliminando el ID de locations cuando llegue a cero. Defina si eliminar un ID inexistente lanza una excepción o se ignora. Con add y remove concurrentes, localizar, mover y desenlazar un bucket vacío deben compartir una única sección crítica atómica; de lo contrario, el mismo ID podría aparecer en dos buckets.

Pregunta de seguimiento 4: ¿Qué ocurre si la consulta pide solo los últimos 10 minutos?

Las frecuencias dejan de ser monótonas. El índice de buckets también necesita eventos con marcas de tiempo o recuentos agrupados por tiempo para que la expiración emita actualizaciones inversas. Una cola por evento es exacta pero usa espacio proporcional a los eventos en la ventana. Los buckets de tiempo reducen el estado mientras introducen un error de límite explícito. Un resumen Space-Saving de todo el historial no puede restar eventos expirados arbitrarios directamente.

Pregunta de seguimiento 5: ¿Qué pasa si los intervalos de Space-Saving para los rangos k y k + 1 se solapan?

Aumente el presupuesto de contadores m, reporte que el conjunto de candidatos aún no está certificado, o reproduzca los datos para contar un conjunto de candidatos de forma exacta. Una segunda pasada solo corrige los candidatos retenidos. Si el resumen era demasiado pequeño para garantizar que el top-k real entrara en ese conjunto, amplíe el conjunto de candidatos antes de la reejecución.

Pregunta de seguimiento 6: ¿Cómo se obtiene el top-k global a través de shards?

Las listas locales de top-k no pueden producir el top-k global exacto para una distribución arbitraria. Un ID justo debajo del corte en cada shard puede clasificar globalmente tras la agregación. Un diseño exacto debe agregar todos los recuentos relevantes o mantener límites de candidatos que demuestren la cobertura. Un diseño aproximado puede combinar resúmenes fusionables, pero su contrato debe incluir el error adicional y la latencia de reporte.