Category Archives: Interview Questions

Interview Questions

Binary Tree Search (Code Wars 20)

This is probably the right “intro to trees” question I’ve been looking for. The previous one I’ve been doing, “print everything in a binary tree”, is a bit too clunky. For those, people get hung up on the fixation with in-order versus pre-order or whatever, and also the problems usually model it as return an array of the visited nodes; and so they want to pass that as an out-parameter or similar. Ugh!

So I like this better.

def search(n: int, root: Optional[Node]) -> bool:
    """ Determines if a value is in a binary tree (NOT bst) """
    if root is None:
        return False
    if root.value == n:
        return True
    return search(n, root.left) or search(n, root.right)

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

Path Finder 3 (Code Wars 18)

Leave a comment

OK this series is winning me over. Cost function is just interesting enough.

def neighbors(maze, i, j):
    toTry = []
    if i > 0:
        toTry.append((i-1, j))
    if j > 0:
        toTry.append((i, j-1))
    if i + 1 < len(maze):
        toTry.append((i+1, j))
    if j + 1 < len(maze[i]):
        toTry.append((i, j+1))
    return toTry
def path_finder(maze):
    maze = maze.split()
    cost = {}
    toVisit = set([(0,0)])
    cost[(0,0)] = 0
    target = (len(maze)-1, len(maze)-1)
    while toVisit:
        i, j = toVisit.pop()
        c = cost[(i, j)]
        for (a, b) in neighbors(maze, i, j):
            d = abs(int(maze[i][j]) - int(maze[a][b])) + c
            if (a, b) not in cost:
                cost[(a, b)] = d
                toVisit.add((a, b))
            elif cost[(a, b)] > d:
                cost[(a, b)] = d
                toVisit.add((a, b))
    if target in cost:
        return cost[target]
    return False
Interview Questions

Path Finder 2 (Code Wars 17)

Leave a comment

I like the idea of a series. I suppose this is a nice-enough warm up to Djiskstra.

def neighbors(maze, i, j):
    toTry = []
    if i > 0:
        toTry.append((i-1, j))
    if j > 0:
        toTry.append((i, j-1))
    if i + 1 < len(maze):
        toTry.append((i+1, j))
    if j + 1 < len(maze[i]):
        toTry.append((i, j+1))
    final = [(a, b) for (a, b) in toTry if maze[a][b] == '.']
    return final
def path_finder(maze):
    maze = maze.split()
    for row in maze:
        assert(len(row) == len(maze))
    cost = {}
    toVisit = set([(0,0)])
    cost[(0,0)] = 0
    target = (len(maze)-1, len(maze)-1)
    while toVisit:
        i, j = toVisit.pop()
        c = cost[(i, j)] + 1
        for (a, b) in neighbors(maze, i, j):
            if (a, b) not in cost:
                cost[(a, b)] = c
                toVisit.add((a, b))
            elif cost[(a, b)] > c:
                cost[(a, b)] = c
                toVisit.add((a, b))
    if target in cost:
        return cost[target]
    return False
Interview Questions

Path Finder 1 (Code Wars 16)

Leave a comment

Variation on island finding. Which is to say, more depth-first-search. Embarrassingly, I forgot some the base case!

def neighbors(maze, i, j):
    toTry = []
    if i > 0:
        toTry.append((i-1, j))
    if j > 0:
        toTry.append((i, j-1))
    if i + 1 < len(maze):
        toTry.append((i+1, j))
    if j + 1 < len(maze[i]):
        toTry.append((i, j+1))
    final = [(a, b) for (a, b) in toTry if maze[a][b] == '.']
    return final
def path_finder(maze):
    maze = maze.split()
    for row in maze:
        assert(len(row) == len(maze))
    seen = set([])
    toVisit = [(0,0)]
    seen.add((0, 0))
    target = (len(maze)-1, len(maze)-1)
    while toVisit:
        i, j = toVisit.pop()
        for (a, b) in neighbors(maze, i, j):
            if (a, b) in seen:
                continue
            seen.add((a, b))
            toVisit.append((a, b))
    return target in seen
Interview Questions

Nth Pell Number (Code Wars 13)

Leave a comment

I typically don’t like math problems. This one seems like a “small” enough one to maybe introduce students to and get familiar with the notation, so they have at least some tools if an interviewer decides to spring something like this on them. So I like it for that reason. Basically a variation of the fib. sequence.

The commitment to the “get” method is a bit odd. Maybe really trying to get to the memoization, stateful approach? Not really needed, unless if I’m really missing something…. Presumably a limitation of the test design itself.

class Pell(object):
    def get(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        nprev = 1
        x = 2
        for i in range(3,n+1):
            nprevprev = nprev
            nprev = x
            x = (2*nprev) + nprevprev
        return x