Category Archives: Recursion

Binary Tree, Interview Questions, Recursion

Longest Univalue Path (Leetcode)

This leetcode question is interesting. It is from my archives. Originally, I misunderstood and thought you could only look for paths going “down”, but obviously as illustrated the question also admits “sideways” paths, see the second example.

Curiously, I was able to adapt my solution for the simpler interpretation and extend it to work for the more complicated interpretation too! Here is the code:

class Solution(object):
    def bottomUpBuilder(self, root):
        if root is None: return
        
        self.bottomUpBuilder(root.left)
        self.bottomUpBuilder(root.right)
        
        # can we continue a path from either of our children?
        self.longestPath[root] = 0
        if root.left and root.left.val == root.val:
            lval = self.longestPath[root.left]+1
            self.longestPath[root] = lval
        if root.right and root.right.val == root.val:
            rval = self.longestPath[root.right]+1
            self.longestPath[root] = max(self.longestPath[root], rval)
            
        # Can we join a path between our two children?
        # Note, crucially, that we're using "longestPath" for our child values;
        # we can't use asJoin because that would suggest a degree-3 node in our "path".
        self.asJoin[root] = 0
        if root.left and root.right and root.left.val == root.val and root.right.val == root.val:
            self.asJoin[root] = self.longestPath[root.left] + self.longestPath[root.right] + 2
    def longestUnivaluePath(self, root):
        self.longestPath = {}
        self.asJoin = {}
        self.bottomUpBuilder(root)
        m = 0
        for r in self.asJoin:
            m = max(m, self.asJoin[r])
        for r in self.longestPath:
            m = max(m, self.longestPath[r])
        return m

Discussion

You can see that there are basically 2 maps built, not just one. The asJoin map handles the case I forgot about.

So I can see this question as a nice one-two sort of question: first solve my simpler case, and then “can you extend that to the sideways case”? Well, the key insight that allows us to extend our code is hinted at in the comments: the asJoin map is defined in terms of longestPath, we don’t want to define it recursively.

This has a nice bottom-up iteration, and some neat invariants and applications. This question, on Leetcode, also has a certified solution. What is that solution? Let’s see.

Leetcode Solution Discussion

OK, it’s a more elegant recursive formulation (maybe?), and doesn’t admit my “extension” idea. Understanding why it’s linear-time is an interesting exercise.

More trees here, more recursion here.

Interview Questions, Recursion

Permutation Sequence (Leetcode)

I’ve decided to call this permutation sequence question a “classic problem” because it is I think a very reasonable combinatorics/counting question. Also, the problem is marked as a “Leetcode Hard”, so I figure I should get one of those on this blog before too long.

Discussion and Approach to Solution

As a change of pace, I tried to see what it would be like to make a “literate code” approach. This, uh, didn’t work. I ended up with a block comment above the code, so I’ve extracted that out here:

for [1, 2, 3, 4], we have 3! sequences that begin with 1, 3! that begin with 2, etc… so we end up with 4 * 3! = 4!, that checks out. So in general, if we have a size-n set, there are n! distinct values, and the first (n-1)! begin with 1, then the next (n-1)! begin with 2, etc. This reasoning applies recursively. So we want to find the highest “m” in [1, n] such that (m-1)(n-1)! < k (or equiv, the smallest m such that m(n-1)! >= k. Maybe that’s a better formulation). Note the “punning” between m as an element of the remaining set, and n as the count of elements left in the set. In turn, m is the index of the m’th largest element, not literally the value m.

So that’s a terse comment. To take a step back:

If we consider the n! possible permutations of [1..n], in lexicographical order, the first (n-1)! begin with 1, the next (n-1)! begin with 2, and so on. This leads to n sub-sequences of length (n-1)!, and we can be confident that the concatenation of these sequences gives us the original sequence back, as there are n*(n-1)!=n! elements altogether.

This suggests an analogy to digits (if we consider the sequence [0..999], the first 100 “begin” with 0, the next 100 begin with 1, and so for 10 times, leading to 100*10 = 1000 elements). We can repeat this recursively, for the sequence [0..99] there are again 10 sub-sequences. Unspooling the recursive reasoning, it means we can “index” into that sequence by looking at successively-lower-magnitude digits. This feels like a no-op because it’s sort of what we already do with normal indexing.

With this factorial-esque indexing, there are n biggest-“digit” sequences, then n-1 next-digit-sequences, and so on. The formulation in the code below is not explicitly recursive, but instead currentIndex is basically, well, the index of the implicit sequence of [result + start]. And we select certain elements from start to “increment” our currentIndex.

Code

