Category Archives: Numerical

Interview Questions, Numerical

Self Dividing Numbers (Leetcode 35)

Another from the archive! I’ll confess some annoyance with this style of question (this is not the first or only example) that presents a contrived concept, in this case a “self dividing number“, and define it with the same language as more typical math concepts. I’ve seen it confuse or intimidate students with a nontraditional background as they think “here’s another thing I should have known, but I don’t because of my background”. I just wish these questions would make it clear when they’re making up a concept for the sake of the exercise.

In any case, this is a question that has another interesting-sort of loop. There is a style of using divide-by-10, modulo-by-10 to “iterate” through a number. See the standard atoi question (which I realize I don’t have yet? Something to add.) In binary form we have the implementation of popcount here, or the formatting requirement here.

def selfDividing(n):
    N = n
    while n > 0:
        d = n % 10
        if d == 0:
            return False
        if N % d != 0:
            return False
        n = n // 10
    return True
class Solution:
    def selfDividingNumbers(self, left: int, right: int) -> List[int]:
        res = [i for i in range(left, right+1) if selfDividing(i)]
        return list(res)

Discussion

I like that this has helper functions. For Python you get this cute filtering machinery, and I think that’s also a nice thing for this question. I think even just implementing the single helper function is a good warm-up and could lead into the atoi question, which a question I actually like. Maybe this is a good teaching warm-up before covering atoi. For lack of a better category I called this a numerical question, others of which can be found 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.