Category Archives: Interview Questions

Dynamic Programming, Interview Questions

House Robber (Leetcode Dynamic Programming Study Plan)

This was a nice dynamic programming exercise, and part of the Leetcode-defined study guide. This is a fun alternative to the Dasgupta et. al. intro question of longest increasing subsequence. It feels like the same flavor. Perhaps a more peaceful formulation would be making it like choosing a sequence of moves in some game show, to win money.

The Core Approach

This is the first question in the sequence that really motivates, to my mind, a “real” dynamic programming formulation. In this case, we want a table T such that T[i] is the “best” thing for some category. To me the most interesting complication is how to express that choice implicitly in T. The counterintuitive trick I’ve learned is to have T involve committing to that choice.

Just as the Dasgupta LIS example has T[i] be the longest increasing subsequence ending at that point (so it’s committed to using the ith element as part of the sequence), we should have T[i] in this question be the most money you get if the last house you rob is house i.

On a more mechanical level, there are two harsh jumps in my mind:

  1. We’re going from a linear algorithm to a quadratic algorithm. Not a problem, but as people seem to approach dynamic programming with some fearful awe, it may be worth to clear the way and say multiple scans over the table is OK.
  2. The solution to the problem is not (necessarily) the last cell of the table. That is again fine, but again different from the previous questions.

The solution

No further ado, complete with unaltered comments to myself.

class Solution:
    def rob(self, nums: List[int]) -> int:
        T = []
        # T[i] = most money when comitting to robbing house at i
        # Observation: we encode the decision into our definition
        # of T, that's how we avoid having to think about more than
        # 1 house at a time (we instead look at the previous... 3 options?)
        # Interesting inputs: [10, 1, 1, 10], you don't want to rob either "1" house
        for i, v in enumerate(nums):
            options = T[:i-1] + [0]
            T.append(max(options)+nums[i])
        return max(T)
Dynamic Programming, Interview Questions

Min Cost Climbing Stairs (Leetcode Dynamic Programming Study Guide)

And we’re back with our study plan. The next question follows from the previous pretty naturally, now we want to find a particular path, one that is optimal in some sense. In this case, it’s the min-cost path.

So I’m coming around to the approach presented in this study plan. There is a design behind it; my concern is that the design is a bit opaque to the new student. I can see it as someone familiar with the topic and knowing what ideas to build up to. In this question:

  1. We make the jump (finally) to an optimization problem. We want to compute the -est if something (in the case, the small-est).
  2. The syntax of the solution will present a lot of the common patterns to look for: you have a recurrence that basically feeds off of previous elements from the table you’re building, as well as a component of the input.

Wishlist

There are some rough edges to this question. Again, I’m coming around to this approach, but if I could ask for some things:

  1. The question itself is a bit ambiguous. The effect is that the best answer is either ending on the last, or the second-to-last step. I wonder how the question would look if you always had a cost-0 step at the end. You’d end up in the same place, and I think it’d help remove ambiguity about where the path actually has to end.
  2. Similar thing with the beginning, though to a lesser extent.
  3. My approach, and maybe due to my own limitation, ended up with slightly different offsets from i in my new table (minCost) and the input table (cost). If/when I teach this, I’d want to make sure those indices line up in the material I present.

With that final caveat, here’s my quick solution.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # trusting the invariants than len(cost) > 1
        minCost = [0, cost[0], cost[1]]
        # mincost[i-1] is the min-cost of landing on that step
        for i in range(2, len(cost)):
            minCost.append(min(minCost[-1], minCost[-2])+cost[i])
        # we essentially can either end on the last, or second-to-last, step
        return min(minCost[-1], minCost[-2])

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

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

Evaluate Reverse Polish Notation (Leetcode 37)

This was a homework assignment in my intro-to-data-structures-and-algorithms course. Evaluating an expression in this way is a good exercise. While it’s not literally recursion, I’ve tagged it as such because it uses those ideas. (And there doesn’t seem to be a better category.) These sort of questions, I think, are to Leetcode’s merit: a student (assuming they don’t cheat, of course) can really use this to test their understanding.

Having already known the answer, and not yet subjecting any of my students to this, it’s hard for me to anticipate what the tricky parts of this question are. I assume the key insight is that you can push (what Python calls append) the intermediate values back on the stack and it “just works”. Maybe that follows from reading carefully what RPN is?

The motivation for this problem is that it’s an easy calculator to make, and compilers.

class Solution:
    def isOp(self, s):
        return s in ['+', '-', '*', '/']
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for t in tokens:
            if self.isOp(t):
                r = stack.pop()
                l = stack.pop()
                if t == '+': x = l + r
                elif t == '-': x = l - r
                elif t == '*': x = l * r
                elif t == '/': x = int(l / r)
                stack.append(x)
            else:
                stack.append(int(t))
        return stack[0]

Postscript

Is this a good interview question? I don’t know. At a big meeting about interview questions, a work colleague said that they always ask this one as their standard interview question. So that’s one vote! I don’t think there’s trickiness per-se, and I think the parsing and case-handling here is an interesting and good exercise.

I am in parallel trying to build a collection of “classic” problems for students, under this tag.

Binary Search Tree, Recursion

Validate Binary Search Tree (Leetcode 36)

1 Comment

