Hay un gran archivo de palabras que cambia dinámicamente. Estamos continuamente agregando algunas palabras en él. ¿Cómo mantendría un registro de las 10 mejores palabras en cada momento?amazon interview prob
Encontré esta pregunta en un blog pero no pude entender la respuesta. La respuesta es: hash table + min-heap
Entiendo por qué hashtable pero no parte de min-heap, ¿alguien puede ayudarme?
Si es top 10 trending words, entonces debe usar un max-heap junto con un hash-table.
Cuando se añade una nueva palabra en el fichero a continuación:
Create un elemento nuevo x con x.key=word y x.count=1.Addx al hash-table. O(1).Addx al max-heap. O(lgn).Cuando se añade una palabra existente en el fichero a continuación:
Findx en el hash-table. O(1).Updatex.count a x.count++.Cuando hay una necesidad de recuperar la top 10 trending words a continuación:
Extract 10 veces desde el max-heap. 10*O(lgn)=O(10*lgn)=O(lgn).Como puede ver, todas las operaciones necesarias se realizan a lo sumo O(lgn).
es posible que desee utilizar un montón mínimo: cuando una palabra existente que no está en el top 10 se convierte en una de las 10 principales, eliminar el mínimo sería un tiempo constante. – aw626
"Actualizar x.count a x.count ++ en el max-heap" - ¿no debería ser 'O (n)'? Primero debe encontrar 'x' en' max-heap', pero no sabe dónde está.Una vez que lo encuentre, aumentarlo y burbujearlo es una operación 'O (lgn)'. –
@ B-Con: Dado que 'max-heap' y' hash-table' apuntan al mismo elemento 'x', entonces no hay necesidad de encontrarlo nuevamente en la tabla hash. Lo arreglaré, gracias. –
Si solo quiere mantener el top 10, usar un max-heap es excesivo. Mantener las 10 entradas en una matriz ordenada será más simple y más rápido.
Para la clasificación, simplemente utilice la ordenación de inserción comenzando desde la parte inferior de la matriz. Deberá verificar si el candidato ya está en el top ten actualizando su posición si es necesario.
si no conserva las otras entradas, ninguna entrada nueva llegará al top 10. –
@KarolyHorvath: obviamente, todavía necesita la tabla hash para contar los hits por entrada. Mi punto es que usar un min-heap para administrar las 10 entradas principales es exagerado. Una matriz ordenada simple funcionaría mejor y la implementación también sería bastante más simple. En realidad, para un N superior superior incrementalmente actualizado (y a menos que tenga lazos masivos) una matriz ordenada siempre funcionaría mejor que un min-montón. – salva
Por lo general, desea un min-heap para realizar un seguimiento de las N respuestas más altas, porque en cada etapa tiene una respuesta candidata y desea saber si es mejor que la peor respuesta en el min-heap, si es , elimine la peor respuesta de la parte superior N del min-heap e inserte al candidato. Tener el - intuitivo - max-heap hace que sea muy fácil elegir la mejor respuesta, pero al decidir si aceptar una nueva respuesta candidata, esto no es lo que quieres. (Solo recuerde que cuando extrae las N respuestas superiores al final, saldrán con la peor de esas N primero). – mcdowella