in tempo reale il monitoraggio delle prime 100 parole di Twitter al minuto/ora/giorno

Question

Recentemente ho sono imbattuto in questa domanda intervista:

Given a continuous twitter feed, design an algorithm to return the 100 most 
frequent words used at this minute, this hour and this day. 

Stavo pensando di un sistema con una mappa hash di word -> count legata a 3 min-cumuli per il minuto, ora e giorno corrente.

Ogni messaggio in entrata è tokenized, sterilizzate e le parola conta aggiornati nella mappa di hash (e aumentare-chiave nei cumuli se la parola esiste già in esso)

Se una delle parole non esistono in l'heap (e la dimensione dell'heap == 100) controllano se il loro frequency > min value nell'heap e se è così estrarre-min e inserirlo nell'heap.

Ci sono modi migliori per farlo?

Answer 1

L'algoritmo è un buon inizio, ma non produrrà risultati corretti. Il problema è che le tabelle hash come le descrivi sono una strada a senso unico: una volta aggiunta una parola, essa viene contata per sempre.

È necessario un array di 1440 (24 * 60) word+count mappe di hash organizzate come descritto; questi sono i tuoi conteggi minuto per minuto. Sono necessarie due mappe hash aggiuntive, per il totale scorrevole dell'ora e del giorno.

Definire due operazioni su mappe hash - add e subtract, con la semantica di unire i conteggi di parole identiche e rimuovere le parole quando il loro conteggio scende a zero.

Ogni minuto si avvia una nuova mappa hash e si aggiornano i conteggi dal feed. Alla fine del minuto, si inserisce la mappa hash nell'array per il minuto corrente, la si aggiunge al totale scorrevole per l'ora e per il giorno, quindi si sottrae la mappa hash di un'ora fa dal totale parziale orario, e sottrarre la mappa hash di 24 ore fa dal totale parziale giornaliero.

Infine, è necessario un modo per produrre le prime 100 parole fornite con una mappa hash. Questo dovrebbe essere un compito banale: aggiungere elementi a un array di voci word+count, ordinare il conteggio e mantenere la top 100.

Answer 2

dasblinkenlight ha reso un buon punto per un errore di non escludere gli elementi dalla mappa hash.

C'è ancora una cosa da aggiungere, per calcolare effettivamente le parole K in alto date un minuto/ora/giorno, è più veloce usare la partizione (O (n)) piuttosto che l'ordinamento (O (nlgn)):

1. scaricare un HashMap di parola di un min/ora/giorno conta in un array: O (n)
2. uso mediana-di-mediana selezione per ottenere l'elem K-esimo: O (n)
3. partizione attorno al K-th elem: O (n)

HTH.