All posts by Aaron

Interview Questions, Strings

To Lower Case (Leetcode)

From the archives. A challenge with this is (I think?) Javascript overloads their tolower equivalent to take either strings or characters. This is more testing familiarity with language features (do you do this, or do you use ASCII tables — which I guess isn’t unicode-friendly — or something else?) than anything else. Not a terrible question, just a correct answer doesn’t say much about the candidate/student.

class Solution {
public:
    string toLowerCase(string str) {
        string v;
        for (auto&& c : str) {
            v.push_back(std::tolower(c));
        }
        return v;
        // Maybe this is an excuse for some sanity checking, as well as destroying the input parameter,
        // etc.
    }
};

Nevertheless, it’s a string question, so it lives here.

Interview Questions, Strings

Jewels and Stones (Leetcode)

The hardest part of this question for me was the phrasing. However, I do sort of like this question: hopefully the student will realize they need to repeatedly check the string (set) of jewels, as they iterate over their stones. I don’t know how I feel about the fact that we’re using strings as sets, basically. It does happen in the real world.

Again, from the archives. This is me having too much fun with C++-isms. You can see my inline notes about other approaches.

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        // let's do this very simply, no helper objects.
        int jewelCount = 0;
        for (auto&& stone : S) {
            if (std::find(std::begin(J), std::end(J), stone) != std::end(J))
            {
                jewelCount++;
            }
        }
        // We can do lots of things, really. We should cache J into a set, perhaps, and
        // then can just do a fancier std::algorithms (for_each) sort of thing, if that
        // strikes our fancy. filter etc.
        return jewelCount;
    }
};

We may even be able to collapse the outer for-loop into a count_if call or something… but that’s probably too clever. Who knows.

I guess this is a strings question? Even though it’s really treating strings as a set.

Bit Manipulation, Dynamic Programming, Interview Questions

Counting Bits (Leetcode)

Another from the archives! I had a lot of fun with this one. Would others? I don’t know! We can use a sort-of dynamic programming approach (maybe this is a good replacement for that frustrating “Fib” standard warmup?) to avoid calling popcount over and over again. Not sure what’s actually faster on hardware, but I like the principle here.

This is a good algorithmic-thinking question, I think. Requires some fluency with bit manipulation, though.

class Solution {
public:
    vector<int> countBits(int num) {
        if (num == 0) { return {0}; }
        if (num == 1) { return {0, 1}; }
        if (num == 2) { return {0, 1, 1}; }
        vector<int> res(num+1);
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i <= num; ++i) {
            const int lastBit = i % 2;
            res[i] = res[i/2] + lastBit;
        }
        return res;
    }
};

Notes

Additional implementation details? I don’t know. I found it reassuring that the length of the output is required to be num, because there’s always that potential psuedopolynomial trap. Fixing the output size (versus, say, we’d have to return the total numbers of 1s or something) helps make it unambiguous that we’d at least be able to iterate through all inputs.

Other bit-manipulating questions are collected here. Other dynamic-programming questions are collected here.

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.