Category Archives: Interview Questions

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.

Binary Tree, Interview Questions

Min Depth of Binary Tree (Leetcode 14)

Leave a comment

This one is interesting. It tricked me, I had answered the wrong question at first! It is curious how it defines the depth, that it requires a leaf node. I was computing something else, something like max height.

This one’s interesting because it provides a somewhat (unless if I’m missing something) complicated inductive case. Good to know!

class Solution(object):
    def minDepth(self, root):
        if root is None:
            return 0
        lDepth = self.minDepth(root.left)
        rDepth = self.minDepth(root.right)
        # Were we a leaf?
        if lDepth is 0 and rDepth is 0:
            return 1
        if lDepth is 0:
            return rDepth + 1
        if rDepth is 0:
            return lDepth + 1
        return min(lDepth, rDepth) + 1
Binary Tree, Interview Questions

Univalued Binary Tree (Leetcode 13)

Leave a comment

I think I want to do a battery of tree exercises. Here’s one. The names some of these community-contributed questions come up with are quite striking.

We can either think about maintaining some global, “ah, here is the value we should compare again”, or we can exploit the transitive nature of equality.

class Solution(object):
    def isUnivalTree(self, root):
        if root is None: return True
        if root.left is not None and root.left.val != root.val:
            return False
        if root.right is not None and root.right.val != root.val:
            return False
        return self.isUnivalTree(root.left) and self.isUnivalTree(root.right)

Hey, let’s do the global approach too, why not. Well, not global exactly, but you know.

class Solution(object):
    def isUnivalTreeInternal(self, root):
        if root is None: return True
        if root.val != self.val: return False
        return self.isUnivalTreeInternal(root.left) and self.isUnivalTreeInternal(root.right)
    def isUnivalTree(self, root):
        if root is None: return True
        self.val = root.val
        return self.isUnivalTreeInternal(root)
Interview Questions

Longest Common Prefix (Leetcode 12)

Leave a comment

This is another good one, I think. Strings and arrays are commonly-requested topics.

  1. We can observe that “the first string must contain the longest common prefix”. That’s an interesting tool that we can leverage.
  2. So we know that we can iterate over that length. We want to “scan” all the strings in parallel, and that’s how.
  3. We have an interesting “return from a nested loop” potential. Helper functions may make this clearer. Potential sequel homework.
class Solution(object):
    def longestCommonPrefix(self, strs):
        if len(strs) == 0:
            return ""
        root = strs[0]
        if len(root) == 0:
            return ""
        
        prefixLen = 0
        for i in range(len(root)):
            for s in strs[1:]:
                if i >= len(s):
                    return root[:prefixLen]
                if s[i] != root[i]:
                    return root[:prefixLen]
            prefixLen += 1
        return root

Interview Questions

Count characters in a string (Code Wars 11)

Leave a comment

This one’s a classic! I’m a big fan of this as a warm-up question. A simple exercise of looping, strings, exercising two different cases with dictionaries (what if the key already exists, what if it’s new), and best of all it’s a pretty reasonable distillation of real programming scenarios.

def count(string):
    m = {}
    for c in string:
        if c in m:
            m[c] += 1
        else:
            m[c] = 1
    return m

I’m sure there are very fancy ways of doing this. I’d rather use a default-dictionary, but otherwise I’m happy with this solution.

Interview Questions, Linked List

Remove Duplicates from Sorted LL (Leetcode 11)

Leave a comment

There is definitely a pattern! Sorted array, and previously move zeros. Well this has no relation to the remove-zeros, but it’s interesting….

This suggests an interesting lesson as well, three variations on a theme. That’s why I’m doing these things.

class Solution(object):
    def deleteDuplicates(self, head):
        if head is None:
            return head
        curr = head
        while curr is not None and curr.next is not None:
            while curr.next is not None and curr.val == curr.next.val:
                curr.next = curr.next.next
            curr = curr.next
        return head

I bet there’s a nicer way of writing that loop. It’s interesting that this logic “feels” neater to me (especially if my suspicion of a nicer way of writing that loop bears out.)

Nested loops with linked lists! Neat.

Interview Questions

Search Insert Position (Leetcode 10)

Leave a comment

Why don’t they just call it binary search? The runtime requirement is a giveaway — and for people who are “fluent” enough with runtime complexity to understand O(lg n) but don’t yet know about binary search, you are a rare breed, I’d think.

So I’ll spare you the usual C++ std::algorithm implementation. I like this loop. I think a lesson where we really 100% understand the intuition behind binary search, and then having students actually implement it, could be a nice hour.

class Solution(object):
    def searchInsert(self, nums, target):
        lb = 0
        ub = len(nums)
        while lb < ub:
            mid = (lb+ub)/2
            #print(lb, mid, ub)
            
            searchValue = nums[mid]
            
            # Feels hacky... can we do something smarter?
            if mid == lb:
                assert(ub == lb + 1)
                if searchValue < target:
                    return ub
                return lb
                
            if searchValue > target:
                ub = mid
            elif searchValue < target:
                lb = mid
            else:
                return mid
        #print("done", lb, ub)
        assert(lb == ub)
        return lb
Interview Questions

Remove Duplicates from Sorted Array (Leetcode 9)

Leave a comment

This is the warm-up sort of problem to one we’ve seen earlier. The solution is the same spirit.

This is a nice example (finally!) of my drumbeat that a lot of these problems are really reflections of the same “root” problem. While there are still many such root problems, after a while you start to see repetitions, in addition to the shared fundamental material of course.

So we have the same sort of solutions. The first is the C++ algorithm, which is likely “too close to the real problem”. The interviewer would naturally ask “please implement the “unique” function you use there.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto new_end = std::unique(std::begin(nums), std::end(nums));
        return std::distance(std::begin(nums), new_end);
    }
};

So let’s do that in Python. There is probably a similar-enough algorithm, but ironically let’s just do a much more explicit version.

class Solution(object):
    def removeDuplicates(self, nums):
        i = 0
        j = 0
        while i < len(nums):
            nums[j] = nums[i]
            j += 1
            new_i = i + 1
            while new_i < len(nums) and nums[i] == nums[new_i]:
                new_i += 1
            i = new_i
        return j

I actually really like this question. There are multiple ways of solving it. The loops involved here are understandable, but different from the “cliche” for-loops. They also start the idea of having 2 different indices into the same array, a powerful tool that a lot of novice programmers seem pretty surprised by.