Tag Archives: classic problem

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.

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.

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.

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.

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.

Binary Tree, Interview Questions

Tree Equality (Leetcode 15)

1 Comment

Now this I’m certain is a classic. I like how it’s not, well, a single tree! A neat second-lecture problem on binary trees, I’d think.

class Solution(object):
    def isSameTree(self, p, q):
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False
        if not self.isSameTree(p.left, q.left):
            return False
        if not self.isSameTree(p.right, q.right):
            return False
        return True

This “design” or style of programming is curious. Would the students suspect that “I thought about enough cases, and figured if there’s no other reason, we can return true”? I guess reasoning by cases never felt very persuasive to me when I was starting out, it’s hard to convey that we really have covered all the cases. I don’t know what threshold I crossed to feel more confident about reasoning-by-cases. Now that I do feel comfortable, I think this can be a valuable real-world tool, too.

Other binary tree problems with solutions can be found here.

Postscript: About 9 months after posting this, I was adding more questions, and I had misread my notes and thought this wasn’t a question I solved yet. My new approach is almost character-for-character the exact as listed above! Surprising.

Binary Tree, Interview Questions

Depth of Binary Tree (Leetcode 6)

Leave a comment

I’m pretty sure I got this as a test question in “CS 102”, my data structures and algorithms course. The depth (or the height) of a tree. I really like phrasing this as the height of the tree, to be honest. My solution, as you see below, involves “adding 1” to the children’s depth. Especially if this is used as a teaching exercise, focusing on height helps avoid unneeded difficulties.

When we go over it in review sessions I’ve found students are often confused by the definition of the problem itself. It invites off-by-one errors, and also depth-versus-height. Especially when we say “now add one to the depth” — well, why are we increasing the depth as we go up the tree? It may be clear after-the-fact, but that can even detract from the satisfaction of solving it. If you can get them past that (or cleverly avoid them having to consider that aspect at all) it’s a great exercise.

Oh, and in this particular problem description, the math-y definition invites a certain implementation (ah, trace paths through the tree, very explicitly!). I think that’s a valuable thing to consider, the idea that a mechanical definition may very well different substantively from the “real” implementation, but I would rather introduce that idea outside the context of an interview or academic question. More like lecture material.

class Solution(object):
    def maxDepth(self, root):
        if root is None:
            return 0
        leftDepth = self.maxDepth(root.left)
        rightDepth = self.maxDepth(root.right)
        maxChild = max(leftDepth, rightDepth)
        return maxChild + 1

More binary tree material can be found here.

Interview Questions, Linked List

Merge Sorted Lists (Leetcode 2)

This one’s a classic. Given two sorted lists, merge them into a single sorted list. My “go-to” interview question is a variation of this. While linked lists and pointers may not come up every day, this has an interesting loop that solves a problem not-too-different from ones that come up in real life, collating two different sources of information.

There are also plenty of edge cases to worry about, even while (I think, for people with a college background) the problem is familiar enough to not be overwhelming. Some highlights:

  1. People often forget the final block, where we deal with the “stragglers” in the case that l1 and l2 weren’t close to the same length.
  2. People often end up getting very concerned and confused about the body of the main loop — merging is a tricky operation, I don’t blame them. I don’t expect a polished response, but it is a measure of how confidently people can reason about loop invariants.
  3. Maybe loop invariants seems like a fancy and intimidating term, but we often do that informally: what’s true “on every iteration of the loop”? It’s a powerful question.

Behind-the-scenes, this presents an opportunity to really reason about pointers and references. A natural sequel question is an “intersection” (rather than union) sort of problem. The problem can be made simpler, for some people, by merging two arrays, and forgetting memory concerns for the time being.

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        
        rhead = None
        if l1.val < l2.val:
            rhead = l1
            l1 = l1.next
        else:
            rhead = l2
            l2 = l2.next
        r = rhead
        
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                r.next = l1
                r = r.next
                l1 = l1.next
            else:
                r.next = l2
                r = r.next
                l2 = l2.next
        
        if l1 is not None:
            r.next = l1
        else:
            r.next = l2
        
        return rhead

You can find all of the linked list problems solved on this site here.