402 - PurelyFunctional.tv Newsletter

00 Most frequent element.md

Most frequent element

Write a function that takes a collection and returns the most frequent element. But here's the thing: you can't use the built-in function clojure.core/frequencies. And if there are ties, just pick one.

Examples

(most-frequent [2 2 3 4 4 2 1 1 3 2]) ;=> 2
(most-frequent []) ;=> nil
(most-frequent [1 1 4 4 5]) ;=> 4

Notes

• return nil for an empty collection
• in the case of a tie, return one of the winners

Thanks to this site for the challenge idea where it is considered Very Hard level in JavaScript.

Please submit your solutions as comments on this gist.

(defn most-frequent-stream
  "Lazy sequence of which element has occurred most often up through point in collection"
  ([xs] (most-freq-stream xs {}))
  ([xs counts] (most-freq-stream xs counts nil))
  ([xs counts mf]
   (lazy-seq
    (when (seq xs)
      (let [x (first xs)               ;; Will referencing head here be issue?
            xc (inc (or (counts x) 0)) ;; x count
            mc (or (counts mf) 0)      ;; max frequent val count
            nmf (if (< xc mc) mf x)]   ;; new most frequent val
        (cons nmf
              (most-freq-stream (rest xs) (assoc counts x xc) nmf)))))))

(defn most-frequent
  "Return most frequent element in coll. In event of a tie, return the first to hit that frequency"
  {:test #(do
            (assert (= (most-frequent [2 2 3 4 4 2 1 1 3 2]) 2)) ;=> 2
            (assert (nil? (most-frequent []))) ;=> nil
            (assert (= (most-frequent [1 1 4 4 5]) 4)))}
  [xs]
  (last (most-freq-stream xs)))

(test #'most-frequent)