Category Archives: Interview Questions

Binary Search, Interview Questions

Peak Index Mountain Array (Leetcode 23)

Another from the archives! (Can you tell I’m going through old notes?)

This one strikes me as an interesting exercise exploring that common hurdle of mixing up array-indexes and array-values. This is a nontrivial “array search” problem.

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        for i in range(1, len(arr)-1):
            if arr[i] > arr[i-1] and arr[i] > arr[i+1]:
                return i

Apparently, however, we’re obliged to use binary search and find it in log(N) time. The idea there is you check your index “locally”, and move right or left depending on which way the mountain says is “up”.

Interview Questions

Hamming Distance (Leetcode 22)

This is another question and solution from the archive. I think this is a nice educational question, but not a great interview question. It’s an OK interview question. I tagged this “vocabulary” because Hamming distance, and the tools (that I think are) the right ones to solve this are less things you gain insight about over time, and instead things you learn. Some observations:

  1. The final punchline involves the XOR operator (^), which can be understood in a few ways. One way is seeing it as a symmetric-difference operator (or something like that), where the two integers are bitsets. So the result is a third bitset, that contains all those elements that were in exactly 1 of the two original bitsets. This sounds like what we want!
  2. The missing piece is being able to count the 1s in that resulting set. The vocab to use here is “popcount”, which is either a hardware instruction or — if you’d like — a simple enough loop.
class Solution {
public:
    int popcount(int x) {
        int count = 0;
        while (x) {
            if (x % 2) {
                count++;
            }
            x >>= 1;
        }
        return count;
    }
    int hammingDistance(int x, int y) {
        return popcount(x^y);
    }
};
Interview Questions, Linked List

Add Two Numbers (Leetcode 21)

This is from the archives, when I’d take more notes. Let me take those insights and preserve them here.

Despite the name, this question is really about linked lists. I’ll assume you’ve read the question and understood it. Now, a few observations:

  1. We get to iterate through the list in the “nice” way: we can start adding digits immediately.
  2. Built into the question is the problem of “carries” — we’re adding things, but each node can only hold the values 0-9, and so if there’s overflow we have to carry that.
  3. This is a linked-list-merge-style question (see featured post here), so we should be mindful of the “end” of each of our two linked lists and how we should handle them. A moment’s thought also suggests that the carry value can also play a role here!
  4. No negative numbers! The natural approach doesn’t suggest we’d introduce an erroneous leading zero or anything either. So it doesn’t seem there’s anything too tricky here.

Some insights:

  1. We can treat the carry value as a “virtual” node: this tightens up our iterations and puts everything into one loop.
  2. The approach I took was to create a new, third list. Another option (in practice; I assume the autograder would accept this too) would be to make this transformation destructive of one or both lists.
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* lastDigit = nullptr;
        ListNode* result = nullptr;
        bool carry = false;
        
        while (l1 || l2 || carry) {
            auto l1val = l1 ? l1->val : 0;
            auto l2val = l2 ? l2->val : 0;
            auto nextVal = l1val + l2val;
            
            if (carry) {
                nextVal++;
                carry = false;
            }
            
            if (nextVal > 9) {
                nextVal -= 10;
                carry = true;
                // assert(nextVal < 10 && nextVal >= 0)
            }
            
            if (!result) {
                result = new ListNode(nextVal);
                lastDigit = result;
            } else {
                lastDigit->next = new ListNode(nextVal);
                lastDigit = lastDigit->next;
            }
            
            if (l1) { l1 = l1->next; }
            if (l2) { l2 = l2->next; }
        }
        
        return result;
    }
};

I think this is a nice interview question.

Interview Questions

Pre/In/Post-Order Tree Traversal (Leetcode 20)

These don’t need to be 3 different questions. The vocabulary (knowing what pre, in, post means) is nice, and the questions follows what I see as the “typical” recursive tree-problem skeleton.

The first one is how I think it should be solved (albeit recursively). If memory serves, doing it iteratively for infix is a bit interesting. The other two example solutions are very terse.

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None: return []
        prefix = self.preorderTraversal(root.left)
        suffix = self.preorderTraversal(root.right)
        return [root.val] + prefix + suffix
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)V
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None: return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
Interview Questions

Tree to list (Code Wars 21)

Breadth-first search! Of an arbitrary (not necessarily binary) tree. Glad to have this one. At least in the python implementation it’s weird that they model null as [], it should be None, but whatever.

def tree_to_list(tree_root):
    res = []
    worklist = [tree_root]
    while worklist:
        n = worklist[0]
        worklist = worklist[1:]
        if n == []:
            continue
        res.append(n.data)
        for c in n.child_nodes:
            worklist.append(c)
    return res