All posts by Aaron

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
Interview Questions, Numerical

Is This Number Prime (Code Wars 8)

Leave a comment

Primality is a math-y topic. Sure, let’s implement the naive definition of what a prime number is. Excuse to talk about a bit of trivia I know.

Meta-note: not sure what the question-author is getting at with the Wikipedia mention. I don’t know if they’re “trying to make knowledge accessible”, or they don’t realize the limits of Wikipedia. I think that, and their encouragement that “there are no fancy optimizations required, but…” shows that they may have certain assumptions about their audience. Ah well!

Key facts:

  1. n % m == 0 when m divides n. So we can recast the definition of primality as: for our input n, is there such an m such that n%m==0? I would venture that this is the “trivial” solution the author was thinking of.
  2. A subtle complication is that n can be very big. Counting up to n may actually take a long time, even though the data itself is very small. If n were 100 digits, for instance, we’d just never finish. Fortunately, we’re not in that scenario.
  3. Cute trick: say that n is not prime. So there must be some a*b=n. Try to convince yourself that one of a or b must be less than the square root of n, or a and b are the square root of n. Turning that around: if there’s some number that divides n, it will be found between 2 and sqrt(n). This is a much shorter loop (still a big loop!) to get through. It gets us across the finish-line, here.
import math
def is_prime(num):
    if num < 2: return False
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0: return False
    return True

Closing Notes

I’m not a big fan of using numerical questions for interview questions. Obviously if it comes up in the work etc. etc., but these sort of questions seem more “targeted” (you either know the right approach or you don’t). This one is an interesting way to present the unintuitive fact that even though your input is “only” one number, your loop can run for a really long time! n, for O(n), is the number of values between 0 and num, which is exponential in the length of n. For the times I do other numerical questions, I’d list them here.

Binary Tree, Interview Questions

Symmetric Tree (Leetcode 4)

Leave a comment

Is a binary tree symmetric about its root? How might one determine this?

There is a whole menagerie of binary-tree-questions that all reflect the same pattern of recursive thinking. I have a whole list here. Presented as a battery, it’s a nice way to build up recursive thinking muscles. Presented in isolation, it feels like an unpleasant surprise to do this sort of unusual problem-solving. Here’s the reasoning

  1. We do the base case.
  2. We imagine we have the answer for our smaller problems.
  3. We recombine those answers into our main answer.

The extra “half-step” here is that we need to realize that we want to be asking if our 2 children are symmetric. So while our initial input takes a single root, we’ll want to defer to an implementation of something like isMirror(root.left, root.right), which asks if the first parameter is a tree that is a mirror-image of the right. This is sort of a reduction: the tree root is symmetric if the two subtrees root.left and root.right are mirror-images of each other.

So, let’s use the 3 steps to implement isMirror(a, b), where a and b are two trees.

Applying the Skeleton

  1. Base cases: if they’re both empty (None or null or whatever), they’re mirror images. Return true, done! If only one is empty, they can’t be mirrors. Return false, done! If a and b have different root values, well then they’re not mirrors, so return false done! (That last case may be the most subtle. I can’t explain it better in this blog-post format).
  2. So far, at the “root” level, our two trees seem like mirror-images. Great. What we want now is a.left to be a mirror of b.right. (Note the left-versus right!) and a.right to be a mirror of b.left. We pretend we already have the answers.
  3. So if both those cases are true, our original trees are mirrors of each other. We’re done, return true! (Or false, if either of those recursive calls were false).

This question seems like a much-more-complicated version of tree equality. One might be (as I was) suspicious of whether the comparison in step 2 is exactly correct. It may be a sort of parity problem, where you only want to “flip” the left-versus-right comparison, and doing it on the 2nd or 3rd recursive layer will erroneously undo the mirroring. As it happens, this is simply not the case, but I think it’s very forgivable to act hesitantly in light of that concern.

def isMirror(a, b):
    if a is None and b is None:
        return True
    if a is None or b is None:
        return False
    if a.val != b.val:
        return False
    return isMirror(a.left, b.right) and isMirror(a.right, b.left)
class Solution(object):
    def isSymmetric(self, root):
        if root is None: return True
        return isMirror(root.left, root.right)
Arrays, Interview Questions, Sorting

Move Zeros (Leetcode 3)

1 Comment

This problem is a fun exercise on arrays. Given an array, move all the zeros to the end of the array. Maintain the relative order of all other elements.

I have some familiarity with the C++ standard library, which includes algorithms similar-to-this (but without the relative order). In languages with very explicit memory-management, this is removing elements from the array “in spirit”. In C++, in fact, this is the solution:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        auto new_end = std::remove(std::begin(nums), std::end(nums), 0);
        std::fill(new_end, std::end(nums), 0);
    }
};