This “medium” problem does present a nice way where an initial solution (i.e., mine) has lots of room for improvement. Assuming the student knows what a binary search tree is and is fairly comfortable with them, and recursion, this is an excellent homework problem. In a sense, it’s taking the invariants of a binary search tree, and taking them a step further and applying them to solve a new problem, validation. While this is a bit contrived, I think validation for a datastructure has good-enough motivation.

The solution code is a bit bigger than typical, and I bet it can be made a lot smaller and more efficient. I just was confident this would work, so I went that way. An opportunity, later, to discuss how to improve code after-the-fact?

Solution Ideas

  1. All nodes to the left of our “root” (and remember we’re going to look at every node as its own root) should be smaller than us. So we’d like to know what the largest value to our left is—if we’re bigger than that, then we’re OK. Similarly, we want to know the smallest value to our right [Note: terrifyingly, as I was writing this, the “we want to know the smallest value to…” auto-complete filled in “to our right”! I suppose it saw the opposites of larger and smallest, and mapped that to right/left? Spooky!].
  2. So I imagined as if I knew the min-and-max values for each node. If we had that attached to each node, we can simply query our immediate children and see what they each have as their min/max values. If our value is smaller than the max of our left, or larger than the min of our right, we are not a valid BST.
  3. Additionally, if we have the min/max values of our children, we can easily compute the min/max values of ourselves.

Finding the min or max value of a tree is an easy-enough recursive exercise. Doing both at the same time is a nice sequel. Doing it for all node is itself an interesting problem: I haven’t done out the arithmetic, but the temptation to do it “purely recursively” would lead to a very expensive algorithm. I don’t know if it’s quadratic per-se, but it sounds like “for each node, walk the tree”. So you want a very deliberate bottom-up approach.

Conclusion

My solution is a bit of a hybrid where I set the stage for a two-pass approach, computing global maps for the nodes, but then realized I could determine a BST violation while computing the maps. I bet we can get rid of the maps and turn this into a more typical recursive formulation. Later!

class Solution:
    def solution(self, root):
        if root is None:
            self.minMap[root] = None
            self.maxMap[root] = None
            return True
        
        l = self.solution(root.left)
        if not l: return False # might as well stop
        
        r = self.solution(root.right)
        if not r: return False
        
        lm = self.maxMap[root.left]
        if lm is not None and lm >= root.val:
            return False
        
        rm = self.minMap[root.right]
        if rm is not None and rm <= root.val:
            return False
        
        rMax = self.maxMap[root.right]
        if rMax is None:
            rMax = root.val
        lMin = self.minMap[root.left]
        if lMin is None:
            lMin = root.val
        
        self.maxMap[root] = rMax
        self.minMap[root] = lMin
        
        return True
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # Observation: if we check each node, we'll be doing something that feels
        # a little bit too "quadratic" (for each node, validate the rest of the tree)
        # What we can do is build a map of nodes to min/max values under that tree,
        # and then do another pass (in parallel?) to do the final validation.
        # So, in other words:
        
        # Silly initializatio
        self.minMap = {}
        self.maxMap = {}
        return self.solution(root)

More BST questions can be found here.

Interview Questions, Matrix

Tic-Tac-Toe Checker (Code Wars 27)

On a personal note, this question is actually one of the first interview questions I had to work through for a college internship at a giant tech company. It could have gone better; I got the internship anyways. So let’s see if I can redeem myself. I’m going to try to solve it “live”.

Approach

I know (from many years ago, and hopefully also many more years of experience) that I want to do nice-and-simple helper functions. So things like “columnWins”, “rowWins”, etc. Well, I know that Python is friendly enough where I just made a generic helper that would say which, if any, player won any length-3 sequence of values. Then I simply iterated over all relevant length-3 sequences. It’s not a small amount of code.

I had a few typos I fixed up. There are inefficiencies and redundancies, nevermind the allocations, but it’s straightforward and readable enough. The other python solutions, those that won as “best practices”, are a bit more explicit about it being a 3×3 matrix.

def seq_wins(seq):
    assert(len(seq) == 3)
    V = seq[0]
    if V == 0: return 0
    for v in seq[1:]:
        if v != V:
            return 0
    return V
def is_solved(board):
    # Check rows:
    for r in board:
        w = seq_wins(r)
        if w != 0:
            return w
    # Check columns
    for c in range(3):
        col = []
        for r in board:
            col.append(r[c])
        w = seq_wins(col)
        if w != 0:
            return w
    # Check diagonals
    d1 = []
    d2 = []
    for i in range(3):
        d1.append(board[i][i])
        d2.append(board[i][2-i])
    w = seq_wins(d1)
    if w != 0:
        return w
    w = seq_wins(d2)
    if w != 0:
        return w

    for r in board:
        for v in r:
            if v == 0:
                return -1
    return 0

Take-Aways

I like this question as an interview question, actually. The reasoning-by-cases is nice and comes up in the real world. Sure, 2D arrays aren’t very common in my experience, but as a proxy for indexing into a nontrivial data structure, it’s a good one. I think a natural approach (obviously, given my own approach) is to make a helper function, either explicitly or at least implicitly, and seeing how a candidate thinks to draw the line of where/how to make a helper function can be a good insight into their views.

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.