# Coding Challenges

This is a place for me to record my work on various coding challenges for later reference.

## Reverse a 32-bit Integer

Link: https://leetcode.com/problems/reverse-integer/

I used this one to try out Racket, rather than to practice word size
constraint as the problem instructs. Leetcode unfortunately requires
that your solution be called `reverse`, which causes the builtin
function of the same name to be shadowed. So we have to reimplement
list reversal with a new name:

(define/contract (reverse-list l) (-> list? list?) (reverse-list-helper l '())) (define/contract (reverse-list-helper l aux) (-> list? list? list?) (if (null? l) aux (reverse-list-helper (cdr l) (cons (car l) aux))))

And then solve the problem:

(define/contract (reverse x) (-> exact-integer? number?) (let* ([s (number->string x)] [y (string->number (if (< x 0) (string-join (list "-" (reverse-string (substring s 1))) "") (reverse-string s)))]) (if (or (< y -2147483648) (>= y 2147483648)) 0 y))) (define/contract (reverse-string s) (-> string? string?) (list->string (reverse-list (string->list s))))

## Sierpinski Triangles

The tricky part of this problem is choosing a way to represent and draw triangles that can be reused across iterations. One useful observation is that at each iteration, the canvas can cleanly be divided into rows of triangles. Using this observation, we need to devise a way of drawing a row of triangles and identify how these rows change at each "iteration" of generating the fractal.

(def n (Integer/parseInt (read-line))) (def num-rows 32) (def num-cols 63) (def mark "1") (def unmark "_") (def marks (repeat mark)) (def unmarks (repeat unmark)) (defn draw-line [height vertices width line] (if (empty? vertices) (let [num-left (- num-cols width) complete (concat (take num-left unmarks) line)] (apply str (reverse complete))) (let [v (- (first vertices) height) num-unmark (- v width) num-mark (inc (* 2 height)) more (concat (take num-mark marks) (take num-unmark unmarks))] (recur height (rest vertices) (+ width (count more)) (concat more line))))) (defn draw-row [height vertices] (clojure.string/join "\n" (for [h (range height)] (draw-line h vertices 0 '())))) (defn draw-rows [height sets] (clojure.string/join "\n" (for [s sets] (draw-row height s)))) (def n0 (draw-rows 32 '((31)))) (def n1 (draw-rows 16 '((31) (15 47)))) (def n2 (draw-rows 8 '((31) (23 39) (15 47) (7 23 39 55)))) (defn fractalize [num-iter curr-iter height verts] (if (= curr-iter num-iter) (draw-rows height verts) (let [new-verts (apply concat (for [l verts] (list l (apply concat (for [v l] (list (- v (/ height 2)) (+ v (/ height 2))))))))] (fractalize num-iter (inc curr-iter) (/ height 2) new-verts)))) (defn draw-fractal [n] (fractalize n 0 num-rows (list (list (dec num-rows))))) (println (draw-fractal n))

## Unique Paths in Chicago

Link: https://leetcode.com/problems/unique-paths/

I posed this question in a practice interview because I wanted to know how many different ways I could walk to the Y before I had to start repeating routes. Later I found it on Leetcode: https://leetcode.com/problems/unique-paths/

The best solution I've found frames this problem as moving along one
axis, and choosing at which of the cross streets to move along the
other axis. This is an combinations with replacement problem, also
known as multichoose. n multichoose k can also be thought of as a
stars and bars problem with `n+k-1` objects: choose `k` of the objects
to be stars (representing chosen elements), leaving `n-1` to be bars
(separating each of `n` cells which contain some number of the `k`
elements). This stackoverflow post has more detail.

I'm tempted to call this solution constant-time, but really the number
of operations it performs grows as `m+n`:

def comb(n,k): res = 1 i = n while i > n - k: res *= i i -= 1 i = k while i > 1: res = res // i i -= 1 return res class Solution: def uniquePaths(self, m: int, n: int) -> int: return comb(m+n-2,m-1)

## Construct Binary Tree from Inorder and Preorder Traversals

Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

At first, I tried a solution where I constructed a candidate tree (leftward descending linked list according to preorder) and then using the inorder traversal to graft the tree so that it satisfied the inorder.

In thinking over that solution, I observed that when we start, we know that the first element of the preorder must be the root; moreover, all of the elements appearing before the root in the inorder must belong to the left subtree, and the rest to the right.

A recursive structure was beginning to appear. Now we know how many
elements `k` are in the left subtree; the next `k` elements of the
preorder travsersal (after the first) must therefore represent a
preorder traversal of the left subtree.

# Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right

def traverse(preorder,inorder): if preorder == []: return None val = preorder[0] pivot = inorder.index(val) inorderLeft = inorder[:pivot] inorderRight = inorder[pivot+1:] preorderLeft = [i for i in preorder if i in inorderLeft] preorderRight = [i for i in preorder if i in inorderRight] return TreeNode(val,traverse(preorderLeft,inorderLeft),traverse(preorderRight,inorderRight)) class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: return traverse(preorder,inorder)

That solution passed all but one test case, and exceeded the time limit. How can we avoid creating so many copies of the traversals?

# Definition for a binary tree node. class Solution: # [left,right) def traverse(self,pleft,pright,ileft,iright): if pleft >= pright: return None val = self.preorder[pleft] pivot = self.inorder.index(val) numLeft = pivot-ileft leftNode = self.traverse(pleft+1,pleft+1+numLeft,ileft,pivot) # traverse(preorderLeft,inorderLeft) rightNode = self.traverse(pleft+1+numLeft,pright,pivot+1,iright) # traverse(preorderRight,inorderRight) return TreeNode(val,leftNode,rightNode) def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: self.preorder = preorder self.inorder = inorder return self.traverse(0,len(preorder),0,len(preorder))

## Make Each Node of Perfect Binary Tree "Point Right"

Link: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next def rightests(node): if node: node.next = None rightests(node.right) def inners(a,b): if a: a.next = b inners(a.right,b.left) def sibs(a,b): if a: a.next = b sibs(a.left,a.right) sibs(b.left,b.right) inners(a.right,b.left) class Solution: def connect(self, root: 'Optional[Node]') -> 'Optional[Node]': if root: sibs(root.left,root.right) rightests(root) return root

## Implement `x^n`

I remember implementing this in SICP using tail-recursion. I applied the same principle to come up with this iterative solution:

aclass Solution: def myPow(self, x: float, n: int) -> float: if n < 0: return 1/self.myPow(x,-n) res = 1 while n: if n & 1: res *= x x *= x n = n >> 1 return res

## Maximum Number of Colinear Points

Link: https://leetcode.com/problems/max-points-on-a-line/

The brute-force solution is somewhat clear: for each line between two points, check how many points it hits and return the max. The tricky part ends up being how you store a line:

class Solution: def maxPoints(self, points: List[List[int]]) -> int: if len(points) < 2: return len(points) d = {} dx = {} for i in range(len(points)): for j in range(i+1,len(points)): x1 = points[i][0] y1 = points[i][1] x2 = points[j][0] y2 = points[j][1] if x1 != x2: m = (y2-y1)/(x2-x1) b = y1 - m*x1 m2 = round(m,10) b2 = round(b,10) if (m2,b2) in d: d[(m2,b2)] += 1 else: d[(m2,b2)] = 1 else: if x1 in dx: dx[x1] += 1 else: dx[x1] = 1 m1 = max(d.values()) if len(d.values()) > 0 else 0 m2 = max(dx.values()) if len(dx.values()) > 0 else 0 if m1 > m2: pair = max(d,key=d.get) m = pair[0] b = pair[1] tot = 0 for k in range(len(points)): if math.isclose(points[k][1],m*points[k][0]+b): tot += 1 return tot else: x = max(dx,key=dx.get) tot = 0 for k in range(len(points)): if points[k][0] == x: tot += 1 return tot

## Median of Two Sorted Arrays

Link: https://leetcode.com/problems/median-of-two-sorted-arrays/

First of all, an O(n+m) solution is easy: merge the two arrays in O(n+m) time and return the median. But if we want a logarithmic solution, we have to repetitively halve the problem.

Both are sorted, so we can binary search them "together" somehow. Perhaps we can start with a bound on the median and tighten it.

By looking through a few examples, I identified an optimal substructure: the overall median will sit somewhere between the first median and the second, which means we can sort of knock of half of the array left of the lower median, and half of the array right of the greater median. The name of the game ended up being properly addressing edge cases:

def getMedianSorted(l,r,n): # if empty, return anything if r <= l: return -42069 i = (l+r) // 2 m = 0 if (r-l) % 2 == 0: m = (n[i-1] + n[i]) / 2 else: m = n[i] return m def getMedianWithExtras(n,l,r,e): if (r-l) % 2 == 0: i = (r+l)//2 - 1 a = sorted(n[i-len(e):i+len(e)+2]+e) return getMedianSorted(0,len(a),a) else: i = (r+l)//2 a = sorted(n[i-len(e):i+len(e)+1]+e) return getMedianSorted(0,len(a),a) class Solution: def getMedian(self,l1,r1,l2,r2): # if one is empty, we return the median of the other if l1 == r1: return getMedianSorted(l2,r2,self.nums2) if l2 == r2: return getMedianSorted(l1,r1,self.nums1) # next check the medians m1 = getMedianSorted(l1,r1,self.nums1) m2 = getMedianSorted(l2,r2,self.nums2) if m1 == m2: return m1 if r1-l1 < 6 and r2-l2 < 6: arr = sorted(self.nums1[l1:r1]+self.nums2[l2:r2]) return getMedianSorted(0,len(arr),arr) # we may get to a case where 1 array has 2 elements, which we can't reduce! if r1-l1 < 3: return getMedianWithExtras(self.nums2,l2,r2,self.nums1[l1:r1]) if r2-l2 < 3: return getMedianWithExtras(self.nums1,l1,r1,self.nums2[l2:r2]) numOutL = int((r1-l1-1)//2) numOutR = int((r2-l2-1)//2) numOut = min(numOutL,numOutR) if m1 < m2: return self.getMedian(l1+numOut,r1,l2,r2-numOut) else: return self.getMedian(l1,r1-numOut,l2+numOut,r2) def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float: # it is given that m+n >= 1 self.nums1 = nums1 self.nums2 = nums2 return self.getMedian(0,len(nums1),0,len(nums2))

## How many trailing zeroes in `n!`?

Link: https://leetcode.com/problems/factorial-trailing-zeroes/ A good application for the fundamental theorem of arithmetic!

class Solution: def getPrimesInFact(self,prime,fact): acc = 0 i = prime while i <= fact: acc += fact // i i *= prime return acc def trailingZeroes(self, n: int) -> int: twos = self.getPrimesInFact(2,n) fives = self.getPrimesInFact(5,n) return min(twos,fives)

It wasn't until after looking at the solution that I realized that
the prime factorization of `n!` is always saturated with twos! The
first call to `getPrimesInFact` is unnecessary.