Really line 4 is the answer this problem is looking for. Really what happen is that remove “slides the contents down” to fill up the zeros. The new_end variable stores the end of the newly-shrunken array. However, the length of the original nums is unchanged — it’s up to the programmer (me) to really explicitly request that memory be freed, or otherwise messed with.

This also echoes, in a way even more directly, partitioning algorithms. We want to reorder the contents of nums such that one category of elements (those not equal to 0) are on one side, and the other category is at the other side. Again, C++ has this algorithm directly:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        std::stable_partition(std::begin(nums), std::end(nums), [](int n) { return n != 0;});
    }
};

A common critique of code (which I agree with!) is “don’t get too clever with one-liners”. I’ll stress that the above solution, in my mind, is fine because it really is just using the fact that the algorithm is exactly what the problem is asking for. Akin to using the built-in sort method for a question that asks you to sort items. C++ is just a bit verbose.

Say, however, that we don’t have such a partition algorithm. Or that the problem is explicitly asking us to implement a partition algorithm. One trick we can do here is exploit that we know how to create new 0s. In contrast to when our array might container pointers or similar, we can just “remember how many zeros to add in later”. Here’s a Python version, basically of the first C++ solution:

class Solution(object):
    def moveZeroes(self, nums):
        nextWrite = 0
        for nextRead in range(len(nums)):
            x = nums[nextRead]
            if x == 0:
                continue
            nums[nextWrite] = x
            nextWrite += 1
        for zeroOut in range(nextWrite, len(nums)):
            nums[zeroOut] = 0

Basically nextWrite serves as new_end, the first for loop is remove, and the second for loop is fill.

Say, however, instead of an array of 0s, we have an array of objects, and we’ve been partitioning them based on whether their, I don’t know, books-checked-out-of-the-library-count was 0. We couldn’t really do the above approach because we couldn’t reconstruct a whole object after-the-fact. A nice sequel problem to consider, basically, how do we “really” implement partition.

PS: This problem can be found in codewars, too. I’d say related questions are collected under array questions, or sorting questions.

Tools and Takeaways

  1. Moving elements within an array is a common sort of “vocabulary” pattern. Remove, partition, etc., are often building blocks of larger algorithms.
  2. Sometimes we may break a for-loop up into multiple “ranges”. In our first approach, we go through the “tail” of the input array to zero-out those contents.
  3. Sometimes we can recreate the same values we care about, but later. We can do this when the values are integers. Sometimes we can’t get away with that, and have to do something more sophisticated.
Interview Questions, Strings

Replace with Alphabet Position (Code Wars 7)

Leave a comment

An interesting application of maps (or transforms?) or something.

I think it’s always interesting when a question motivates some precomputed data. In this case we want to encode, well, the alphabet. Other examples are various bit-manipulation stuff, or Roman numeral stuff, and probably many more. Otherwise we’re doing a pretty straightforward mapping. A “normal” for loop this time.

def alphabet_position(text):
    # This can all be computed statically,
    # compute it dynamically for now
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    alphabetPositions = {}
    for i in range(len(alphabet)):
        alphabetPositions[alphabet[i]] = str(i+1)
    
    result = []
    for s in text:
        s = s.lower()
        if s in alphabetPositions:
            result.append(alphabetPositions[s])
    return " ".join(result)

No real interesting notes for this one, I’m afraid. A few little bits of trickiness with types (see the str on line 7), off-by-ones (also on line 7), and some comfort with joins and other tricks. Oh, and lower().

I suppose it’s a nice exercise on building and using a map. Yes, I like that, that’s true. Overall I’d say it’s a string-related question, and other string questions can be found here.

Interview Questions, Strings

Pairify Strings (Code Wars 6)

Leave a comment

This one’s a quick exercise in slices, if you’re comfortable with those in Python. I like that (to me) the solution suggests an interesting loop, one that isn’t a ready for-loop.

It also suggests an interesting question of memory usage, maybe. What’s going on with s, and how is it shrinking (or not?). Are we changing the original input string? Other sort of “basic” questions that may test the applicant’s familiarity with runtime environments.

def solution(s):
    res = []
    while len(s) > 1:
        p, s = s[:2], s[2:]
        res.append(p)
    if len(s) == 1:
        res.append(s+'_')
    return res

Would be curious to see this without slices. I like this, though, that it motivates slices and an “interesting” for loop. More exercises on strings can be found here.

Real-World Application

I don’t think there’s a ready real-world application for this. However, taking a single stream of data, and digesting it into smaller chunks and feeding those into a later collection: that happens all the time. I think the skills exercised by this particular problem are pretty tactical (slices, for-loop wrangling) but the discussion about resource usage or other larger design questions can invite consideration of real-world analogs.

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.