Heavy Hitters algorithm

heavy-hitters.clj

(defn heavy-hitter
  "Output the lement in the list that came up more than 50% of the time, nil otherwise."
  [lst]
  (let [heavy (heavy-hitter* lst)]
    (when (->> lst
             (filter (partial = heavy))
             (count)
             (<= (/ (count lst) 2)))
      heavy)))

(defn- heavy-hitter*
  "Output the element in the list that most likely came up most."
  [lst]
  (first
   (reduce
    (fn [[heavy count] next]
      (if (= heavy next)
        [heavy (inc count)]
        (if (= count 0)
          [next 1]
          [heavy (dec count)])))
    [(first lst) 1]
    (rest lst))))

An algorithm that finds the element in the list that finds the most common element in a list.

It's good because although it requires two passes of the data, it only has constant space requirements.