Is This Number Prime (Code Wars 8)

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.

Symmetric Tree (Leetcode 4)

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)

Move Zeros (Leetcode 3)

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.

Replace with Alphabet Position (Code Wars 7)

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.

Pairify Strings (Code Wars 6)

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.

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.

Is it a triangle? (Code Wars 5)

Given 3 integers, can there be a triangle with edges equal to those lengths?

I have never encountered even the tiniest of geometric questions in my professional career. On the other hand, many people have worked in graphics and games, where geometric reasoning (presumably) matters a lot. As it happens, even my stunted geometric reasoning was able to handle this question. I think it’ll be a nice exercise on a whiteboard as a general sort of problem-solving measurement, but I don’t see how it says much about the interviewee’s actual software-development capabilities.

Ultimately, what the question is asking for is a list of constraints. If those constraints are all satisfied, then there can exist a triangle with edge-lengths a, b, c. If those constraints aren’t satisfied, then there isn’t.

Finding Constraints

So we have to determine those constraints. What are those constraints? The way I think about them is that I imagine the constraints are true for (a, b, c) so I ask myself something like: “if a, b, c from a triangle (so to speak), and a is really big (relative to b and c), what does b and c look like?”

Sketching out that question on paper, it seems that the “larger” a gets relative to b and c, the “flatter” the triangle has to be. Turning it around, b and c together are always going to be a bit bigger than a. So can hypothesize: “a < b + c”, and pretty quickly establish analogous constraints with the other 2 edges.

So that’s a nice constraint! We can play around with the opposite: say a is 100, and b and c are both 2. It seems pretty clear that b and c won’t be able to touch each other, when placed on either end of a. So that’s reassuring.

Looking at the constraint we have, we have what’s called an “upper bound” on a. We know that the size of a can only get so big before it breaks the rules. Can we go the other way? If we know b and c, does a have to be a certain length? Intuitively, we can imagine a sort of arm or hinge, where one edge is b, the other c. Say c=b/2. Clearly, even if we close the hinge entirely, the end of c is pretty far away from the other end of b. It suggests that the length of a must be at least the difference between c and b, or a > b – c.

Do fun arithmetic, and those are the same constraints as we determined above, just with a sign change. Is this a real proof? Not in my opinion. But at this point I have intuitive arguments that shows the 3 constraints we determined (a<b+c,b<a+c,c<a+b) effectively both upper-and-lower bound the value of each a, b, c, so I got confident enough to hit the go button. Hey, it passed all the tests.

Here are those constraints, plus an edge case handler, written down:

def is_triangle(a, b, c):
    if a < 0 or b < 0 or c < 0:
        return False
    b1 = a + b > c
    b2 = a + c > b
    b3 = b + c > a
    return b1 and b2 and b3

Should I have included pictures explaining my reasoning in this post? Almost certainly yes.

I don’t often explore geometric problems, and I don’t think their a focus for my students, but as more come up the solutions will be found here.

Valid Parentheses (Leetcode 1)

It’s a classic problem: given a string of parentheses, determine if they’re properly nested. The complication here is that, instead of just 1 kind of parens, we have 3 to deal with. This same problem can be found on codewars.

This is often presented as an exercise where the “solution” is to realize that a stack works perfectly for this scenario. What else can we learn from this?

Opportunities for Learning

  1. Helper functions! The flip here is pretty useful and helps makes the different cases we want to deal with clearer.
  2. Dealing with cases! This is an interesting question because we have a lot of branches inside the loop. Usually that’s not so.
  3. An extension of that is thinking about loop invariants. What are all the different cases we can expect in our loop, and what do we want to maintain? For instance, it’s important not to push on close-parens (we’re not just pushing on every character we see, the invariants we want to maintain aren’t quite that).
  4. I like the “tail” condition. We’re not just done at the end of the loop, we have to make sure we’ve matched all our open parens.

Something I’m not so excited about with this question is that, as I’ve seen, it invites a lot of complicated experiments. People seem inclined to try very “stateful” approaches (build up a complicated analysis of the string, start doing some kind of weird tree-ish thing). It seems a lot of the neat-ness of this question is from realizing that you may tempted to have a very sophisticated amount of state, but you “just” need a stack. It’s very gratifying to make those realizations, and can be very valuable for professional software development… but is answering this a useful signal?

class Solution:
    def flip(self, c):
        if c == '}': return '{'
        if c == ')': return '('
        if c == ']': return '['
        assert(False)
        
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in {'(', '[', '{'}:
                stack.append(c)
                continue
            elif len(stack) == 0:
                return False
            elif self.flip(c) == stack[-1]:
                stack.pop()
            else:
                return False
        return len(stack) == 0

