Tag Archives: leetcode

Interview Questions

Climbing Stairs (Leetcode Dynamic Programming Study Plan)

This one I’ve taught many times. I have it in my archives, and in my old lectures notes. It’s the first “day 2” exercise for the study plan.

The punchline, of course, is that you end up with the fibonacci sequence again. I do appreciate that they’re articulating the question as “choosing” between two options… but with the head-fake that you’re calculating the number of choices, which of course is fixed. So we’re still not really choosing anything! I am sympathetic to the idea that this is how we’re getting closer to the concepts that underly “real” dynamic programming, but I’ve seen enough confusion on the matter where I can’t say that’s intentional.

Though, that said, I do recall when I taught a lesson on this, I think we were able to get some practice in on the idea of taking 2 previous solutions, and “building” off of those. I do think this is a much better first question than fibonacci. On the other hand, it took probably 60 minutes (half of my 2-hour session) to go over this… not exactly a warm-up question if the audience is learning dynamic programming (versus reviewing it).

Anyways, here’s the solution, with a slight off-by-one difference from the last time.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        if n == 2: return 2
        a = [1, 2]
        for i in range(2, n):
            a.append(a[i-1]+a[i-2])
        return a[-1]

I’m trying to collect all the study-plan questions under this tag. All dynamic programming questions go under this other tag.

Dynamic Programming, Interview Questions

Tribonacci (Leetcode Dynamic Programming Study Plan)

We meet again. Our second question in the study plan is the question on how to compute the n-th tribonacci (a pun off of “fibonacci”) number. Again I am not sure if we should really use this to teach dynamic programming! We’re just practicing the array tables.

In truth I don’t have much to say. This definitely is able to be done after solving the first question. I am a fan of these sort of “very basic extensions” to previous questions to help the student drive home the idea. I just went with the table approach this time.

I suppose it’s interesting that the question is articulated slightly differently in the codewars question. There is something a bit more general there; I prefer the specificity if I were using this question in a classroom or review setting. Maybe as a side-note, or a “quick” homework question, would be to further extend to these sort of signatures.

Anyways, here’s the solution:

class Solution:
    def tribonacci(self, n: int) -> int:
        a = [0, 1, 1]
        if n < 3: return a[n]
        for i in range(3, n+1):
            a.append(a[i-3]+a[i-2]+a[i-1])
        return a[-1]
Dynamic Programming, Interview Questions

Fibonacci (Leetcode Dynamic Programming Study Plan)

I’m changing up the format. I’m going to be going through a so-called “Leetcode Study Plan”, in particular the one on dynamic programming, and see how it compares to what I’d do for teaching this topic. I will “just” be solving the problems as with my other posts here, but I’ll hopefully be finding good notes to fulfill a larger write-up of how one might, or might not, use this to help their students.

Findings

To be honest, I don’t think this is off to a great start with Fibonacci. I suppose it’s nice to use arrays to compute intermediate values, but the recurrence here is meaningfully simpler than what comes up in “real” (or at least the hard) dynamic programming problems. In particular, we don’t choose from a collection of solved subproblems, we always know we’ll use the n-1 and n-2 solutions to create the n solution.

Speaking of solutions… I playfully made one without any arrays. Presumably if I had to use this to teach dynamic programming, I would use the “array based” method even though it’s not needed, as demonstrated:

class Solution:
    def fib(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        prevprev = 0
        prev = 1
        for i in range(2, n+1):
            tmp = prev + prevprev
            prevprev = prev
            prev = tmp
        return prev

So if I want to play along more, we have:

class Solution:
    def fib(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        a = [0, 1]
        for i in range(2, n+1):
            a.append(a[i-1]+a[i-2])
        return a[-1]

I will admit it looks prettier.

This and more dynamic programming problems will be listed here.

Interview Questions, Numerical

Self Dividing Numbers (Leetcode 35)

Another from the archive! I’ll confess some annoyance with this style of question (this is not the first or only example) that presents a contrived concept, in this case a “self dividing number“, and define it with the same language as more typical math concepts. I’ve seen it confuse or intimidate students with a nontraditional background as they think “here’s another thing I should have known, but I don’t because of my background”. I just wish these questions would make it clear when they’re making up a concept for the sake of the exercise.

In any case, this is a question that has another interesting-sort of loop. There is a style of using divide-by-10, modulo-by-10 to “iterate” through a number. See the standard atoi question (which I realize I don’t have yet? Something to add.) In binary form we have the implementation of popcount here, or the formatting requirement here.

def selfDividing(n):
    N = n
    while n > 0:
        d = n % 10
        if d == 0:
            return False
        if N % d != 0:
            return False
        n = n // 10
    return True
class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        res = [i for i in range(left, right+1) if selfDividing(i)]
        return list(res)

Discussion

I like that this has helper functions. For Python you get this cute filtering machinery, and I think that’s also a nice thing for this question. I think even just implementing the single helper function is a good warm-up and could lead into the atoi question, which a question I actually like. Maybe this is a good teaching warm-up before covering atoi. For lack of a better category I called this a numerical question, others of which can be found here.

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.

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, 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.