All posts by Aaron

Binary Tree, Interview Questions

Zigzag Order Traversal (Leetcode)

Long ago my students wanted binary tree problems, so I did a lot. I don’t think this one made the cut. This is from the archives, and according to my notes it took me a while to figure out the right iteration “pattern”. I think this stateful kind of iteration (the state is to help track the zigzag) is useful, though obviously here it’s contrived, so I think this is a good practice problem.

Approach

The key observation, and maybe this is too obvious, is that we can do BFS and keep track of the parity of what layer we’re in. If we’re in a left-to-right layer, we append our next children (who comprise the following layer) right-to-left, and vice-versa.

Realizing this in code, at least for me, was nontrivial. Here it is!

class Solution(object):
    def zigzagLevelOrder(self, root):
        if root is None:
            return []
        res = []
        currLevel = [root]
        reverse = False
        while currLevel:
            layer = []
            nextLevel = []
            # Drain the current level
            while currLevel:
                n = currLevel.pop()
                layer.append(n.val)
                if not reverse:
                    if n.left is not None:
                        nextLevel.append(n.left)
                    if n.right is not None:
                        nextLevel.append(n.right)
                else:
                    if n.right is not None:
                        nextLevel.append(n.right)
                    if n.left is not None:
                        nextLevel.append(n.left)
            res.append(layer[:])
            layer = []
            currLevel = nextLevel
            reverse = not reverse
        return res

Observations

Some thoughts:

  1. As we’re updating our state, this has some nice exercises with variable lifetime stuff. You can see I append a copy of layer, rather than a reference to it. I am not 100% clear on how references and scoping work in Python, so I went conservative. Turning that around, this exercise helped “poke at” my understanding of references and scoping.
  2. There’s something interesting going on about how the zig-zag-edness comes about implicitly from the tree structure and our iteration order.

Anyways. A weird tree question! More tree questions here.

Interview Questions, Introductory

Two Sum (Leetcode)

This is the classic, literally Leetcode question 1. It’s an OK question. It admits a “naive” solution of try-every-pair, and also enables some deeper thought. I don’t have a good read on whether that deeper thought should be considered expected in an interview setting.

Naive Solution

The naive solution is try-every-pair. This is an accessible example of a concept I like, where we have the explicit object (in our case, an array), but we’re really exploring an implicit object (in our case, a sequence of pairs of elements, those elements drawn from an array). We can be careful about precisely which pairs we’re exploring.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                if nums[i]+nums[j] == target:
                    return [i, j]

Not-Better Solution

The interesting thing is how to derive the better solution. Let’s formulate it in terms of the condition we “care” about, nums[i]+nums[j] == target. With arithmetic, we can say that’s the same condition as: nums[i] == target – nums[j], (we subtracted nums[j] from each side).

So we can derive a new sequence, diffNums, where we assign diffNums[j] = target – nums[j]. Now what would our loop look like?

class Solution(object):
    def twoSum(self, nums, target):
        diffNums = [target-nums[i] for i in range(len(nums))]
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i == j:
                    continue
                if nums[i] == diffNums[j]:
                    return [i, j]

This is not faster by any measure: asymptotically it’s still O(n^2), and now we have an extra intermediate array diffNums to instantiate. Sure enough, it’s too slow for Leetcode, haha.

However, a careful look at our condition now is enticing: we’re “just” seeing if the collection nums has any element in common with the collection diffNums. That’s set-membership! So let’s recast things:

Faster Solution

We ultimately need to return the indices. So let’s have diffNums be a mapping from target-nums[i] : i.

class Solution(object):
    def twoSum(self, nums, target):
        diffNums = {target-nums[i] : i for i in range(len(nums))}
        for i in range(len(nums)):
            v = nums[i]
            if v in diffNums and i != diffNums[v]:
                return [i, diffNums[v]]

A lot has changed! Crucially, we have the if v in diffNums condition: that captures the whole inner for-loop! Even better, because diffNums is a map, we can expect that lookup to be roughly constant time, instead of linear. This brings our algorithm down to roughly-linear time. (Note that diffNums[v] is basically j in this loop.)

Conclusion

This problem grew on me, in terms of introducing some intermediate programming thoughts. I think if we have to use this an interview question, assuming the candidate is stuck on getting the faster solution, I’d prompt them to that not-better solution and see where they take it. More introductory questions here.

Interview Questions, Recursion

