Category Archives: Interview Questions

Greedy Algorithm, Interview Questions, Strings

Decimal to Roman Numerals (Leetcode)

A sequel to our previous effort, this time going the other way. That the greedy algorithm works here is not too surprising, but maybe there’s a way of concocting a variant of roman numerals where the greedy algorithm wouldn’t work? It’s basically the change-making algorithm. That it works is intuitive, perhaps, but it feels a bit unstable. If somehow we had to do something like this for production, I’d want to really spend out the time characterizing exactly why this works—why we can recast the whole subtractive thing as just a pile of coins. It’s sort of interesting, I guess…

def trySingleString(num, result, symbol, amount):
    if num >= amount:
        return num - amount, result + symbol
    return num, result


def tryRepeatedString(num, result, symbol, amount):
    while True:
        num2, result2 = trySingleString(num, result, symbol, amount)
        if num2 == num:
            return num, result
        num, result = num2, result2


class Solution:
    def intToRoman(self, num: int) -> str:
        assert num >= 0
        result = ""
        num, result = tryRepeatedString(num, result, "M", 1000)
        num, result = tryRepeatedString(num, result, "CM", 900)
        num, result = tryRepeatedString(num, result, "D", 500)
        num, result = tryRepeatedString(num, result, "CD", 400)
        num, result = tryRepeatedString(num, result, "C", 100)
        num, result = tryRepeatedString(num, result, "XC", 90)
        num, result = tryRepeatedString(num, result, "L", 50)
        num, result = tryRepeatedString(num, result, "XL", 40)
        num, result = tryRepeatedString(num, result, "X", 10)
        num, result = tryRepeatedString(num, result, "IX", 9)
        num, result = tryRepeatedString(num, result, "V", 5)
        num, result = tryRepeatedString(num, result, "IV", 4)
        num, result = tryRepeatedString(num, result, "I", 1)
        return result
Interview Questions, Introductory, Strings

Roman Numerals to Decimal (Leetcode)

This is apparently a popular question. It seems OK, it’s very easy. I think I already knew the rule of subtraction. I suppose questions that prompt the learner to consider “doing the work” of writing out a map is nice.

Maybe there’s something to it with the loop being backwards. What if I did it forwards? Seems like it’d end up in the same place: the condition in the if statement would be a bit different, that’s all.

MAP = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

class Solution:
    def romanToInt(self, s: str) -> int:
        val = 0
        prevC = None
        for c in reversed(s):
            if prevC is not None and MAP[c] < MAP[prevC]:
                val -= MAP[c]
            else:
                val += MAP[c]
            prevC = c
        return val
Linked List

Delete Node in a Linked List (Leetcode)

Another question from the archives. I was loathe to share this because it was an easy (or medium?) question at the time that I really hammered on but could not solve. The description makes it plain there’s not too many options on what to do, but having exhausted everything I could think of, I looked at the answer. It was not something I considered a good practical approach. Let’s discuss.

The Meta-Problem

You have a singly-linked list, and you have a pointer to a node, and you want to delete that node. The challenge is that, naively “blowing away” that object would invalidate the list: presumably there is some prefix that ends with the node you were given, and the node you were given may continue with some suffix.

So ideally you’d have a pointer to the node prior to the one you want to delete. Then you just do node.next = nodex.next.next, up to null-checks and the like. We lack that ability.

Vindication

Having returned to this question many years from now (and to be clear, my notes have the solution I ultimately got from the site), I feel vindicated. As of reading in June 2023, the following paragraph is included:

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean: […]

That clarification was 100% missing in the version I read! I can’t objectively claim I would have gotten it with that clue, but saying delete and not meaning free-the-memory is a pretty weird construction.

So I would bet this question got a lot of feedback. Anyways, the solution is straightforward, it’s more an excuse to have a cute loop over linked lists.

class Solution:
    def deleteNode(self, node):
        prev = None
        while node.next is not None:
            node.val = node.next.val
            prev = node
            node = node.next
        prev.next = None