It’s a bit difficult to categorize this problem. On the one hand the input is a string, but the intended solution uses a stack. As I think the string-edness is more arbitrary, I would categorize this as a stack-based question, even though that speaks more to the solution than the nature of the problem. Here is where any other stack questions will end up.

Tribonacci (Code Wars 4)

Let’s compute the complete Tribonacci (riff off of “Fibonacci”) sequence.

It’s worth a few minutes understanding and “visualizing” what the solution might look like. In this case, I just mean that we’re going to be returning a list. Moreover, (most of) the elements in that list are computed by prior elements in that list. The list is going to be n elements long (the same n as is a parameter to our function).

One of my favorite exercises: dealing with the edge/easy cases.

  1. If n is 0, we can return the empty list.
  2. If n is less than or equal to the number of elements in signature, we can just return that appropriate subsequence.
  3. Otherwise, we already have enough elements in signature to compute all the other elements we need.

And that’s the answer:

def tribonacci(signature, n):
    if n == 0:
        return []
    if n <= len(signature):
        return signature[:n]
    result = signature[:]
    for i in range(3, n):
        s = result[i-1]+result[i-2]+result[i-3]
        result.append(s)
    return result

Additional Thoughts

  1. The slice on line 5 may not be available in all languages; it will just be more verbose, if slicing isn’t available, with the spirit being the same.
  2. I think sometimes we’re returning a shallow copy (line 5), otherwise a deep copy. Probably not ideal. I wouldn’t let this pass code-review.
  3. We often have for loops that go over an array of length n. Here we’re creating an array of length n. That’s a fun contrast.
  4. This sort of algorithm, where we build the contents of the list based off of previous elements, hasn’t come up very often in my professional experiences. I suppose it’s neat to see what that kind of code looks like, though I think it doesn’t add much versus other, more applicable loop questions.

I’d categorize this question as one in the “recursion” topic. You can find all such questions on this site here.

Displaying Sum in Binary (Code Wars 3)

Here is the next codewars problem. It’s a bit strange: you get two “normal” numbers, and then you need to return their sum as a binary string. Adding two numbers is pretty straightforward in this case: you use the +, to be humorous about this.

Already you can see we have another case of bitwise manipulation! We can use the same trick, again, to iterate through all the bits in our sum and add them to a string.

I had a bug! First, here is the (validated) solution:

def add_binary(a,b):
    assert(a >= 0 and b >= 0)
    s = a + b
    result = []
    while s > 0:
        oldS = s
        result.append(str(s % 2))
        s = s // 2
    result = ''.join(reversed(result))
    return result

Let’s focus on the positives.

  1. The assert on line 2 is my own sanity-checking. Things can get funny in this question if a or b can be negative.
  2. You can barely see where the sum happens in this question: line 3. After that, you can see we completely ignore a, b.
  3. This has a fun combination of the previous 2 questions we talked about. We build up our string as a list of strings (each element in that list is either the string “0” or “1”) and join that list over the empty string. Just as we saw ‘ ‘.join(…) in the previous question, how it combined all the elements into a string, separating each element by ‘ ‘, this combines all elements in our list as a string, separated by , i.e., separated by nothing.
  4. We determine the “next” bit of s with s % 2, just like before. A big change (and this is where the bug is) is on line 8. Previously, we did s = int(s/2), and my initial implementation had that as well. In tests with extremely large integers, that method failed. Let’s discussion why.

The Bug

This is a somewhat advanced bug. Truth be told, if a beginner programmer (esp. from a bootcamp) hit this issue, I’m not sure if they’d have the context to address it. Here’s what happens:

  1. Python distinguishes between integers, which are whole numbers, and floats, which are numbers that can have a decimal point. Adding two integers always gives you the answer you’d expect, so integers are simple. Floating point numbers ultimately have to round (similar to how, with 0.333333333…, eventually you have to decide when to stop writing 3s!).
  2. In our code, s is an integer, except when it’s being divided by 2. Python will automatically convert it into a float. That is why we immediately turn it back into an integer, with int(s/2). This gives the effect of “chopping off” anything after the decimal point, which is what we want. (We’d expect the decimal to either be .0, when s was previously even, or 0.5, when s was previously odd.)
  3. However, that rounding that we have to do with floating-point-numbers doesn’t just happen after the decimal point. For very large numbers, the rounding can happen in the thousandth’s place, or similar (so rather than a big number ending with 124,325.0, it would look like 124,000.0). This truncation is too aggressive!
  4. So the bug manifested that we were outputting a binary number with just a long string of 0s at the end, when it should have been a mix of 0s and 1s.
  5. The fix was me searching around online until I found out how to do truncating-integer-division in Python. That avoids converting the integer into a double, and therefore we never introduce that inadvertent rounding, and we get the right answer!