All posts by Aaron

Binary Tree, Interview Questions

Min Depth of Binary Tree (Leetcode 14)

Leave a comment

This one is interesting. It tricked me, I had answered the wrong question at first! It is curious how it defines the depth, that it requires a leaf node. I was computing something else, something like max height.

This one’s interesting because it provides a somewhat (unless if I’m missing something) complicated inductive case. Good to know!

class Solution(object):
    def minDepth(self, root):
        if root is None:
            return 0
        lDepth = self.minDepth(root.left)
        rDepth = self.minDepth(root.right)
        # Were we a leaf?
        if lDepth is 0 and rDepth is 0:
            return 1
        if lDepth is 0:
            return rDepth + 1
        if rDepth is 0:
            return lDepth + 1
        return min(lDepth, rDepth) + 1
Binary Tree, Interview Questions

Univalued Binary Tree (Leetcode 13)

Leave a comment

I think I want to do a battery of tree exercises. Here’s one. The names some of these community-contributed questions come up with are quite striking.

We can either think about maintaining some global, “ah, here is the value we should compare again”, or we can exploit the transitive nature of equality.

class Solution(object):
    def isUnivalTree(self, root):
        if root is None: return True
        if root.left is not None and root.left.val != root.val:
            return False
        if root.right is not None and root.right.val != root.val:
            return False
        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

Hey, let’s do the global approach too, why not. Well, not global exactly, but you know.

class Solution(object):
    def isUnivalTreeInternal(self, root):
        if root is None: return True
        if root.val != self.val: return False
        return self.isUnivalTreeInternal(root.left) and self.isUnivalTreeInternal(root.right)
    def isUnivalTree(self, root):
        if root is None: return True
        self.val = root.val
        return self.isUnivalTreeInternal(root)
Interview Questions

Longest Common Prefix (Leetcode 12)

Leave a comment

This is another good one, I think. Strings and arrays are commonly-requested topics.

  1. We can observe that “the first string must contain the longest common prefix”. That’s an interesting tool that we can leverage.
  2. So we know that we can iterate over that length. We want to “scan” all the strings in parallel, and that’s how.
  3. We have an interesting “return from a nested loop” potential. Helper functions may make this clearer. Potential sequel homework.
class Solution(object):
    def longestCommonPrefix(self, strs):
        if len(strs) == 0:
            return ""
        root = strs[0]
        if len(root) == 0:
            return ""
        
        prefixLen = 0
        for i in range(len(root)):
            for s in strs[1:]:
                if i >= len(s):
                    return root[:prefixLen]
                if s[i] != root[i]:
                    return root[:prefixLen]
            prefixLen += 1
        return root

Interview Questions

Count characters in a string (Code Wars 11)

Leave a comment

This one’s a classic! I’m a big fan of this as a warm-up question. A simple exercise of looping, strings, exercising two different cases with dictionaries (what if the key already exists, what if it’s new), and best of all it’s a pretty reasonable distillation of real programming scenarios.

def count(string):
    m = {}
    for c in string:
        if c in m:
            m[c] += 1
        else:
            m[c] = 1
    return m

I’m sure there are very fancy ways of doing this. I’d rather use a default-dictionary, but otherwise I’m happy with this solution.

Interview Questions, Linked List

Remove Duplicates from Sorted LL (Leetcode 11)

Leave a comment

There is definitely a pattern! Sorted array, and previously move zeros. Well this has no relation to the remove-zeros, but it’s interesting….

This suggests an interesting lesson as well, three variations on a theme. That’s why I’m doing these things.

class Solution(object):
    def deleteDuplicates(self, head):
        if head is None:
            return head
        curr = head
        while curr is not None and curr.next is not None:
            while curr.next is not None and curr.val == curr.next.val:
                curr.next = curr.next.next
            curr = curr.next
        return head

I bet there’s a nicer way of writing that loop. It’s interesting that this logic “feels” neater to me (especially if my suspicion of a nicer way of writing that loop bears out.)

Nested loops with linked lists! Neat.

Interview Questions

Search Insert Position (Leetcode 10)

Leave a comment

Why don’t they just call it binary search? The runtime requirement is a giveaway — and for people who are “fluent” enough with runtime complexity to understand O(lg n) but don’t yet know about binary search, you are a rare breed, I’d think.

So I’ll spare you the usual C++ std::algorithm implementation. I like this loop. I think a lesson where we really 100% understand the intuition behind binary search, and then having students actually implement it, could be a nice hour.

class Solution(object):
    def searchInsert(self, nums, target):
        lb = 0
        ub = len(nums)
        while lb < ub:
            mid = (lb+ub)/2
            #print(lb, mid, ub)
            
            searchValue = nums[mid]
            
            # Feels hacky... can we do something smarter?
            if mid == lb:
                assert(ub == lb + 1)
                if searchValue < target:
                    return ub
                return lb
                
            if searchValue > target:
                ub = mid
            elif searchValue < target:
                lb = mid
            else:
                return mid
        #print("done", lb, ub)
        assert(lb == ub)
        return lb
