Monthly Archives: November 2021

Interview Questions, Linked List

Remove Duplicates from Sorted LL (Leetcode 11)

Leave a comment

There is definitely a pattern! Sorted array, and previously move zeros. Well this has no relation to the remove-zeros, but it’s interesting….

This suggests an interesting lesson as well, three variations on a theme. That’s why I’m doing these things.

class Solution(object):
    def deleteDuplicates(self, head):
        if head is None:
            return head
        curr = head
        while curr is not None and curr.next is not None:
            while curr.next is not None and curr.val == curr.next.val:
                curr.next = curr.next.next
            curr = curr.next
        return head

I bet there’s a nicer way of writing that loop. It’s interesting that this logic “feels” neater to me (especially if my suspicion of a nicer way of writing that loop bears out.)

Nested loops with linked lists! Neat.

Interview Questions

Search Insert Position (Leetcode 10)

Leave a comment

Why don’t they just call it binary search? The runtime requirement is a giveaway — and for people who are “fluent” enough with runtime complexity to understand O(lg n) but don’t yet know about binary search, you are a rare breed, I’d think.

So I’ll spare you the usual C++ std::algorithm implementation. I like this loop. I think a lesson where we really 100% understand the intuition behind binary search, and then having students actually implement it, could be a nice hour.

class Solution(object):
    def searchInsert(self, nums, target):
        lb = 0
        ub = len(nums)
        while lb < ub:
            mid = (lb+ub)/2
            #print(lb, mid, ub)
            
            searchValue = nums[mid]
            
            # Feels hacky... can we do something smarter?
            if mid == lb:
                assert(ub == lb + 1)
                if searchValue < target:
                    return ub
                return lb
                
            if searchValue > target:
                ub = mid
            elif searchValue < target:
                lb = mid
            else:
                return mid
        #print("done", lb, ub)
        assert(lb == ub)
        return lb
Interview Questions

Remove Duplicates from Sorted Array (Leetcode 9)

Leave a comment

This is the warm-up sort of problem to one we’ve seen earlier. The solution is the same spirit.

This is a nice example (finally!) of my drumbeat that a lot of these problems are really reflections of the same “root” problem. While there are still many such root problems, after a while you start to see repetitions, in addition to the shared fundamental material of course.

So we have the same sort of solutions. The first is the C++ algorithm, which is likely “too close to the real problem”. The interviewer would naturally ask “please implement the “unique” function you use there.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto new_end = std::unique(std::begin(nums), std::end(nums));
        return std::distance(std::begin(nums), new_end);
    }
};

So let’s do that in Python. There is probably a similar-enough algorithm, but ironically let’s just do a much more explicit version.

class Solution(object):
    def removeDuplicates(self, nums):
        i = 0
        j = 0
        while i < len(nums):
            nums[j] = nums[i]
            j += 1
            new_i = i + 1
            while new_i < len(nums) and nums[i] == nums[new_i]:
                new_i += 1
            i = new_i
        return j

I actually really like this question. There are multiple ways of solving it. The loops involved here are understandable, but different from the “cliche” for-loops. They also start the idea of having 2 different indices into the same array, a powerful tool that a lot of novice programmers seem pretty surprised by.

Interview Questions, Linked List

Flatten a Doubly-Linked List (Leetcode 8)

Leave a comment

Isn’t this basically the same as the last one? Instead of left and right it’s “child” and “next”. The doubly-linked stitching is a bit different, but nothing major. Interesting contrast.

class Solution(object):
    def flatten(self, head):
        if head is None:
            return None
        if head.child is None:
            self.flatten(head.next)
            return head
        flatChild = self.flatten(head.child)
        head.child = None

        childEnd = flatChild
        while childEnd.next != None:
            childEnd = childEnd.next
        
        
        oldNext = head.next
        if oldNext:
            oldNext.prev = childEnd
        childEnd.next = oldNext

        flatChild.prev = head
        head.next = flatChild
        
        return head
Binary Tree, Interview Questions

Flatten Tree (Leetcode 7)

1 Comment

