All posts by Aaron

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

Count Islands (Leetcode 16)

Leave a comment

Did this one a while ago. “Just” an exercise in DFS, counting connected subgraph or something. A nice enough word-problem for exercising “recognizing” when graphs appear. Ah, that’s a nice topic to consider.

class Solution(object):
    def visited(self, i, j):
        return (i, j) in self.seenSet
    def mark(self, i, j):
        self.seenSet.add((i, j))
    def neighbors(self, i, j):
        ns = []
        if i > 0:
            ns.append((i-1, j))
        if j > 0:
            ns.append((i, j-1))
        if i < (len(self.grid) - 1):
            ns.append((i+1, j))
        if j < (len(self.grid[0]) - 1):
            ns.append((i, j+1))
        return ns
    def markIsland(self, i, j):
        assert(self.grid[i][j] == '1')
        assert(not self.visited(i, j))
        toMark = [(i, j)]
        while toMark:
            i, j = toMark.pop()
            if self.visited(i, j):
                continue
            self.mark(i, j)
            for n in self.neighbors(i, j):
                a, b = n
                if self.grid[a][b] == '1':
                    if not self.visited(a, b):
                        toMark.append(n)
                        
    def numIslands(self, grid):
        self.seenSet = set([])
        self.grid = grid
        islandCount = 0
        for i in range(len(grid)): # for each row
            for j in range(len(grid[i])): # for each column
                if grid[i][j] == "0":
                    continue
                if self.visited(i, j):
                    continue
                self.markIsland(i, j)
                islandCount+=1
        return islandCount
Binary Tree, Interview Questions

Tree Equality (Leetcode 15)

1 Comment

Now this I’m certain is a classic. I like how it’s not, well, a single tree! A neat second-lecture problem on binary trees, I’d think.

class Solution(object):
    def isSameTree(self, p, q):
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False
        if not self.isSameTree(p.left, q.left):
            return False
        if not self.isSameTree(p.right, q.right):
            return False
        return True

This “design” or style of programming is curious. Would the students suspect that “I thought about enough cases, and figured if there’s no other reason, we can return true”? I guess reasoning by cases never felt very persuasive to me when I was starting out, it’s hard to convey that we really have covered all the cases. I don’t know what threshold I crossed to feel more confident about reasoning-by-cases. Now that I do feel comfortable, I think this can be a valuable real-world tool, too.

Other binary tree problems with solutions can be found here.

Postscript: About 9 months after posting this, I was adding more questions, and I had misread my notes and thought this wasn’t a question I solved yet. My new approach is almost character-for-character the exact as listed above! Surprising.