Category Archives: Interview Questions

Interview Questions

Neovim Rant 1

Getting Python Autocomplete

I use python to help collect some high-level commands, such as in my SAT solver. I’ve said previously that I don’t want to use nvim as an IDE, but I do want lots of nice features. (So by “not an IDE” I mean not really do much for file-exploring, git(hub) integration, etc: the tools are only to help edit text, leaving other more focused tools to do their thing.)

There’s syntax highlighting, linting, autoformatting, and autocomplete stuff. To my mind these are just examples of supporting a language, but apparently in nvim they’re all sort of different components. I followed along this nice video to get started (in a lot of ways; the language support is later, and to be clear I recommend this video a lot) but the pieces involved get a bit silly. As I get more plugged into the nvim world maybe this will feel better, but until then…

  1. I had to choose a plugin manager. Apparently lazy is the new hotness, though the purported lazy-loading seems never to be used?
  2. NVim supports the LSP, which is the root of all this functionality, but apparently there’s also a separate plugin you need to “really” use it?
  3. My impression is that NVim is an LSP client, but you still need per-language servers, which are separate executables (!, but fine…) for which you need another layer of package-manager-recursion: Mason.
  4. For auto-formatting (which is nice) one recommends this server, which is integrated with this plugin.
  5. Using pyright apparently required some treesitter stuff (a dimension to all this I haven’t really explored!), which ultimately meant I had to download and install npm, and futz with my path, and then I think everything sort of worked.
  6. Well I needed to do something with nvm-cmp too.

I think there were a few more steps, but I hope this speaks to the number of discrete components I had to futz with. I see the appeal of pre-made distributions like LazyVim.

Can This Be Easier?

I have some familiarity with implementing language tooling. I’m reasonably confident with what’s happening here: people have managed to factor the “incremental-compilation” aspect of IDEs into this LSP language, and that allows for modularity: any language developer can implement an LSP server and it can provide some amount of information to clients. The functionality to consume that information is itself separate: so far it seems like theres’: [LanguageServer]->[Client(Neovim)]->[Tool(AutoComplete plugin)] or something. I suppose this allows users to, e.g., define their own hotkeys for the single autocomplete tool, and have that intelligently consume the LSP information for any language, which is neat.

I believe that the components here have a reasoning behind them, but I think their presentation would be better served by having a few minutes saying why this is the way it is (versus, say, a Python plugin that has all the options you want, a C++ plugin that has all the options you want, etc…). Having to go to 3 different plugins or whatever, and manually install third-party tools (even if there’s a plugin that does that installation for you!) is, to my mind, not ideal.

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.