I think this question has a lot of potential. It is very algorithmic-y, but also has an idea that can come up in practice. Flattening a 2D object like a tree into a 1D object like a list happens in, e.g., the unit utility ls or the Window’s equivalent dir. However, the idea of keeping that same object in memory, and “punning” the linked-list structure over the tree structure, seems unneeded. Saving memory is great and I think we’re much too inclined to think memory is “free”, but from an pedagogical perspective we’re building off of a number of concepts.

Prerequisites and Solving

Of course the student should be very comfortable with typical recursion-and-binary-trees material. They should also be comfortable with updating pointers, like with complicated linked-lists questions (say, my favorite question of merging two linked lists).

Once we have all that, considering the question-actual: The “child management” is a bit tree-specific, but I think that’s OK (we’re allowed to talk about trees sometime). The idea of transforming the tree in question I think helps illustrate the power of recursion — many of the questions I’ve been thinking of don’t mutate the input.

One complication that caught me: You really have to account for both children, even the one you want to leave empty. I think this is a good “tough” question. I guess Leetcode calls it medium, sure. I’ve collected all my tree solutions here.

class Solution(object):
    def flatten(self, root):
        if root is None:
            return None
        root.right = self.flatten(root.right)
        if root.left is None:
            return root
        
        flatLeft = self.flatten(root.left)
        root.left = None
        t = flatLeft
        while t.right is not None: t = t.right
        t.right = root.right
        
        root.right = flatLeft
        return root
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.

Musings

Different Categories of Programming Problems

Leave a comment

Probably the most talked-about interview question types are those that exercise “data structures and algorithms” (DSA) knowledge. That’s a big category, including everything from linked lists to graph algorithms to dynamic programming to sometimes even combinatorics or probability. These questions are more-or-less quizzing the interviewees on their comfort with undergraduate theory knowledge. As I’ve noticed, a lot of the problems on the website Leetcode, in particular, are exercises in this vein.

A more “organic” type of interview question that’s recently piqued my interest is one I see more often in codewars. The higher-numbered questions (which are the easier ones) are often exercises in manipulating strings or arrays in some fashion. Some are pretty naturally motivated, some are contrived. However, they seem to me to be very nice exercises in reasoning about indexes, expressions, and values evolve over multiple iterations of a loop.

I have an interest, and am able to pursue that interest, in helping people learn computer science and programming. When I consider, for that purpose, the first category of questions, the perhaps-frustrating answer to “how do I better at these?” is “learn or review undergraduate algorithms”. This is a tall order for those with a nontraditional background. The second type of question is, on the one hand, more elementary, but consequently also more able-to-be-learned by those with a nontraditional background. I think also they’re quite useful, and I’m curious if there’s some way of more formally transforming those sorts of questions into teaching material.

I recall taking a computer science course, and the professor needed to refer to 2-dimensional array. Professors rarely used an explicit programming language, but even so he took the time to “allocate” a n^2 block of memory, and an accompanying array of n pointers that each pointed to the “next” length-n sequence in that block. My classmates and I were astonished by the sheer cleverness of what was, I later found out, a fairly routine construction. There is a huge “surface area” of material to learn for anything, including programming, and I’m always keen on finding more ways to help people explore more of that quickly.

The term I like to use is “vocabulary”. Some of the loops revealed by these codewar problems help teach new “vocabulary”, but I don’t think that’s quite the right analogy. If the core building blocks of a language are its words, and programs are the books and essays with that language, then I think we’re learning sentences and phrases. Independent of which problems are harder (leetcode-style DSA or codewars-style loops), I think the sheer breadth of loop-based questions in codewars can really augment the abilities of a junior programmer by showing them lots and lots of new sentences — sentences they can absorb and adapt on their own later. As a pedagogical tool for nontraditional students, I really like those. DSA-style questions feel more like complications over the same two-dozen really-complicated DSA sentences you learn in school.

Now, codewars and leetcode and friends are motivated by the infamous “coding interview”. So: which style questions make for better interviews? I think much harder versions of codewars-style questions, with sophisticated (and well-motivated) loops, could go a long way as an evaluation tool. You’re not quizzing on them if they remember Djikstra’s algorithm, you’re seeing how they handle a complicated loop with interesting interactions. Of course there isn’t a bright line: my favorite interview question is more-or-less the merge step of mergesort. I think that’s sufficiently “real” enough, but its heritage is in DSA.

