Tag Archives: interesting loops

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, Introductory

Robot Return to Origin (Leetcode 33)

I guess I have a lot of archives. This question is mainly about reasoning-by-cases, which is a way of handling a question that isn’t explicitly called out so well by the usual exercise batteries, in my experience (it’s neither a data structure nor an algorithm, not really).

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        x = 0
        y = 0
        for m in moves:
            if m == 'U': y += 1
            if m == 'D': y -= 1
            if m == 'R': x += 1
            if m == 'L': x -= 1
        return x == 0 and y == 0

Discussion

  1. The question is of course contrived, but I think it’s a good exercise in initial practice in “understanding a question” and translating that to a programming-amenable approach.
  2. The question does invite overthinking it, I would guess. Hopefully not everyone, but I can see a student panicking and starting to make an array-of-arrays. Knowing that sometimes you don’t have to do the hardest thing you can think of is very valuable in interviews and in practice!

I don’t know really know a general category to put this in. I’ll call it an introductory interview question, and collect any more here.

Interview Questions, Matrix

Reshape the Matrix (Leetcode 30)

I decided to redo this problem, from the archives in Python. Previously I had it in C++. You’d think this post, then, of resizing a 2D array, would have been straightforward. Here are some notes:

  1. The key insight (in my approach, at least) is that assuming the resize is valid, there are r*c elements, and we can define helper functions like getRow and getColumn that take an i, and an r, c dimensions, and return the row and column of the ith element. In this way we can walk through the arrays “in parallel”
  2. I hit an issue with some terse way of allocating an array in python. It seems something like [[0]*c]*r leads to shallow copies in some cases, and that tripped me up.
  3. Then, of course, I managed to get R and C mixed up.

I think this is a good exercise for junior people who say they feel comfortable with 2D arrays.

Complete with debugging statements, here is my approach:

def getRow(i, r, c):
    #print('row of', i, '-th element in matrix ', r, '*', c, 'is', i // c)
    return i // c
def getCol(i, r, c):
    return i % c
class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        R = len(mat)
        if R is 0: return mat
        
        C = len(mat[0])
        
        if R * C != r * c:
            return mat
        
        res = []
        for i in range(r):
            res.append([])
            for j in range(c):
                res[i].append(0)
        
        for i in range(r*c):
            #print(getRow(i, r, c), getCol(i, r, c), getRow(i, R, C), getCol(i, R, C))
            old = mat[getRow(i, R, C)][getCol(i, R, C)]
            res[getRow(i, r, c)][getCol(i, r, c)] = old
                
        return res

Take-Aways

This covers interesting questions like allocation (pre-allocating the results array), bounds-checking in a nontrivial setting (numrows, numcols), and then an interesting question of mapping. That mapping also really requires a comfort with indices versus the values of an array, plus array-of-arrays instead of just arrays. I think this is a good “hard” phone-screen question.

For real-world applicability, I’ve never worked too much with 2D arrays, certainly not this explicitly. However, the challenge of iterating over 2 different objects/data-structures that don’t naively both map to the same for loop (so to speak), that’s something that comes up a lot, albeit not so directly as in this code. Just recently I was iterating over 2 similar (but not the same!) trees at work, and had to make sure the iteration remains in lockstep. Of course, this complex-iteration also comes up in my favorite merge-linked-list sort of questions. Again, not literally identical, but the same “genus”.

Interview Questions

Monotonic Array (Leetcode 26)

Another from the archives. I think this is a nice introduction to a more “stateful” complicated loop. A productive approach was to break it into cases. I think this is a nice introduction to state machines.

class Solution {
    public:
    enum class dir {
        UNKNOWN,
        INCREASING,
        DECREASING
    };
    bool isMonotonic(vector<int>& nums) {
        auto state = dir::UNKNOWN;
        for (int i = 1; i < nums.size(); i++) {
            switch (state) {
                case dir::UNKNOWN:
                    if (nums[i-1] < nums[i]) {
                        state = dir::INCREASING;
                    }
                    else if (nums[i-1] > nums[i]) {
                        state = dir::DECREASING;
                    }
                    break;
                case dir::INCREASING:
                    if (nums[i-1] > nums[i]) {
                        return false;
                    }
                    break;
                case dir::DECREASING:
                    if (nums[i-1] < nums[i]) {
                        return false;
                    }
                    break;
            }
        }
        return true;
    }
};
Interview Questions

