title: Algorithm to find top 10 search terms
body: <p>I'm currently preparing for an interview, and it reminded me of a question I was once asked in a previous interview that went something like this:</p>
  
  <p>"You have been asked to design some software to continuously display the top 10 search terms on Google. You are given access to a feed that provides an endless real-time stream of search terms currently being searched on Google. Describe what algorithm and data structures you would use to implement this. You are to design two variations: </p>
  
  <p>(i) Display the top 10 search terms of all time (i.e. since you started reading the feed). </p>
  
  <p>(ii) Display only the top 10 search terms for the past month, updated hourly. </p>
  
  <p>You can use an approximation to obtain the top 10 list, but you must justify your choices."
  <br />I bombed in this interview and still have really no idea how to implement this. </p>
  
  <p>The first part asks for the 10 most frequent items in a continuously growing sub-sequence of an infinite list. I looked into selection algorithms, but couldn't find any online versions to solve this problem. </p>
  
  <p>The second part uses a finite list, but due to the large amount of data being processed, you can't really store the whole month of search terms in memory and calculate a histogram every hour. </p>
  
  <p>The problem is made more difficult by the fact that the top 10 list is being continuously updated, so somehow you need to be calculating your top 10 over a sliding window.</p>
  
  <p>Any ideas?</p>