Facebook Interview Question
SDE1sCountry: United States
1. Maintain a hash table as follows:
Key = word
Value = array of integers of size 25
The 26 values are
0 => The total 24 hour count for this word
1 => The total count for this word in the current hour
2 => The count for this word in the previous hour
...
24 => The count for this word 24th hour from now
.
2. As you process the stream of messages, for each word, do the following
(a) Look up the word in the hash table, if not found, add it
(b) Increment both the total word count (index 0) and the current hour count (index 1)
.
3. Run a batch job every hour that iterates through all the values and does the following:
(a) Subtract the 24th hour (index 24) word count from the total count (index 0)
(b) Shift the sub-array from 1-24 by one place
(c) Set value at index 1 to count=0
.
There are two advantages to this approach:
(a) Once you have processed a message, you don't need to keep the logs any more
(b) It also satisfies the follow-up question, where the message does not have a time stamp
1. do word stemming (eat, eating, eats, ate --> eat) for each word in a twitter message
- Chris June 09, 20172. for each word-id (an integer now), increase the occurence count when a message is sent
3. for each word-id decrease the occurence when a message is older than 24 hours (e.g. a batch job identifying this messages)
4. over this huge vector (hashtable) either iterate frequently to pick the 10 biggest and cache that result or maintain the order using a tree (hastable -> tree-item, tree is sorted according to occurence)
this has the advantage that you can distribute it well, k servers can handle the m words, if you want to know the top 10 words, ask each server for the top 10 words and take the top 10 out of those responses...