Monthly Archives: December 2022

Interview Questions, Strings

Unique Morse Code Words (Leetcode)

Another from the archives. I had too much fun with this python approach. A nice introductory string question.

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        mapping = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        def mapIndex(c):
            return ord(c) - ord('a')
        def mapWord(w):
            return ''.join(map(lambda c: mapping[mapIndex(c)], w))
        return len(set(list(map(mapWord, words))))

This is a fine introductory interview question. The exact motivation isn’t great, but “process this data and count unique ones” is fine. More strings — a popular request from my students — here.

Interview Questions, Strings

Longest Substring Without Repeating Characters (Leetcode)

Another from the archives. In my old notes I tried a few different approaches. Ultimately this one feels a little “brute-force-y”, here is what I got:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int l = std::max(res, 1); l + i <= s.size(); l++) {
                std::bitset<256> seen;
                bool bad = false;
                for (int j = i; j < i + l; j++) {
                    if (seen.test(s[j])) {
                        bad = true;
                        break;
                    }
                    seen.set(s[j]);
                }
                if (!bad) {
                    res = std::max(res, l);
                } else {
                    // i i our starting point, a longer l won't help here.
                    break;
                }
            }
        }
        return res;
    }
};

Thoughts

  1. The “length” iteration (how i, l, j indexes interact) is pretty interesting. Comes up rarely, but in thinking about many collections of substrings.
  2. The final “break” (with the comment above it) is necessary.
  3. I wanted to port this to Python—my old archives are in C++. But it lacks a bitset class, and its range loops aren’t amenable to the length-based iteration (or at least, I don’t know how to adapt them).

I doubt my solution is the right one. What is the official Leetcode solution? Oh I like it! Does this make the cut as an interview question? I don’t know, I am skeptical. More string questions here.

Binary Search Tree, Interview Questions

Minimum Distance Between BST Nodes (Leetcode)

This is a fun-enough question, I guess. I feel like I’ve seen a few questions with BSTs where the answer involves the idea that in-order traversal presents their content as a sorted list. Or should… Oh yeah, this would much-improve my answer for this older question.

Interlude: Yield Statements

I guess sometimes they’re called coroutines? Fun excuse to use those in Python. For our purposes they’re a “better” (?) way of collapsing the BST we have into a sorted list. The magic of that isn’t the coroutines of course, it’s that in-order traversal of a BST presents the contents as a sorted list. The yield statement just makes it nice, we don’t have to allocate a whole intermediate list.

Solution

class Solution(object):
    def inOrderYield(self, root):
        if root is None:
            return
        for x in self.inOrderYield(root.left):
            yield x
        yield root.val
        for y in self.inOrderYield(root.right):
            yield y
    def minDiffInBST(self, root):
        minDiff = None
        prev = None
        for v in self.inOrderYield(root):
            if prev is None:
                prev = v
                continue
            if minDiff is None:
                minDiff = v - prev
                prev = v
                continue
            minDiff = min(minDiff, v - prev)
            prev = v
        return minDiff

I bet there’s a better way of doing the final loop in our main function.

More BST goodness here.

Graphs, Interview Questions

Network Delay Time (Leetcode)

This is a classic algorithm, and from the archive! It is just Dijkstra’s algorithm, and in fact this sort of formulation is exactly how my undergrad algorithms professor tried to have us develop the intuition of how it worked. I appreciate that this formulation at least suggests something of an approachable motivation, measuring network latency and similar.

class Solution(object):
    def networkDelayTime(self, times, n, k):
        # Cache neighbors and their weights
        neighbors = {u : [] for u, _, _ in times}
        for u, v, w in times:
            neighbors[u].append((v, w))
            
        # Djikstra's
        worklist = [k]
        cost = {k: 0} # cost to reach k
        while worklist:
            u = worklist.pop()
            c = cost[u]
            if u not in neighbors:
                continue # its a sink
            for v, w in neighbors[u]:
                if v not in cost or cost[v] > w + c:
                    cost[v] = w + c
                    worklist.append(v)
        
        # Return requested result
        if len(cost) != n:
            return -1
        return max(cost.values())

Discussion

This was originally “easy” on Leetcode, according to my notes. I think with some thought this can be an approachable, or independently derivable algorithm. (A different professor I had pointed to Dijkstra as an advantage of being early on in a new field: if you are, you can name all the “obvious” results after yourself!) I wouldn’t say this is an obvious algorithm, but the idea that you “update your neighbors” when you receive new information is something that is worth getting a measurement on, interview-ish speaking.

Glad to finally get another graph algorithm on the books. The others are here.

Binary Tree, Interview Questions, Recursion

Longest Univalue Path (Leetcode)

This leetcode question is interesting. It is from my archives. Originally, I misunderstood and thought you could only look for paths going “down”, but obviously as illustrated the question also admits “sideways” paths, see the second example.

Curiously, I was able to adapt my solution for the simpler interpretation and extend it to work for the more complicated interpretation too! Here is the code:

class Solution(object):
    def bottomUpBuilder(self, root):
        if root is None: return
        
        self.bottomUpBuilder(root.left)
        self.bottomUpBuilder(root.right)
        
        # can we continue a path from either of our children?
        self.longestPath[root] = 0
        if root.left and root.left.val == root.val:
            lval = self.longestPath[root.left]+1
            self.longestPath[root] = lval
        if root.right and root.right.val == root.val:
            rval = self.longestPath[root.right]+1
            self.longestPath[root] = max(self.longestPath[root], rval)
            
        # Can we join a path between our two children?
        # Note, crucially, that we're using "longestPath" for our child values;
        # we can't use asJoin because that would suggest a degree-3 node in our "path".
        self.asJoin[root] = 0
        if root.left and root.right and root.left.val == root.val and root.right.val == root.val:
            self.asJoin[root] = self.longestPath[root.left] + self.longestPath[root.right] + 2
    def longestUnivaluePath(self, root):
        self.longestPath = {}
        self.asJoin = {}
        self.bottomUpBuilder(root)
        m = 0
        for r in self.asJoin:
            m = max(m, self.asJoin[r])
        for r in self.longestPath:
            m = max(m, self.longestPath[r])
        return m

Discussion

You can see that there are basically 2 maps built, not just one. The asJoin map handles the case I forgot about.

So I can see this question as a nice one-two sort of question: first solve my simpler case, and then “can you extend that to the sideways case”? Well, the key insight that allows us to extend our code is hinted at in the comments: the asJoin map is defined in terms of longestPath, we don’t want to define it recursively.

This has a nice bottom-up iteration, and some neat invariants and applications. This question, on Leetcode, also has a certified solution. What is that solution? Let’s see.

Leetcode Solution Discussion

OK, it’s a more elegant recursive formulation (maybe?), and doesn’t admit my “extension” idea. Understanding why it’s linear-time is an interesting exercise.

More trees here, more recursion here.

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.