Normalize Array Indexes (Code Wars 19)

This was a problem a student brought to me. It was very interesting! It suggests 2 approaches of different “trickiness”.

The natural approach suggested by the problem’s description is to use a for-loop. This is complicated by that, in an unusual twist, the for loop (over the provided index parameter) isn’t really related to the length of the array. So while you have the i or whatever in your for loop, you want to resist the temptation to do a[i].

Ultimately you’ll want a secondary variable. While i tracks the provided index, j handles the “wrap-around” logic:

def norm_index_test(seq, ind):
    if seq == []:
        return None
    isneg = ind < 0
    ind = abs(ind)
    j = 0
    for i in range(ind):
        j += 1
        if j == len(seq):
            j = 0
    assert(j < len(seq))
    if isneg and j != 0:
        j = len(seq) - j
    return seq[j]

This is actually probably the hardest form of the question, complicated by the negative indexes. If I were asking this problem, I would not ask about negative indexes. Ugh!

Once you can trust modular arithmetic (and maybe Python makes it too easy? Not sure if all languages define module of a negative number the same), it’s a one-liner. Cute, but OK.

def norm_index_test(seq, ind): 
    if seq == []:
        return None
    return seq[ind%len(seq)]
Interview Questions

RLE compress string (Leetcode 19)

OK, a sequel!

I like:

  1. We have two views of the same array.
  2. We can start at 1 in the for-loop
  3. Opportunity for invariants to help our loop-based reasoning.
  4. Things get much simpler with the helper function (i.e., I made a lot of bugs until I decided to use a helper function).

I don’t think I’m biased to say this one requires a bit of careful thought!

class Solution(object):
    def commitLetter(self, chars, c, i, count):
        assert(count > 0)
        chars[i] = c
        i += 1
        if count > 1:
            w = str(count)
            for t in w:
                chars[i] = t
                i += 1
        return i
            
    def compress(self, chars):
        if len(chars) == 0: return []
        
        count = 1
        j = 0
        lastChar = chars[0]
        
        for i in range(1, len(chars)):
            if chars[i] == lastChar:
                count += 1
            else:
                j = self.commitLetter(chars, lastChar, j, count)
                lastChar = chars[i]
                count = 1
        j = self.commitLetter(chars, lastChar, j, count)
        return j
Interview Questions

Decompress RLE (Leetcode 18)

Another experiment: can leetcode-esque problems provide a useful way to learn computer science topics?

This problem is about run-length-encoding. Still pretty algorithmic, but a bit more applied. Though, as I did it, it really did feel more like understanding the description more than solving the problem. On the other hand, I think this is a great “fundamentals” problem.

class Solution(object):
    def decompressRLElist(self, nums):
        res = []
        for i in range(0, len(nums), 2):
            freq = nums[i]
            val = nums[i+1]
            res += freq*[val]
        return res
Interview Questions

Highest Rank Number (Code Wars 12)

Leave a comment

I guess what I’m curious about in my one “musings” post is what code wars calls “fundamentals”. This is one such question. I think it’s a really nice one. It is very approachable and understandable, but finicky enough where it’s not completely trivial. It also invites the question about certain “quality of life” improvements one can find in a language. If nothing else, I’m a big proponent of the “max” function, which can play a role here. Mea culpa, I hadn’t read the question fully and forgot the case if there are two candidate numbers.

def highest_rank(arr):
    counter = {}
    for x in arr:
        if x not in counter:
            counter[x] = 0
        counter[x] += 1
    maxCount = 0
    maxCand = None
    for k in counter:
        if maxCount < counter[k]:
            maxCount = counter[k]
            maxCand = k
        if maxCount == counter[k] and maxCand is not None:
            maxCand = max(maxCand, k)
    return maxCand