Monthly Archives: September 2022

Interview Questions, Sorting

Sort Array By Parity (Leetcode 34)

1 Comment

Still working through the archives. This is another interesting problem, similar to the robots one, where it’s not strictly an algorithmic problem. The intention of this question is clearly not about implementing a sorting algorithm, but an exercise showing that you’re familiar with the idea of passing in a custom sort-predicate. As I think about this question I think it has value in a very targeted situation.

def parityKey(x):
    return x % 2
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        nums.sort(key=parityKey)
        return nums

Application to Interviewing

If I had to use this question for interviewing, I would compare a solution like the python above to the C++ solution below. This shows two (slightly) different APIs, and how to adapt them. There’s no reason why we couldn’t “just” use the same value-mapping approach the Python implementation suggests (just have int xOdd… and do the < comparator as usual), but here we get the added benefit of having each sub-sequence sorted.

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        std::sort(std::begin(nums), std::end(nums),
                 [](int x, int y) {
                     bool xOdd = x % 2;
                     bool yOdd = y % 2;
                     if (xOdd == yOdd) {
                         return x < y;
                     }
                     if (xOdd) {
                         return false;
                     }
                     return true;
                 });
        return nums;
    }
};

Application

As I think more about this, I would think this is a nice question to lecture on, or share as a bit of trivia. Maybe asking the original question as an exercise, to help introduce the idea of a sorting API and passing functors, is useful. I think this is too pointed (you either know about the API idea or not) for an interview question. I want to see if there’s something more general to help students take-away with the difference between the Python and C++ approach. With more material, maybe an idea will become clearer.

I believe this is the first question on sorting; more will be listed here.

Interview Questions, Introductory

Robot Return to Origin (Leetcode 33)

I guess I have a lot of archives. This question is mainly about reasoning-by-cases, which is a way of handling a question that isn’t explicitly called out so well by the usual exercise batteries, in my experience (it’s neither a data structure nor an algorithm, not really).

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = 0
        y = 0
        for m in moves:
            if m == 'U': y += 1
            if m == 'D': y -= 1
            if m == 'R': x += 1
            if m == 'L': x -= 1
        return x == 0 and y == 0

Discussion

  1. The question is of course contrived, but I think it’s a good exercise in initial practice in “understanding a question” and translating that to a programming-amenable approach.
  2. The question does invite overthinking it, I would guess. Hopefully not everyone, but I can see a student panicking and starting to make an array-of-arrays. Knowing that sometimes you don’t have to do the hardest thing you can think of is very valuable in interviews and in practice!

I don’t know really know a general category to put this in. I’ll call it an introductory interview question, and collect any more here.

Binary Search Tree, Binary Tree, Interview Questions

Trim a Binary Search Tree (Leetcode 32)

Another one from the archives. Similar to the merge-binary-trees question, I think this is a nice exercise for students are starting to feel comfortable with the “classic” questions. I think this problem has some natural-enough motivation, and for the student to be confident in their solution, they’d need to be confident in their recursive reasoning.

class Solution:
    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        if root is None: return None
        if root.val < low: return self.trimBST(root.right, low, high)
        if root.val > high: return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)
        return root

Discussion Points

  1. We still have that classic “skeleton” of handling-the-base-case, and then building up our solution from smaller trees (recursive calls).
  2. I think the big conceptual jump is the confidence of being able to return the empty tree (None or null or whatever) even when the tree isn’t “originally” the empty tree, and know that it will percolate up correctly in the previously recursive invocations.
  3. As always it’s not that this problem literally comes up in practice, but taking some “database” and preprocessing it according to some later filter is good. For people who have a passion for functional programming, this is nothing but a particular filter applied to a tree instead of a list.

In fact as I think about it, the idea of this being a tree filter may be a particularly compelling one. This uses the particulars of the filter, and the particulars of the BST, to optimize. Having a first form be “handle an arbitrary tree” and then “optimize this if you know the tree is a BST”, that may be a nice interview sequence.

All BST questions are collected here; other binary-tree questions are here.

Binary Search Tree, Interview Questions

