Hit Aggregator Problem

HitAggregator.java

/* PROBLEM:
 * Write a class to support the following website feature. On each product 
 * detail page, display the number of hits in the past 10 minutes if there have 
 * been at least 10. Otherwise, display the number of hits in the past hour if 
 * there have been at least 10. Otherwise, display the number of hits in the 
 * past 24 hours if there have been at least 10. Otherwise, display nothing. 
 * There is no analytics service available to provide realtime reporting on the 
 * number of hits, so this class must also collect that data. It should aim to 
 * work on a website that has a few million product pages and gets 10 million 
 * unique visitors per day.
 */

import java.util.*;

public class HitAggregator {

	// 10 min, 1 hr, 24 hr
	private final static int[] THRESHOLDS = {10, 60, 1440};

	// number of hits needed to satisfy a threshold
	private final static int MIN_HITS = 10;

	// stores a list of dated hits for each id
	private Map<Long,List<Entry>> hitCounts = new HashMap<Long,List<Entry>>();

	// dated hit count, hits are grouped for 1 minute
	protected static final class Entry {
		public long date = System.currentTimeMillis(); 
		public int hits = 1;
	}

	// return value must include the hit count and the threshold
	public static final class Result {
		public int threshold; // in minutes (10 min, 1hr, 24 hr)
		public int hits; // number of hits
		public Result(int t, int h) { threshold = t; hits = h; }
	}

	// get list of minute/counts for an id
	private List<Entry> getCounts(long id) {
		List<Entry> counts = this.hitCounts.get(id);
		if (counts==null) {
			counts = new ArrayList<Entry>();
			this.hitCounts.put(id, counts);
		}
		return counts;
	}

	// record a hit
	private void recordHit(List<Entry> counts, long id, long now) {
		long minuteAgo = now - (60*1000);

		// get most recent entry and add to it if it's for the current minute, or create a new one
		Entry latest = null;
		if (counts.size()>0) {
			// get latest entry
			latest = counts.get(counts.size()-1);
			// increment if its for this minute
			if (latest.date > minuteAgo) {
				latest.hits++;
			} 
			else {
				// minute has passed, create hit count for the current minute
				counts.add(new Entry());
			}
		} 
		else {
			// empty list, create new hit count
			counts.add(new Entry());
		}
	}

	/* record a hit for the page and return a result object */
	/* this is the only method exposed to the servlet layer */
	public Result aggregate(long id) {

		// get entry list for this id
		List<Entry> counts = getCounts(id);

		// record the hit
		long now = System.currentTimeMillis();
		recordHit(counts, id, now);

		// get the hit count and threshold
		int hits = 0;
		int threshold_ix = 0;
		int threshold = HitAggregator.THRESHOLDS[threshold_ix];
		long threshold_date = now - (threshold*60*1000);
		// walk through the hit counts backwards
		for (int i=counts.size()-1; i>=0; i-- ) {
			Entry e = counts.get(i);
			// increment hits if within the current threshold
			if (e.date > threshold_date) {
				hits += e.hits;
			}
			// we've met the min threshold hits, so get out
			else if (hits >= HitAggregator.MIN_HITS) {
				counts.subList(0,i).clear(); // had to look up this trick
				break;
			}
			// increase threshold to look for more hits
			else {
				threshold_ix++;
				if (HitAggregator.THRESHOLDS.length <= threshold_ix) {
					threshold = HitAggregator.THRESHOLDS[threshold_ix];
					threshold_date = now - (threshold*60*1000);
				}
				// out of HitAggregator.THRESHOLDS, remove old entries and get out
				else {
					counts.subList(0,i).clear(); 
					break;
				}
			}
		}
		// return result or null if we don't have the minimum hits needed 
		Result result = null;
		if (hits >= HitAggregator.MIN_HITS) {
			result = new Result(threshold, hits);
		}
		return result;
	}
}