All posts by Aaron

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
Interview Questions, Linked List

Remove Linked List Elements (Leetcode 24)

Another removal-question. Another from the archive. Again the trickiness case is usually if the very-first or very-last element should be removed. I find this is another nice exercise giving the opportunity to think carefully about different cases happening inside a loop.

class Solution(object):
    def removeElements(self, head, val):
        # base case: remove from head until not equal to val
        while head is not None and head.val == val:
            head = head.next
        
        if head is None:
            return None
        
        t = head
        while t.next is not None:
            if t.next.val == val:
                t.next = t.next.next
            else:
                t = t.next
        
        return head
Binary Search, Interview Questions

Peak Index Mountain Array (Leetcode 23)

Another from the archives! (Can you tell I’m going through old notes?)

This one strikes me as an interesting exercise exploring that common hurdle of mixing up array-indexes and array-values. This is a nontrivial “array search” problem.

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        for i in range(1, len(arr)-1):
            if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
                return i

Apparently, however, we’re obliged to use binary search and find it in log(N) time. The idea there is you check your index “locally”, and move right or left depending on which way the mountain says is “up”.

Interview Questions

Hamming Distance (Leetcode 22)

This is another question and solution from the archive. I think this is a nice educational question, but not a great interview question. It’s an OK interview question. I tagged this “vocabulary” because Hamming distance, and the tools (that I think are) the right ones to solve this are less things you gain insight about over time, and instead things you learn. Some observations:

  1. The final punchline involves the XOR operator (^), which can be understood in a few ways. One way is seeing it as a symmetric-difference operator (or something like that), where the two integers are bitsets. So the result is a third bitset, that contains all those elements that were in exactly 1 of the two original bitsets. This sounds like what we want!
  2. The missing piece is being able to count the 1s in that resulting set. The vocab to use here is “popcount”, which is either a hardware instruction or — if you’d like — a simple enough loop.
class Solution {
public:
    int popcount(int x) {
        int count = 0;
        while (x) {
            if (x % 2) {
                count++;
            }
            x >>= 1;
        }
        return count;
    }
    int hammingDistance(int x, int y) {
        return popcount(x^y);
    }
};
Interview Questions, Linked List

Add Two Numbers (Leetcode 21)

This is from the archives, when I’d take more notes. Let me take those insights and preserve them here.

Despite the name, this question is really about linked lists. I’ll assume you’ve read the question and understood it. Now, a few observations:

  1. We get to iterate through the list in the “nice” way: we can start adding digits immediately.
  2. Built into the question is the problem of “carries” — we’re adding things, but each node can only hold the values 0-9, and so if there’s overflow we have to carry that.
  3. This is a linked-list-merge-style question (see featured post here), so we should be mindful of the “end” of each of our two linked lists and how we should handle them. A moment’s thought also suggests that the carry value can also play a role here!
  4. No negative numbers! The natural approach doesn’t suggest we’d introduce an erroneous leading zero or anything either. So it doesn’t seem there’s anything too tricky here.

Some insights:

  1. We can treat the carry value as a “virtual” node: this tightens up our iterations and puts everything into one loop.
  2. The approach I took was to create a new, third list. Another option (in practice; I assume the autograder would accept this too) would be to make this transformation destructive of one or both lists.
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* lastDigit = nullptr;
        ListNode* result = nullptr;
        bool carry = false;
        
        while (l1 || l2 || carry) {
            auto l1val = l1 ? l1->val : 0;
            auto l2val = l2 ? l2->val : 0;
            auto nextVal = l1val + l2val;
            
            if (carry) {
                nextVal++;
                carry = false;
            }
            
            if (nextVal > 9) {
                nextVal -= 10;
                carry = true;
                // assert(nextVal < 10 && nextVal >= 0)
            }
            
            if (!result) {
                result = new ListNode(nextVal);
                lastDigit = result;
            } else {
                lastDigit->next = new ListNode(nextVal);
                lastDigit = lastDigit->next;
            }
            
            if (l1) { l1 = l1->next; }
            if (l2) { l2 = l2->next; }
        }
        
        return result;
    }
};

I think this is a nice interview question.