Monthly Archives: October 2022

Greedy Algorithm, Interview Questions

Array Partition (Leetcode)

Another from the archives! This one is interesting because, at least to me, I found it was more an algorithmic/math question, rather than a straight application or exploration of a data structure.

By that same token I’m not sure I’d use this as an interview question, nor as a homework question. It’s building the confidence that we have the “right” pairing is the tricky part, I think. When I’ve seen students confront an algorithm that ultimately has a greedy solution, they often intuit the greedy algorithm as an approach, but won’t have the rigor to be able to be confident it’s the right one (or they don’t even know it might not be the right one, and an, e.g., dynamic programming solution is called-for). I don’t know how I feel about students “accidentally” getting the right answer: when Leetcode finally lights up all green for them, I’d imagine they view that as a certificate that they fully understand the answer. Maybe not!

Anyways, I fortunately recorded my original thoughts in a comment, which I’ve extracted here:

Approach and Solution

The algorithmic question here is somewhat interesting! We don’t just want to pair the largest half with the smallest half. Is the intuition that we want to pair the “closest” values? The max value cannot be chosen, as it’d be paired with something smaller. But the second-max value can be chosen if we pair it with the max. Do we always want to do that?

That’s suggesting a greedy algorithm. Find the “largest-still-pickable” value. Let’s say there’s some other, better pairing. Then we have at least two pairs (a, b) (c, d) where a < b, c < d, but also b > c. In that case we have: a, c, b, d (or a, c, d, b, or c, a, b, d, or c, a, d, b) in terms of sorting by order.

Presumably what I want to say is that swapping b, c here would increase the result. Let’s see: previously we’d have a + c, but by swapping we get either b or d (both of which are bigger than c), and either a or c.

WLOG can we say that a < c? Probably! I think that’s enough to go on here.

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        if (nums.size() == 0) { return 0; }
        std::sort(begin(nums), end(nums));
        assert(nums.size() % 2 == 0);
        int result = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            result += nums[i];
        }
        return result;
    }
};

I think this is the first “greedy algorithm” solution I’ve posted here. So it trailblazes a new category, here.

Interview Questions

Sort Array By Parity 2 (Leetcode)

We’ve been here before. Quite explicitly in fact, this question is obviously marked as a sequel.

This really drills into the idea of thinking about values versus indices. I think that’s something my students would get a lot out of. As mentioned in my comments, I feel like the term “sort” here is a bit deceptive. I would call this more like merging or partitioning, a helper function within a sort function. “Classify” by party? “Cubbyhole” by parity?

class Solution {
public:
    // Helpers inspired by commented out block in the main function.
    // This sort of "given the index, find the next valid index" pattern
    // is quite common. This is inclusive -- we can return start.
    // Yes I can have them share a function with lamdbads or whatever,
    // but let's not overcomplicate implementation.
    int nextEvenIndex(vector<int>& A, int start) {
        assert(start % 2 == 0);
        for (; start < A.size(); start += 2) {
            if (A[start] % 2) return start;
        }
        return -1;
    }
    int nextOddIndex(vector<int>& A, int start) {
        assert(start % 2);
        for (; start < A.size(); start += 2) {
            if (A[start] % 2 == 0) return start;
        }
        return -1;
    }
    vector<int> sortArrayByParityII(vector<int>& A) {
        // One of the quadratic sorts? This is almost more like merging or pivoting, than
        // sorting. The name feels deceptive :).
        
        // initialize i as the first even index to swap;
        int i = nextEvenIndex(A, 0);
        // j as the first odd index to swap;
        int j = nextOddIndex(A, 1);
        while (i != -1) {
            assert(j != -1);
            swap(A[i], A[j]);
            i = nextEvenIndex(A, i); // we should be able to get past i here, as it's now legal.
            j = nextOddIndex(A, j); // ditto
        }
        assert(i == -1 && j == -1); // we should both be done here.
        return A;
    }
};

Notes

  • You can definitely see my merge-friendly perspective influencing my approach.
  • I really like drilling into these loops where the index variables aren’t necessarily always incremented by a constant, as is here.
  • I like how this has the implicit sub-arrays inside the main array.
  • Avoiding a new allocation is a nice extended requirement, I think.