Introductory, Linked List

Middle of Linked List (Leetcode)

Another warm-up question from the archives.

The editorial solution, fast-and-slow-pointer, is very cute. I’m not sure how it’s preferable over separating the length (“fast”) calculation from the actual-find-calculation (“slow”). We’re doing the same traversals, but presumably with better locality?

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        l = 0
        n = head
        while n is not None:
            n = n.next
            l += 1

        n = head
        for i in range(l//2):
            n = n.next
        
        return n
Interview Questions, Introductory, Musings

Find the Duplicate Number (Leetcode)

This is a reasonable warm-up question I think, but the performance-related requirement (constant space) is silly. Reading the editorial, well, I have thoughts to share. This is from the archives.

Using this as a warm-up question

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        seen = set([])
        for n in nums:
            if n in seen: return n
            seen.add(n)

This presents an approachable-enough setting to discuss performance, and I think things like “find the duplicates” are related to real-world questions. Moreover, there are ready sequels: OK, if they use this “hash table approach”, what about one that can take more time, but less space?

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        prev = None
        for n in sorted(nums):
            if prev is None:
                prev = n
            elif prev == n:
                return n
            prev = n

Considering The Leetcode Discussion

The leetcode “editorial” (at least as of June 2023) presents 7 different approaches for the problem. Here are some of my reactions to the editorial. This is my experimental foray into providing a criticism to, what I think is the typical leetcode perspective on questions. I’m not meaning to pick on this particular question.

  • “[The problem] is a classic problem” — I’m not sure in what domain this question is a classic. Deduplication in general is very useful, but the particular of this question don’t strike me as something classic. Maybe it’s a common interview question for a certain company? I wish leetcode questions placed their evaluations in more context. It gives the air of secret knowledge (“oh, this is a classic question, and I didn’t know that!”) when I think they’re just… making things up.
  • Approach 3, in which they borrow a bit from each element in the array (and use the range-trick) they say is O(1) space. In practical terms, sure, but what if the array is, say, unsigned shorts and the size of 2^16? You have no bits to borrow; that’s just an example where this is sort of “punning” between theoretical concerns (asymptotic analysis of resource usage) versus practical concerns. Both are fine, but mixing them leads to confusion.
  • The other approaches are fun things to learn, but all (including approach 3) really rely on the particular structure of the input. It’s just unsatisfying.
Graphs, Interview Questions

Island Perimeter (Leetcode)

This is a nice application of DFS. I think this is a good question that exercises a few things. Briefly, the question is “given a grid, find the perimeter of the unique island”. To me the natural approach feels like, find the island, and then do a DFS exploration to touch its perimeter.

  • From a pedagogical standpoint, I think it’s nice that it uses DFS, and “stretches” its application. In the [[1, 1], [1, 1]] example it made it clear that I couldn’t “double-count” any nodes!
  • From an interview standpoint, it’s a nice mapping of intuitive(-enough) requirements to code.
  • As always it’s a bit contrived, but I like questions where you have to synthesize higher-level data from smaller parts. I think that’s a good theme.

Solution, and detailed discussion, below

Solution

class Solution:
    def findLand(self, grid: List[List[int]]):
        for i, row in enumerate(grid):
            for j, cell in enumerate(row):
                if cell == 1:
                    return (i, j)
        return (-1, -1) # error state

    def islandPerimeter(self, grid: List[List[int]]) -> int:
        startLoc = self.findLand(grid)
        assert(startLoc[0] != -1)

        p = 0
        # DFS
        seen = set([])
        willProcess = set([startLoc])
        workList = [startLoc]
        while workList:
            i, j = workList.pop()
            for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
                # case 1: we know there cannot be a neighbor (edge of map) or water!
                if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[x]) or grid[x][y] == 0:
                    p += 1
                    continue
                # case 2: it's a neighbor we've seen:
                if (x, y) in seen:
                    continue
                # case 3: a new node to explore!
                if (x, y) not in willProcess:
                    willProcess.add((x, y))
                    workList.append((x, y))
            seen.add((i, j))
        return p

