bagaag · January 29, 2014 02:52 · Jan 29, 2014
diff --git a/HitAggregator.java b/HitAggregator.java
@@ -0,0 +1,124 @@
+/* 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;
+	}
+}
+
+