Vanta interview match-pattern

I was asked the following two questions in a technical interview with Vanta:

Suppose you have an array of numbers: [1 2 1 2] and a string: “cat dog cat dog“

And you have to write a function that determines whether the string matches the “pattern“ of the array. To match the pattern, there can’t be two different words corresponding to the same number in that position. For example [1 2 1 2] matches the pattern “cat dog cat dog“ because 1 only maps to cat and 2 only maps to dog, where as

[1 2 3 2 1] doesn’t match with “dog ant cat dog dog“, because 2 matches with ant and with dog at positions 1 and 3.

I wrote the following function:

(defn match-pattern
  "TOC: ~15m
  Time Complexity: O(n), (= n (count candidates))"
  [pattern candidates]

  (loop [candidates (clojure.string/split candidates #" ")
         pattern pattern
         mapping {}]

    (cond
      (not mapping) false
      (and (seq candidates) mapping) (recur (rest candidates) (rest pattern)
                                          (if (contains? mapping
                                                         (first pattern))
                                            (if
                                                (not=
                                                 (get mapping (first pattern))
                                                 (first candidates))
                                              false
                                              mapping)
                                            (assoc mapping (first pattern)
                                                   (first candidates))))
      :else true)))

Then they asked me to write a match-meta-pattern function. The input to the match-meta-pattern is a 2d array and a string like before. The 2d array could be [[1] [1 2]], and the function should return whether all the patterns that can be formed with the 2d array are true or not.

All the patterns formed by the 2d array means taking all permutations of the successive sub arrays in the metapattern. So [[1] [1 2]] will become [[1 1] [1 2]], and [[1 2] [2] [1 2]] will become [[1 2 1] [1 2 2] [2 2 1] [2 2 2]], and we will check whether each of these patterns match with the string, and if all of them match, then we will return true, and otherwise false.

In my first attempt, during the interview, to make all the permutations, I used a two maps nested, but it didn’t work.

BROKEN CODE

(defn match-meta-pattern
  "Time Complexity: O((apply max subvectors)^(size pattern))"
  [metapattern candidates]
  (loop [result [[(nth (first metapattern) 0)]] metapattern metapattern]
    (if (seq metapattern)
        (recur
       ;;;;;;;;;;;;
         (for [next-pattern metapattern
             running-pattern result]
           (do
             (prn running-pattern)
             (conj running-pattern next-pattern))
           )
         #_(do (prn "meta" (first metapattern))
             (prn "->" result)
             (map (fn [next-pattern]
                    (map (fn [running-pattern]
                           (conj running-pattern next-pattern)) result))
                  (first metapattern)))
       ;;;;;;;;;;;;
         (rest metapattern))
        result)))

But here is the working code, that finds whether a metapattern matches the string:

(defn match-meta-pattern
  "Time Complexity: O((apply max subvectors)^(size pattern))"
  [metapattern candidates]
  (letfn [(all-branches [set' & sets]
            (if (seq sets)
              (for [run-set (apply all-branches sets)
                    set-elem set']
                (conj run-set set-elem))
              (for [elem set']
                (list elem))))]
    (every? true? (map #(match-pattern % candidates)
                       (apply all-branches metapattern)))))


(match-meta-pattern [[1] [1 2]] "dog cat")

(match-meta-pattern [[1 2] [2] [1 2]] "ant cat falcon")

(match-meta-pattern [[1 2] [1] [1 2]] "dog cat cat")

(match-meta-pattern [[1] [1 2] [2 500]] "cat dog cat")