Interview Questions

Remove Duplicates from Sorted Array (Leetcode 9)

Leave a comment

This is the warm-up sort of problem to one we’ve seen earlier. The solution is the same spirit.

This is a nice example (finally!) of my drumbeat that a lot of these problems are really reflections of the same “root” problem. While there are still many such root problems, after a while you start to see repetitions, in addition to the shared fundamental material of course.

So we have the same sort of solutions. The first is the C++ algorithm, which is likely “too close to the real problem”. The interviewer would naturally ask “please implement the “unique” function you use there.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto new_end = std::unique(std::begin(nums), std::end(nums));
        return std::distance(std::begin(nums), new_end);
    }
};

So let’s do that in Python. There is probably a similar-enough algorithm, but ironically let’s just do a much more explicit version.

class Solution(object):
    def removeDuplicates(self, nums):
        i = 0
        j = 0
        while i < len(nums):
            nums[j] = nums[i]
            j += 1
            new_i = i + 1
            while new_i < len(nums) and nums[i] == nums[new_i]:
                new_i += 1
            i = new_i
        return j

I actually really like this question. There are multiple ways of solving it. The loops involved here are understandable, but different from the “cliche” for-loops. They also start the idea of having 2 different indices into the same array, a powerful tool that a lot of novice programmers seem pretty surprised by.

Interview Questions, Linked List

Flatten a Doubly-Linked List (Leetcode 8)

Leave a comment

Isn’t this basically the same as the last one? Instead of left and right it’s “child” and “next”. The doubly-linked stitching is a bit different, but nothing major. Interesting contrast.

class Solution(object):
    def flatten(self, head):
        if head is None:
            return None
        if head.child is None:
            self.flatten(head.next)
            return head
        flatChild = self.flatten(head.child)
        head.child = None

        childEnd = flatChild
        while childEnd.next != None:
            childEnd = childEnd.next
        
        
        oldNext = head.next
        if oldNext:
            oldNext.prev = childEnd
        childEnd.next = oldNext

        flatChild.prev = head
        head.next = flatChild
        
        return head
Binary Tree, Interview Questions

Flatten Tree (Leetcode 7)

1 Comment

I think this question has a lot of potential. It is very algorithmic-y, but also has an idea that can come up in practice. Flattening a 2D object like a tree into a 1D object like a list happens in, e.g., the unit utility ls or the Window’s equivalent dir. However, the idea of keeping that same object in memory, and “punning” the linked-list structure over the tree structure, seems unneeded. Saving memory is great and I think we’re much too inclined to think memory is “free”, but from an pedagogical perspective we’re building off of a number of concepts.

Prerequisites and Solving

Of course the student should be very comfortable with typical recursion-and-binary-trees material. They should also be comfortable with updating pointers, like with complicated linked-lists questions (say, my favorite question of merging two linked lists).

Once we have all that, considering the question-actual: The “child management” is a bit tree-specific, but I think that’s OK (we’re allowed to talk about trees sometime). The idea of transforming the tree in question I think helps illustrate the power of recursion — many of the questions I’ve been thinking of don’t mutate the input.

One complication that caught me: You really have to account for both children, even the one you want to leave empty. I think this is a good “tough” question. I guess Leetcode calls it medium, sure. I’ve collected all my tree solutions here.

class Solution(object):
    def flatten(self, root):
        if root is None:
            return None
        root.right = self.flatten(root.right)
        if root.left is None:
            return root
        
        flatLeft = self.flatten(root.left)
        root.left = None
        t = flatLeft
        while t.right is not None: t = t.right
        t.right = root.right
        
        root.right = flatLeft
        return root
Binary Tree, Interview Questions

Depth of Binary Tree (Leetcode 6)

Leave a comment

I’m pretty sure I got this as a test question in “CS 102”, my data structures and algorithms course. The depth (or the height) of a tree. I really like phrasing this as the height of the tree, to be honest. My solution, as you see below, involves “adding 1” to the children’s depth. Especially if this is used as a teaching exercise, focusing on height helps avoid unneeded difficulties.

When we go over it in review sessions I’ve found students are often confused by the definition of the problem itself. It invites off-by-one errors, and also depth-versus-height. Especially when we say “now add one to the depth” — well, why are we increasing the depth as we go up the tree? It may be clear after-the-fact, but that can even detract from the satisfaction of solving it. If you can get them past that (or cleverly avoid them having to consider that aspect at all) it’s a great exercise.

Oh, and in this particular problem description, the math-y definition invites a certain implementation (ah, trace paths through the tree, very explicitly!). I think that’s a valuable thing to consider, the idea that a mechanical definition may very well different substantively from the “real” implementation, but I would rather introduce that idea outside the context of an interview or academic question. More like lecture material.

class Solution(object):
    def maxDepth(self, root):
        if root is None:
            return 0
        leftDepth = self.maxDepth(root.left)
        rightDepth = self.maxDepth(root.right)
        maxChild = max(leftDepth, rightDepth)
        return maxChild + 1

More binary tree material can be found here.