Monthly Archives: December 2021

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.