Merge Two Binary Trees (Leetcode 31)

Another from the archives. Part of a big battery where I went through a lot of tree problems, I guess. I wouldn’t call this problem a classic one (versus, say, Tree Equality), but I think it’s a nice “classroom” exercise on making sure someone feels fluent in tree-manipulation.

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # destructive operation
        if root1 is None:
            return root2
        if root2 is None:
            return root1
        
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        
        return root1

Discussion Points

  1. This follows the classic “skeleton” of solving binary tree problems with recursion. We handle (in the case, the 2) “base cases” of when the tree(s) are null; we solve the smaller cases, and we combine those results to synthesize the new tree.
  2. In this case we treat the operation as wholly destructive. When I help newer programmers, that’s a concept they are often unfamiliar with. Here we are unusually destroying both trees (I’m sure we can solve this without destructive operations; that’s a fun follow-up in many circumstances).
  3. I think that we reassign the left and right children of root1, and in general do some subtle interactions between subtrees, makes this a good next-level exercise. A lot harder than, say, incrementing all the values in a single tree by 1!

All solved tree exercises in this blog series can be found here.

Interview Questions, Matrix

Reshape the Matrix (Leetcode 30)

I decided to redo this problem, from the archives in Python. Previously I had it in C++. You’d think this post, then, of resizing a 2D array, would have been straightforward. Here are some notes:

  1. The key insight (in my approach, at least) is that assuming the resize is valid, there are r*c elements, and we can define helper functions like getRow and getColumn that take an i, and an r, c dimensions, and return the row and column of the ith element. In this way we can walk through the arrays “in parallel”
  2. I hit an issue with some terse way of allocating an array in python. It seems something like [[0]*c]*r leads to shallow copies in some cases, and that tripped me up.
  3. Then, of course, I managed to get R and C mixed up.

I think this is a good exercise for junior people who say they feel comfortable with 2D arrays.

Complete with debugging statements, here is my approach:

def getRow(i, r, c):
    #print('row of', i, '-th element in matrix ', r, '*', c, 'is', i // c)
    return i // c
def getCol(i, r, c):
    return i % c
class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        R = len(mat)
        if R is 0: return mat
        
        C = len(mat[0])
        
        if R * C != r * c:
            return mat
        
        res = []
        for i in range(r):
            res.append([])
            for j in range(c):
                res[i].append(0)
        
        for i in range(r*c):
            #print(getRow(i, r, c), getCol(i, r, c), getRow(i, R, C), getCol(i, R, C))
            old = mat[getRow(i, R, C)][getCol(i, R, C)]
            res[getRow(i, r, c)][getCol(i, r, c)] = old
                
        return res

Take-Aways

This covers interesting questions like allocation (pre-allocating the results array), bounds-checking in a nontrivial setting (numrows, numcols), and then an interesting question of mapping. That mapping also really requires a comfort with indices versus the values of an array, plus array-of-arrays instead of just arrays. I think this is a good “hard” phone-screen question.

For real-world applicability, I’ve never worked too much with 2D arrays, certainly not this explicitly. However, the challenge of iterating over 2 different objects/data-structures that don’t naively both map to the same for loop (so to speak), that’s something that comes up a lot, albeit not so directly as in this code. Just recently I was iterating over 2 similar (but not the same!) trees at work, and had to make sure the iteration remains in lockstep. Of course, this complex-iteration also comes up in my favorite merge-linked-list sort of questions. Again, not literally identical, but the same “genus”.

Binary Search Tree, Interview Questions

Range Sum of a BST (Leetcode 29)

Another one from the archives. This is a nice extension or sequel question to the core “find a value in a BST”, it stretches one’s experience with recursion (assuming that’s your approach). It may be a nice phone-screen question or similar.

The question pre-populates a solution, one that’s recursive but is inefficient. I don’t know how I feel about that, as presenting this. It sort of keeps it focused on what’s new about the problem, which I like, but it may also be distracting? I’ve seen people fixate on existing code and inadvertently box themselves in. (Edit: or maybe not? Maybe that was my existing code? Well, without accusing the question-author, this paragraph is a general question I’d like to consider.)