Permutation Sequence (Leetcode)

I’ve decided to call this permutation sequence question a “classic problem” because it is I think a very reasonable combinatorics/counting question. Also, the problem is marked as a “Leetcode Hard”, so I figure I should get one of those on this blog before too long.

Discussion and Approach to Solution

As a change of pace, I tried to see what it would be like to make a “literate code” approach. This, uh, didn’t work. I ended up with a block comment above the code, so I’ve extracted that out here:

for [1, 2, 3, 4], we have 3! sequences that begin with 1, 3! that begin with 2, etc… so we end up with 4 * 3! = 4!, that checks out. So in general, if we have a size-n set, there are n! distinct values, and the first (n-1)! begin with 1, then the next (n-1)! begin with 2, etc. This reasoning applies recursively. So we want to find the highest “m” in [1, n] such that (m-1)(n-1)! < k (or equiv, the smallest m such that m(n-1)! >= k. Maybe that’s a better formulation). Note the “punning” between m as an element of the remaining set, and n as the count of elements left in the set. In turn, m is the index of the m’th largest element, not literally the value m.

So that’s a terse comment. To take a step back:

If we consider the n! possible permutations of [1..n], in lexicographical order, the first (n-1)! begin with 1, the next (n-1)! begin with 2, and so on. This leads to n sub-sequences of length (n-1)!, and we can be confident that the concatenation of these sequences gives us the original sequence back, as there are n*(n-1)!=n! elements altogether.

This suggests an analogy to digits (if we consider the sequence [0..999], the first 100 “begin” with 0, the next 100 begin with 1, and so for 10 times, leading to 100*10 = 1000 elements). We can repeat this recursively, for the sequence [0..99] there are again 10 sub-sequences. Unspooling the recursive reasoning, it means we can “index” into that sequence by looking at successively-lower-magnitude digits. This feels like a no-op because it’s sort of what we already do with normal indexing.

With this factorial-esque indexing, there are n biggest-“digit” sequences, then n-1 next-digit-sequences, and so on. The formulation in the code below is not explicitly recursive, but instead currentIndex is basically, well, the index of the implicit sequence of [result + start]. And we select certain elements from start to “increment” our currentIndex.

Code

class Solution(object):
    def getPermutation(self, n, k):
        # for [1, 2, 3, 4], we have 3! sequences that begin with 1, 3! that begin with 2, etc...
        # so we end up with 4 * 3! = 4!, that checks out.
        # So in general, if we have a size-n set, there are n! distinct values,
        # and the first (n-1)! begin with 1, then the next (n-1)! begin with 2, etc.
        # This reasoning applies recursively.
        # So we want to find the highest "m" in [1, n] such that (m-1)(n-1)! < k
        # (or equiv, the smallest m such that m(n-1)! >= k. Maybe that's a better formulation).
        # Note the "punning" between m as an element of the remaining set, and n as the *count*
        # of elements left in the set. In turn, m is the *index* of the m'th largest element, not
        # literally the value m.
        def fact(n):
            res = 1
            for i in range(1, n):
                res *= i
            return res
        result = []
        start = list([i for i in range(1, n+1)])
        currentIndex = 1
        while currentIndex != k:
            # find the smallest m. Careful reasoning about indexing
            # to avoid off-by-one errors (1-indexed the range of permutations,
            # but m itself should be zero-indexed as it goes into `start`)
            incrementN = fact(len(start))
            m = -1
            for m in range(len(start)):
                # My one bug: I left out the "currentIndex + " part, which lead
                # to an interesting behavior: n=5, k=1 and n=5, k=120 both passed without this!
                if currentIndex + (m*incrementN) > k:
                    m -= 1
                    break
            # remove m from start, we've selected it
            assert(m >= 0 and m < len(start))
            result.append(start[m])
            start.pop(m)
            currentIndex += m*incrementN
        
        # At this point we know we should emit the "0th" remaining permutation.
        # Some subtlety in making sure we're appending to result in the same "direction"
        # as done in the while loop
        result += start
        return ''.join(map(str, result))

Discussion as an interview question

This is a hard-core question about recursive reasoning. I’m not sure about its appropriateness. As notes for my own attempt, while I didn’t recall my approach I did actually implement this code a long, long time ago, and in a previous form of this blog talked about the general approach. You can see my older implementation (when I was literally studying enumerations) is much better. So in revisiting this I was able to recall the broad strokes of a way that would work, and then take it from there.