My experience with codewars versus leetcode may not be representative, but it was interesting to see the contrast between the questions I got in those two sites as I’ve been writing up this blog.

Interview Questions, Strings

Highest-Scoring Word (Code Wars 10)

Leave a comment

Map letters to numbers, map words to a “score” (presumably defined by the sum of numbers from the per-letter mapping), find the highest-scoring word.

I actually like this one a lot as a set of loop exercises. It’s sort of a couple compound ones. Solution is “merely” an exercise in being fluent in loop writing. It’s a very nice junior test, I think.

def high(x):
    score_map = {}
    for i, letter in enumerate("abcdefghijklmnopqrstuvwxyz"):
        score_map[letter] = i + 1
    def score(w):
        return sum([score_map[c] for c in w])
    words = x.split(' ')
    
    maxScore = 0
    maxWord = ""
    
    for w in words:
        if score(w) > maxScore:
            maxScore = score(w)
            maxWord = w
            
    return maxWord

Strings are a popular topic for practice interviews for newcomers to the field. I list the string questions here.

Arrays, Interview Questions

Find the halfway point (Code Wars 9)

This one, actually called “Equal sides of an array” threw me for a loop because I hadn’t realized we were excluding the i-th element for each possible index where we would try splitting the array. That induces some off-by-one-ish errors, which is the main interesting part.

This is a nice first approach, and it gets the goal:

def find_even_index(arr):
    if len(arr) == 0: return True
    for i in range(len(arr)):
        if sum(arr[:i]) == sum(arr[i+1:]):
            return i
    return -1

The slices-and-sums can be helper functions.

The natural sequel is to not repeat the addition so many times (so, what’s the runtime complexity of the first solution?). That requires some careful thinking and avoiding off-by-one errors.

def find_even_index(arr):
    if len(arr) == 0: return True
    leftSum = 0
    rightSum = sum(arr[1:])
    if leftSum == rightSum:
        return 0
    for i in range(1, len(arr)):
        leftSum += arr[i-1]
        rightSum -= arr[i]
        if leftSum == rightSum:
            return i
    return -1

Take-Aways

This problem seems to hit a lot of right notes: It’s approachable, it has trickiness that requires careful debugging thought, it has plausible applicability (partitioning resources evenly), and keeps the door open to optimizations. Nice! For this and other array questions, I collect them here.

Interview Questions, Numerical

Count Unique Paths (Leetcode 5)

Leave a comment

Time to count!

This problem has less to do with programming and more to do with combinatorics. What might someone who has no experience with combinatorics do to attempt this problem? I suppose you could say it’s an exercise in recursive thinking, or something. To me it is too much “obviously” a combinatorics problem.

Approach with Combinatorics

A key model is that you can imagine there must “m” right-moves, and “n” down-moves. No more, no less. The only thing left is what order those moves can appear in (right right down, down right right, etc.). All possible orders are valid.

A few ways to model this. So there are a=m+n moves to make, and n of those must be down moves (and implicitly, the remaining m must be right moves), so of the a total moves, we have to choose n to be down moves. So the answer is a-choose-n. (Well OK, a detail of the question is that we’ve already made 1 down-move and 1 right-move, essentially, based on the definition of the problem and where the “robot” is. So subtract both by 1, it’s (a-2) choose (n-1).

Towards a Solution

Now, uh, what’s a-choose-n? That’s a good question. The answer is that this is sort of exactly the motivating exercise. A lot of combinatorics is learning the basic tools, like n-choose-k, and see how problems reflect opportunities to use those tools.

So I implemented n-choose-k in a terrible fashion. Numerical stability is definitely a concern. Python helps alleviate that concern. For other numeric-ish problems, I’ve collected them here.

def factorial(x):
    p = 1
    for i in range(1, x+1):
        p *= i
    return p

class Solution(object):
    def uniquePaths(self, m, n):
        # We move everything "forward"
        # because our robot and goal occupy spaces
        m -= 1
        n -= 1
        
        # Attempt at numerical stability
        a = m+n
        s = min(m,n)
        
        # a!/(a-s)!
        res = 1
        for i in range((a-s)+1, a+1):
            res *= i
        
        # X/s!
        res /= factorial(s)
        return res