class Solution:
    def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
        if root is None: return 0
        if root.val > high:
            return self.rangeSumBST(root.left, low, high)
        if root.val < low:
            return self.rangeSumBST(root.right, low, high)
        return self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high) + root.val

What’s interesting to me is that it isn’t obvious how many iterations this would go through. I think that’d be an interesting question for someone who seems very adroit in reasoning about the runtime of other recursive algorithms.

Interview Questions, Strings

Isomorphic Strings (Leetcode 28)

I like this one a lot! Also from the archives. This one is listed as easy, I would say it’s on the harder side of easy. The word “isomorphism” is a bit gnarly, but you can ignore that. I’d rather this be introduced as a Caesar cipher, but maybe that’s also confusing, or makes the possible answer too clear. But if the question is “are you comfortable talking about isomorphism”, well, that’s not a very good question. So I suppose I’d phrase this as a Caesar cipher.

The interesting challenge is, well, distinguish an isomorphism from a homomorphism. Vaguely, the idea of distinguishing this “uniqueness” (invertibility) property is nice. Maybe to enable something like dictionary encoding? I’m trying to brainstorm how to motivate this question and give it some application-justification. In any case…

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # Easy cases
        if len(s) != len(t):
            return False
        
        mapping = {}
        mapped = set([])
        for i in range(len(s)):
            sc = s[i]
            tc = t[i]
            if sc in mapping:
                if mapping[sc] != tc:
                    return False
            elif tc in mapped:
                # uniqueness condition
                return False
            else:
                mapping[sc] = tc
                mapped.add(tc)
        return True
Interview Questions, Strings

Group Anagrams (Leetcode 27)

Another from the archive. This is a nice warm-up or introductory interview question. It is a bit contrived, but I think it exercises a few common tools you’d want to use. You want to group things together that share a common property, and so you want to compare the property but group the things-actual.

Here I use defaultdict, but that’s just out of convenience. I don’t like how to create a sorted string in Python, I wonder if there’s a better way.

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        d = defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            d[key].append(s)
            
        res = []
        for k in d:
            res.append(d[k])
        return res
Interview Questions

Monotonic Array (Leetcode 26)

Another from the archives. I think this is a nice introduction to a more “stateful” complicated loop. A productive approach was to break it into cases. I think this is a nice introduction to state machines.

class Solution {
    public:
    enum class dir {
        UNKNOWN,
        INCREASING,
        DECREASING
    };
    bool isMonotonic(vector<int>& nums) {
        auto state = dir::UNKNOWN;
        for (int i = 1; i < nums.size(); i++) {
            switch (state) {
                case dir::UNKNOWN:
                    if (nums[i-1] < nums[i]) {
                        state = dir::INCREASING;
                    }
                    else if (nums[i-1] > nums[i]) {
                        state = dir::DECREASING;
                    }
                    break;
                case dir::INCREASING:
                    if (nums[i-1] > nums[i]) {
                        return false;
                    }
                    break;
                case dir::DECREASING:
                    if (nums[i-1] < nums[i]) {
                        return false;
                    }
                    break;
            }
        }
        return true;
    }
};
Interview Questions, Matrix

Transpose of Matrix (Leetcode 25)

Another from the archives. This is a “real” matrix question (versus an array-of-arrays). For the people I’ve helped enter into the tech world, the bigger challenge is the vocabulary of matrix math, rather than the actual array-of-array machinery or similar. I like this one as an operation, and I’m glad it takes the time to color and otherwise illustrate what the transpose is.

In a way the straightforward solution may seem “cute”, you “just” need to swap the i/j indices. I think, however, that that’s a real insight, and a real insight you can get in an interview setting. Maybe other people would disagree. I think you can also get there the “brute force” way of just carefully thinking about what to do. The larger challenge is allocating the transpose matrix correctly.

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        if len(matrix) == 0: return []
        T = []
        for j in range(len(matrix[0])):
            T.append([])
            for i in range(len(matrix)):
                T[j].append(matrix[i][j])
        return T