Discussion general

This is a really neat computer science problem! I have a soft spot for enumeration problems, and have enjoyed jumping into Knuth 4A a few times particularly for Gray codes. I have dreams of using those to help provide exhaustive test suites for other combinatoric algorithms, but I just don’t have the time. There is a lot of depth to this topic I’m not familiar with; reconciling my “analogy” with the more in-depth treatment of Factorial Number Systems is something I should do one day.

More recursive problems (which I guess will include enumeration problems?) here.

Arrays, Interview Questions

Max Consecutive Ones (Leetcode)

I think this is an interesting loop, and a nice intro question to people still getting their feet wet with programming and algorithmic thinking. It’s a sort of scan problem.

Solution

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        m = 0
        c = 0
        for n in nums:
            if n == 1:
                c += 1
                m = max(m, c)
            else:
                c = 0
        return m

The sort of “invariants” you have to maintain, or the general idea of the state-of-our-scanner (slightly) evolving as we see different values, is a good muscle to build.

More interesting loops here.

Bit Manipulation, Interview Questions

Single Number (Leetcode)

I don’t like this one. Let’s discuss two solutions:

Natural Solution

Here’s a natural-enough solution in Python. Observe how we use a “counter” object; that’s basically a hashmap, which is a fine-enough solution as well in my opinion. This is, in my opinion, the “right” solution.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counter = collections.Counter()
        for n in nums:
            counter[n] += 1
        for n in counter:
            if counter[n] == 1: return n
        # return None, assert.

This is “inefficient”, in the sense that we’re using O(n) space and a bit more than O(n) time (I’m a pedant about hashmap time). However, it solves the general problem of “what’s the unique element in this sequence”. That problem isn’t super-common, but it’s not way-out-there.

Desired Solution

But! They want constant space and linear time. This is a nice enough “think outside the box” thing, but it’s so obviously fishing for a trick after-the-fact. It’s a tail-wagging-the-dog sort of situation, where someone obviously observed an interesting trick, and then constructed a question that can only be reasonably answered with that trick. What’s the trick? It involves XOR identities.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda a, b: a ^ b, nums)

Ooooh. The observation is that for XOR operation (the ^ operator):

  • a^a = 0
  • a^0 = a
  • And everything commutes

So a sequence like a^a^b^b^c = c, because we end up with 0^0^c=c. That’s neat, but extremely dependent on the idea that the sequence contains an even number of every element, except one, which exists an odd number of times. I suppose it’s neat to keep the “flexibility” of thinking of array contents as values (as we do in the typical solution) and bit-sequences, but it’s really a fishing sort of question.

I’d do this for fun (I did do this for fun), but I’d suggest avoiding it except to show a neat consequence of XOR identities in a classroom. More bit manipulation questions here.

Arrays, Interview Questions

Intersection of Two Arrays (Leetcode)

Another from the archives. This is actually something I like as an interview question, so I suppose maybe that means I should change my interview question. I suppose candidates need to know what a set is, but given the domains I work in I think that’s a fair requirement. This question is to take two arrays of integers, and return their set-intersection.

I think a very reasonable approach is to immediately sort the input. After that, as we build the result vector, we can think about the invariants that are maintained: the result vector is in sorted order, and so the “unique-ification” we need to do can follow naturally from that.

Nevermind also the invariants that guide the overall merge-sort-esque loop iterations. We can reason about how we make forward progress.

Code Solution

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(begin(nums1), end(nums1));
        sort(begin(nums2), end(nums2));
        vector<int> result;
        
        int i = 0;
        int j = 0;
        
        while (i < nums1.size() && j < nums2.size()) {
            if (nums1[i] == nums2[j]) {
                if (result.size() == 0) result.push_back(nums1[i]);
                else if (*(result.rbegin()) != nums1[i]) result.push_back(nums1[i]);
                i++;
                j++;
            }
            else if (nums1[i] < nums2[j]) i++;
            else j++;
        }
        
        return result;
    }
};

Extensions

I think some reasonable extensions are: what if the vector-of-ints is sort of a set datatype with certain invariants (e.g., that the contents are always sorted). This suggests the results should also be sorted, but we sort of get that “for free” with the natural approach. I like discussing possible trade-offs of performance depending on the input size.

This is, in my opinion, a nice exercise on loops and arrays. More can be found here.

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.