class Solution(object):
    def getPermutation(self, n, k):
        # for [1, 2, 3, 4], we have 3! sequences that begin with 1, 3! that begin with 2, etc...
        # so we end up with 4 * 3! = 4!, that checks out.
        # So in general, if we have a size-n set, there are n! distinct values,
        # and the first (n-1)! begin with 1, then the next (n-1)! begin with 2, etc.
        # This reasoning applies recursively.
        # So we want to find the highest "m" in [1, n] such that (m-1)(n-1)! < k
        # (or equiv, the smallest m such that m(n-1)! >= k. Maybe that's a better formulation).
        # Note the "punning" between m as an element of the remaining set, and n as the *count*
        # of elements left in the set. In turn, m is the *index* of the m'th largest element, not
        # literally the value m.
        def fact(n):
            res = 1
            for i in range(1, n):
                res *= i
            return res
        result = []
        start = list([i for i in range(1, n+1)])
        currentIndex = 1
        while currentIndex != k:
            # find the smallest m. Careful reasoning about indexing
            # to avoid off-by-one errors (1-indexed the range of permutations,
            # but m itself should be zero-indexed as it goes into `start`)
            incrementN = fact(len(start))
            m = -1
            for m in range(len(start)):
                # My one bug: I left out the "currentIndex + " part, which lead
                # to an interesting behavior: n=5, k=1 and n=5, k=120 both passed without this!
                if currentIndex + (m*incrementN) > k:
                    m -= 1
                    break
            # remove m from start, we've selected it
            assert(m >= 0 and m < len(start))
            result.append(start[m])
            start.pop(m)
            currentIndex += m*incrementN
        
        # At this point we know we should emit the "0th" remaining permutation.
        # Some subtlety in making sure we're appending to result in the same "direction"
        # as done in the while loop
        result += start
        return ''.join(map(str, result))

Discussion as an interview question

This is a hard-core question about recursive reasoning. I’m not sure about its appropriateness. As notes for my own attempt, while I didn’t recall my approach I did actually implement this code a long, long time ago, and in a previous form of this blog talked about the general approach. You can see my older implementation (when I was literally studying enumerations) is much better. So in revisiting this I was able to recall the broad strokes of a way that would work, and then take it from there.

Discussion general

This is a really neat computer science problem! I have a soft spot for enumeration problems, and have enjoyed jumping into Knuth 4A a few times particularly for Gray codes. I have dreams of using those to help provide exhaustive test suites for other combinatoric algorithms, but I just don’t have the time. There is a lot of depth to this topic I’m not familiar with; reconciling my “analogy” with the more in-depth treatment of Factorial Number Systems is something I should do one day.

More recursive problems (which I guess will include enumeration problems?) here.

Interview Questions, Recursion

Evaluate Reverse Polish Notation (Leetcode 37)

This was a homework assignment in my intro-to-data-structures-and-algorithms course. Evaluating an expression in this way is a good exercise. While it’s not literally recursion, I’ve tagged it as such because it uses those ideas. (And there doesn’t seem to be a better category.) These sort of questions, I think, are to Leetcode’s merit: a student (assuming they don’t cheat, of course) can really use this to test their understanding.

Having already known the answer, and not yet subjecting any of my students to this, it’s hard for me to anticipate what the tricky parts of this question are. I assume the key insight is that you can push (what Python calls append) the intermediate values back on the stack and it “just works”. Maybe that follows from reading carefully what RPN is?

The motivation for this problem is that it’s an easy calculator to make, and compilers.

class Solution:
    def isOp(self, s):
        return s in ['+', '-', '*', '/']
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for t in tokens:
            if self.isOp(t):
                r = stack.pop()
                l = stack.pop()
                if t == '+': x = l + r
                elif t == '-': x = l - r
                elif t == '*': x = l * r
                elif t == '/': x = int(l / r)
                stack.append(x)
            else:
                stack.append(int(t))
        return stack[0]

Postscript

Is this a good interview question? I don’t know. At a big meeting about interview questions, a work colleague said that they always ask this one as their standard interview question. So that’s one vote! I don’t think there’s trickiness per-se, and I think the parsing and case-handling here is an interesting and good exercise.

I am in parallel trying to build a collection of “classic” problems for students, under this tag.

Binary Search Tree, Recursion

Validate Binary Search Tree (Leetcode 36)

1 Comment

This “medium” problem does present a nice way where an initial solution (i.e., mine) has lots of room for improvement. Assuming the student knows what a binary search tree is and is fairly comfortable with them, and recursion, this is an excellent homework problem. In a sense, it’s taking the invariants of a binary search tree, and taking them a step further and applying them to solve a new problem, validation. While this is a bit contrived, I think validation for a datastructure has good-enough motivation.

