Interview Questions

1-ttt.txt

Tic Tac Toe Code Review

1.	What is the code trying to accomplish?

Show who won on a completed tic-tac-toe board. Return nil if a draw. 

2.	Describe at a high level how it works.

It transforms the tic toe board, a vector of vectors, three times: 

 1. It uses a property of the map function that essentially gets
    column data from seq-of-seq-shaped data structures. I.e. the 
    original vec-of-vecs get rows, then he uses a map to rotate it
    to show columns.
 2. He increments two indices, one for the surface level vector and
    one for the nested vector at the same time, pulling the item at 
    this new index into another sequence, forming the first diagonal.
    Turn into a set and nest in a list for the upcoming check function.
 3. Same principle for the opposite diagonal, except for the nested
    index, start at the end (2) and decrement until 0, adding items
    to the sequence. Both 2 and 3 are done with `map` and two `nth`
    calls. Turn into a set and nest in a list for the check function.

After each of these steps, to leverage the unique-member principle of sets,
turn the nested vectors into sets. Pass the original and the three transformations
into the check function, which goes through each board and transformation.
Because each leaf or lower level member is a set, you don't have to check if there
are three :x's or three :o's. You just check if there's a set with only an :x or
only an :o. 

The code passes the vec-of-sets as a rest arg, so the check function sees a list of
vectors/lists of sets or LoV/LoS. The author uses `first` and `map` to traverse the 
resulting filters, the check function returns the keyword of the first one-member set it
finds or nil if there are no wins. 

More concisely, checking a ttt board has two high level problems consisting of eight 
low-level problems:
 1. Getting a sequence of all the longest lines (four problems):
	 - Rows (easy)
	 - Columns (harder)
		 - Get one column
		 - Use the get one column solution for all columns
	 - TL-to-BR diagonal (medium)
	 - TR-to-BL diagonal (medium-hard)
	 - (Suggestion: Combine all these solutions into one (easy))
 2. (Current solution: Check each board)
	 - Check each non-nil longest-line sequence (in the board)
		 - Remove nils
		 - Check one ll sequence for all :x's or :o's, return :x, :o, or :nil
		 - Use check sequences function for others until :x, :o, or exhausted
     
3.	What feedback would you provide in a code review?

In the commit history of my interview questions repo, used:

 - the thread-last macro for readability
 - `some` instead of filter/first to avoid processing items after a win condition's found
 - `(apply concat)` and `flatten` to check one sequence instead of cycling through four
 - one `(map set)` in `check` instead of four times for each board and transformation of
 - Moved the `let` inside of the `defn` to conceptually organize local into global
 
Commit history at https://github.com/Crowbrammer/soltech-interview-questions/commits/main

4.	(Bonus) How would you write it?

Here's my code:

```
(defn ttt [board]
  (let
    [check (fn [& lists]
             (->> lists
                  (apply concat)
                  (map set)
                  (flatten)                               ;; LoVoVoSets => LoSets
                  (some #(when (or (= % #{:x}) (= % #{:o})) %)) ;; Unlike filter, some doesn't process after a match is found
                  (first)))]
    (check
      ;; rows
      board
      ;; columns
      (apply map list board)
      ;; TLBR diagonal
      (->> (range 3)
           (map #(nth (nth board %) %))
           (list))
      ;; TRBL diagonal
      (->> (range 3)
           (map #(nth (nth board %) (- 2 %)))
           (list)))))
```

Passes the three given assertions.

2-pattern-lock.clj

(ns coding-int-questions.android_lock
  (:require [clojure.test :refer [deftest is]]))

;Note: Still working on the bonus questions. It's not a simple
;plug and play into the combinatorics-no-repeat equation because
;I have to remove invalid patterns. For instance, a T pattern or a 
;VS Code logo pattern use a dot more than once. 

(declare valid-step? valid-path)

;is it a neighbor? Yes? Has it been used? Scrap it.
(defn valid-path
  "Given the matrix:

   [1 2 3
    4 5 6
    7 8 9]

   Validate a path of lines connecting dots at these numbers using
   three conditions:
    - A dot (number) must exist in the matrix
    - Each dot may only be used once
    - A dot may not be crossed without being used
   The problem statement mentioned straight lines, but in practice, it's
   hard to make a curved line, so I don't worry about it."
  ;(= 1-arity function-setup)
  ([[cur :as path]]
   ;Empty at start's invalid. Else set up and run the validator.
   (if (empty? path)
     false
     ;In #s 1-9?
     (if (contains? #{1 2 3 4 5 6 7 8 9} cur)
       (valid-path (rest path) (list cur)) ; Use a list so most recent is destructurable, i.e. prev.
       false)))
  ;Workhorse of the function
  ([[cur :as path] used]                 ;used numbers will be a linked list; (= most-recent first)
   ;If the rest of the path is empty, that means despite all
   ;checks, the path is valid, and we can safely return true.

   ;and returns the first false value or last true value.
   ;recursion results in a true or false (hopefully).
   (if cur
     (and (valid-step? cur used) (if (seq path) (valid-path (rest path) (conj used cur)) true))
     true)))

(defn valid-step?
  "Validate cur to the three conditions:
    - Exists
    - Once
    - and Crosses used"
  [cur [prev :as used]]
  (let [numbers #{1 2 3 4 5 6 7 8 9}
        crosses {#{1 3} 2
                 #{1 9} 5
                 #{1 7} 4
                 #{2 8} 5
                 #{3 7} 5
                 #{3 9} 6
                 #{4 6} 5
                 #{7 9} 8}
        cross (get crosses #{cur prev})]
    (cond
      (not (get numbers cur))                    false
      (->> cur (.indexOf used) (< 0))            false
      ;Note: contains? and get do not work with lists... therefore `some` used.
      (and cross (not (some #(= % cross) used))) false
      :else                                      true)))

(deftest cur-step-test
  (is (true? (valid-step? 3 '(2))))
  (is (true? (valid-step? 3 '(1 2)))))

(deftest valid-path-test
  (is (true? (valid-path [1 6 7 4])))                       ;; knights jump is valid
  (is (true? (valid-path [2 1 3])))                         ;; 2 is already used, so we can cross it
  (is (false? (valid-path [1 3 2])))                        ;; can't get from 1 to 3 without using 2 first
  (is (false? (valid-path [1 9])))                          ;; can't cross 5 without using
  (is (false? (valid-path [1 2 3 2 1])))                    ;; can't use dots more than once
  (is (false? (valid-path [0 1 2 3])))  )                   ;; there's no dot 0