Category Archives: Interview Questions

Dynamic Programming, Interview Questions

Longest Increasing Subsequence (Leetcode Dynamic Programming Study Plan)

This is a truly classic problem. The opener in one of the big algorithms textbooks on dynamic programming, I’m glad it’s included in the dynamic programming study plan. I bet there is an even prettier way of writing this code, but here is the solution I have:

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) == 0: return 0
        T = [1] # the first thing is always a sequence
        for i in range(1, len(nums)):
            best = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    best = max(best, T[j]+1)
            T.append(best)
        return max(T)

Recurrence

T[i] is the length of the longest increasing subsequence that has to include the i’th element in nums. Compare to the recurrence in the previous question we discussed; there are similarities, but the big difference here is that our solution at i can build off of any previous solution that ends with a value smaller than ours, versus our solution having to be just contiguous with the previous solution.

So in more depth:

  1. T[i] is the length of the longest increasing subsequence of nums[:i+1] that include nums[i]. Taking the max of this array will find the solution.
  2. T[i] is computed via that append call, so we append the best value. We consider all values in T[:i] — recall T[j] is the length of the longest subsequence ending with nums[j]. If nums[j] < nums[i], we can “continue” that subsequence with nums[i], and so increase its length by 1.
  3. Through the “magic of recursion”, we are able to kick-start this process by defining T up to T[:1], i.e., T = [1].

The Dasgupta algorithm book explains this in a very graph-theoretic way, which I appreciate but is also kind of a lot.

See here for more dynamic programming problems and solution.

Dynamic Programming, Interview Questions

Maximum Subarray (Leetcode Dynamic Programming Study Plan)

1 Comment

How much of this question is carefuly application of arithmetic laws? Computing the maximum subarray seems like a simpler form of the classic longest increasing subsequence, but with fewer edges in the graph and a more “monotonic” (?) recurrence.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        T = [nums[0]]
        for i in range(1, len(nums)):
            T.append(max(nums[i], nums[i]+T[i-1]))
        return max(T)

Recurrence

The recurrence, such that it is, is that T[i] is the maximum sum of the array nums[:i+1] (to use slice syntax) that must use i. As in other questions, we’re embedding a decision in our recurrence. That would explain how the final max(T) works.

The big question is how does the for loop maintain the recurrence? How do we know that T was computed correctly? I don’t have a formal write-up, but to me the intuition follows from:

  1. If any prefix is >0, then it’s worth including that prefix.
  2. If any prefix is <= 0, then it’s not worth including it.

Distinct from the classic problem of longest-increasing-subsequence, we are only allowed to make limited choices, here: we can either attach ourselves to an existing sub-array, or start a new sub-array. If the existing sub-array has a positive influence (turn of phrase), then we might as well jump aboard. The choices are “simple”, in that sense.

This is included with all the other dynamic programming questions listed here.

Graphs, Interview Questions

Is Graph Bipartite? (Leetcode)

Another classic question, and another from the archives. This one’s nice enough where I took a stab at it in Python for readability.

class Solution(object):
    def isBipartite(self, graph):
        color = {}
        wl = []
        for x, ns in enumerate(graph):
            if x in color: continue
            wl = [x]
            color[x] = 1
            while wl:
                u = wl.pop()
                for w in graph[u]:
                    if w in color and color[w] == color[u]: return False
                    if w not in color:
                        color[w] = 1 - color[u]
                        wl.append(w)
        return True

Thoughts

  • The 1 - color[u] trick is handy. It’s a quick way to have 2 options, sort of like not‘ing a boolean variable. Something to teach new people.
  • I think there is the possibility that many of the same node is added to wl. I think I need another seen set to make sure we’re not iterating too often. Well, it passed.
  • The outermost loop is always a bit annoying: it’d be nice to promise that the graph is always connected. It’s good to know how to handle that situation, so I suppose that’s OK.
  • The term color here is because a bipartite graph is the same as a 2-colorable graph. Graph-coloring is a core combinatoric question. This solution overall follows from the observation that “if U is on the left, then all neighbors of U must be on the right, and vice-versa”. Instead of left/right, we use 2 colors (which in this case are… integers).
  • This is basically an extension of DFS. There is probably an opportunity for more cleverness.

Finally, a graph algorithm! More to come, I imagine. They’re all collected here.

Interview Questions, Linked List

Reverse a Linked List (Leetcode)

It’s time. It’s obvious I have a lot of linked questions, and here’s the classic. At least when I was an intern way-back-when, this was a cliche “overdone and inappropriate interview question”. It’s a nice exercise on thinking about linked lists, but unless your job requires it (my first job did!) I understand it feels a bit esoteric. Still, I like it.

Iterative Solution

class Solution(object):
    def reverseList(self, head):
        tail = None
        while head:
            n = head
            head = head.next
            n.next = tail
            tail = n
        return tail

Recursive Solution

class Solution(object):
    def reverseList(self, head):
        if head is None:
            return None
        if head.next is None:
            return head
        newTail = head
        head = head.next
        newTail.next = None
        res = self.reverseList(head)
        head.next = newTail
        return res

Discussion

I’m open to being wrong, but it seems that the iterative solution is nicer than the recursive one? Some of the pointer “faith”, in particular that head points to the tail of the reversed sub-list (penultimate line), is a bit much. With pointers that’d be a lot clearer I think, but Python’s references make it a bit fuzzier for me.

If anything, I think the reasoning about how the iterative solution works is very recursive-feeling. Or at least a nice application of loop invariants.

This question covers a lot! More linked list questions are here.

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.