I think this is an obviously-contrived interview question, but it exercises nice things and the question (while a bit detailed) isn’t tricky. It’s very clear what a successful output should look like, or at least clear enough.

Interview Questions, Linked List

Split Linked List In Parts (Leetcode)

This question feels a bit contrived, but a way to explore a lot of challenges with linked lists. I have an answer to this in my archive.

So, full disclosure: most of my archive is actually in C++, rather than the more approachable Python or (occasionally, for my students) Javascript. I think I do have a few earlier solutions in C++, but this is the first “big” one, I guess? Previously I’ve also been translating my archive, but as my external obligations are increasing I have to drop some features. So this is in C++. Also from the archive: a lot of my notes were intentionally embedded in comments.

class Solution {
public:
    // it seems we need to know the length, to begin with.
    // and then we do an interesting partition sort of algorithm.
    // the value of the LL nodes play no part in this?
    // Sure...
    int len(ListNode* r) {
        int l = 0;
        while (r) {
            l++;
            r = r->next;
        }
        return l;
    }
    // OK, and then we divide things into K.
    // Ah that things differ by less than 1 is sort of an interesting constraint.
    // So if k > l, that's sort of easy: we know we need length 1.
    // if k < l < 2k, then we know we'll have a few length-2, and the rest length 1.
    // So this suggests some kind of modulo. k > 0, so that's safe.
    // l / k is the length of the shorter lists.
    // l % k is how many lists need one more.
    // This feels like an obsfucated remainder check. But actually it's OK. I kind of like
    // this partition problem.
    
    ListNode* peel(ListNode** root, int l) {
        // forgot a deref!
        if (!(*root)) return nullptr; // assert l == 1?
        ListNode* p = *root;
        ListNode* t = *root;
        // Here I'm being a bit risky. Not sure if there's a weird case
        // where if we improperly peel we'll null-deref. I think if everything
        // goes right we'll only ever be "off by one", which is effectively
        // captured by our basecase there.
        //
        // In other words, this is not a very robust peel! Relies on qualities
        // of the list guaranteed by the caller.
        for (int i = 0; i < l-1; ++i) {
            t = t->next;
        }
        *root = t->next;
        t->next = nullptr;
        return p;
    }
    
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        const int l = len(root);
        int shortLength = l / k;
        int listsWithExtras = l % k;
        // next up: helper function "peel";
        vector<ListNode*> result;
        ListNode* r = root;
        for (int i = 0; i < k; ++i) {
            int n = shortLength;
            if (i < listsWithExtras) {
                n++;
            }
            result.push_back(peel(&r, n));
        }
        return result;
    }
};

Notes

A few notable things:

  • The len helper, it seems to be required? It’s unfortunate that we can’t do this online.
  • I’m having second thoughts about my implementation of “peel”. I think I can avoid the pointer-to-pointer, though for C that’s not a huge deal. Maybe inlining the function would make that clearer.
  • You can see my careful-ish reasoning about how to calculate each peel length, I think that’s an interesting comment.

As always, all linked list things are collected here.

Interview Questions, Introductory

Jump Game (Leetcode Dynamic Programming Study Plan)

Well this one was embarrassing, I flubbed a lot of the base cases. I spent the most amount of time, however, trying really hard to see what I was missing: frankly, I don’t see why this is considered a harder question (“Medium”), and I don’t really see why this would be considered dynamic programming or be part of the study plan.

So yes, there is sort of a recurrence we’d want, as demonstrated in the solution…

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # We can (implicitly) make a DAG and now we're just finding
        # some kind of reachability/length
        # This seems a bit too easy... isn't reachability here really simple?
        # We can do normal reachability, but isn't this sort of an integer?
        # We keep the max of our current run, and what we currently see.
        v = nums[0]
        for w in nums[1:]:
            if v <= 0:
                return False
            v -= 1
            v = max(v, w)
        return True

You can see my comments revealing my confusion. There’s no real “there”, there, in my opinion. I’m gathering this and all its friends from the study plan in this tag.

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.