Discussion

  • There’s some redundancy with “willProcess” and “seen”. I think I can get rid of “seen”?
  • I make ready use of a lot of the conveniences of Python. Generating the list as the expression (in the for x, y in … loop), nevermind the ability to decompose those tuples, is really nice for these interviewing questions.
  • Implicit in the code is sort of 2 layers: there’s the “straight” DFS, i.e., case 3, and then there’s also the “when I’m at a node, how does it contribute to the perimeter calculation”? Something in my mind, but not explicitly listed out, is that we process each node exactly once, and then we know that the node will contribute between 0 and 4 to the perimeter (depending on the 4 neighbors we check.
  • I feel like it is crucial we don’t have lakes, as noted in the problem, but I can’t quite articulate why. Something to consider if/when I revisit this problem.

I like this! It touches on both matrix and graph problems (mainly graph problems) and hits a lot of “right notes”. More graph problems here.

Graphs, Interview Questions

Clone Graph (Leetcode)

What can I say, I like graphs. This problem is from the archives, but I think especially from a pedagogical standpoint these “copy the data structure” (or usually I like, “print the data structure”) are terrific educational exercises.

The approach I took for this problem is the commented helper function. I think I need to review DFS/BFS and make sure I’m using the right number of node-marking (typically I’ve seen it formulated as a node being “marked” done or workset, rather than added to a set — that is more efficient generally.

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None

        # We want to provide a function to get the
        # "corresponding" node, allocating it if needed.
        cor = {}
        def getCor(u):
            if u not in cor:
                cor[u] = Node(u.val)
            return cor[u]

        workset = set([])
        done = set([])
        workset.add(node)
        while len(workset) > 0:
            n = workset.pop()
            if n in done:
                continue
            m = getCor(n)
            for u in n.neighbors:
                v = getCor(u)
                m.neighbors.append(v)
                if u not in done:
                    if u not in workset:
                        workset.add(u)
            done.add(n)

        return getCor(node)

Notes

  • All graph problems (rare) are collected here.
Interview Questions, Strings

Unique Morse Code Words (Leetcode)

Another from the archives. I had too much fun with this python approach. A nice introductory string question.

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        mapping = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        def mapIndex(c):
            return ord(c) - ord('a')
        def mapWord(w):
            return ''.join(map(lambda c: mapping[mapIndex(c)], w))
        return len(set(list(map(mapWord, words))))

This is a fine introductory interview question. The exact motivation isn’t great, but “process this data and count unique ones” is fine. More strings — a popular request from my students — here.

Interview Questions, Strings

Longest Substring Without Repeating Characters (Leetcode)

Another from the archives. In my old notes I tried a few different approaches. Ultimately this one feels a little “brute-force-y”, here is what I got:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int l = std::max(res, 1); l + i <= s.size(); l++) {
                std::bitset<256> seen;
                bool bad = false;
                for (int j = i; j < i + l; j++) {
                    if (seen.test(s[j])) {
                        bad = true;
                        break;
                    }
                    seen.set(s[j]);
                }
                if (!bad) {
                    res = std::max(res, l);
                } else {
                    // i i our starting point, a longer l won't help here.
                    break;
                }
            }
        }
        return res;
    }
};

Thoughts

  1. The “length” iteration (how i, l, j indexes interact) is pretty interesting. Comes up rarely, but in thinking about many collections of substrings.
  2. The final “break” (with the comment above it) is necessary.
  3. I wanted to port this to Python—my old archives are in C++. But it lacks a bitset class, and its range loops aren’t amenable to the length-based iteration (or at least, I don’t know how to adapt them).

I doubt my solution is the right one. What is the official Leetcode solution? Oh I like it! Does this make the cut as an interview question? I don’t know, I am skeptical. More string questions here.