The solution code is a bit bigger than typical, and I bet it can be made a lot smaller and more efficient. I just was confident this would work, so I went that way. An opportunity, later, to discuss how to improve code after-the-fact?

Solution Ideas

  1. All nodes to the left of our “root” (and remember we’re going to look at every node as its own root) should be smaller than us. So we’d like to know what the largest value to our left is—if we’re bigger than that, then we’re OK. Similarly, we want to know the smallest value to our right [Note: terrifyingly, as I was writing this, the “we want to know the smallest value to…” auto-complete filled in “to our right”! I suppose it saw the opposites of larger and smallest, and mapped that to right/left? Spooky!].
  2. So I imagined as if I knew the min-and-max values for each node. If we had that attached to each node, we can simply query our immediate children and see what they each have as their min/max values. If our value is smaller than the max of our left, or larger than the min of our right, we are not a valid BST.
  3. Additionally, if we have the min/max values of our children, we can easily compute the min/max values of ourselves.

Finding the min or max value of a tree is an easy-enough recursive exercise. Doing both at the same time is a nice sequel. Doing it for all node is itself an interesting problem: I haven’t done out the arithmetic, but the temptation to do it “purely recursively” would lead to a very expensive algorithm. I don’t know if it’s quadratic per-se, but it sounds like “for each node, walk the tree”. So you want a very deliberate bottom-up approach.

Conclusion

My solution is a bit of a hybrid where I set the stage for a two-pass approach, computing global maps for the nodes, but then realized I could determine a BST violation while computing the maps. I bet we can get rid of the maps and turn this into a more typical recursive formulation. Later!

class Solution:
    def solution(self, root):
        if root is None:
            self.minMap[root] = None
            self.maxMap[root] = None
            return True
        
        l = self.solution(root.left)
        if not l: return False # might as well stop
        
        r = self.solution(root.right)
        if not r: return False
        
        lm = self.maxMap[root.left]
        if lm is not None and lm >= root.val:
            return False
        
        rm = self.minMap[root.right]
        if rm is not None and rm <= root.val:
            return False
        
        rMax = self.maxMap[root.right]
        if rMax is None:
            rMax = root.val
        lMin = self.minMap[root.left]
        if lMin is None:
            lMin = root.val
        
        self.maxMap[root] = rMax
        self.minMap[root] = lMin
        
        return True
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # Observation: if we check each node, we'll be doing something that feels
        # a little bit too "quadratic" (for each node, validate the rest of the tree)
        # What we can do is build a map of nodes to min/max values under that tree,
        # and then do another pass (in parallel?) to do the final validation.
        # So, in other words:
        
        # Silly initializatio
        self.minMap = {}
        self.maxMap = {}
        return self.solution(root)

More BST questions can be found here.

Interview Questions, Recursion

Tribonacci (Code Wars 4)

1 Comment

Let’s compute the complete Tribonacci (riff off of “Fibonacci”) sequence.

It’s worth a few minutes understanding and “visualizing” what the solution might look like. In this case, I just mean that we’re going to be returning a list. Moreover, (most of) the elements in that list are computed by prior elements in that list. The list is going to be n elements long (the same n as is a parameter to our function).

One of my favorite exercises: dealing with the edge/easy cases.

  1. If n is 0, we can return the empty list.
  2. If n is less than or equal to the number of elements in signature, we can just return that appropriate subsequence.
  3. Otherwise, we already have enough elements in signature to compute all the other elements we need.

And that’s the answer:

def tribonacci(signature, n):
    if n == 0:
        return []
    if n <= len(signature):
        return signature[:n]
    result = signature[:]
    for i in range(3, n):
        s = result[i-1]+result[i-2]+result[i-3]
        result.append(s)
    return result

Additional Thoughts

  1. The slice on line 5 may not be available in all languages; it will just be more verbose, if slicing isn’t available, with the spirit being the same.
  2. I think sometimes we’re returning a shallow copy (line 5), otherwise a deep copy. Probably not ideal. I wouldn’t let this pass code-review.
  3. We often have for loops that go over an array of length n. Here we’re creating an array of length n. That’s a fun contrast.
  4. This sort of algorithm, where we build the contents of the list based off of previous elements, hasn’t come up very often in my professional experiences. I suppose it’s neat to see what that kind of code looks like, though I think it doesn’t add much versus other, more applicable loop questions.

I’d categorize this question as one in the “recursion” topic. You can find all such questions on this site here.