Tag Archives: good interview question

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

Isomorphic Strings (Leetcode 28)

I like this one a lot! Also from the archives. This one is listed as easy, I would say it’s on the harder side of easy. The word “isomorphism” is a bit gnarly, but you can ignore that. I’d rather this be introduced as a Caesar cipher, but maybe that’s also confusing, or makes the possible answer too clear. But if the question is “are you comfortable talking about isomorphism”, well, that’s not a very good question. So I suppose I’d phrase this as a Caesar cipher.

The interesting challenge is, well, distinguish an isomorphism from a homomorphism. Vaguely, the idea of distinguishing this “uniqueness” (invertibility) property is nice. Maybe to enable something like dictionary encoding? I’m trying to brainstorm how to motivate this question and give it some application-justification. In any case…

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # Easy cases
        if len(s) != len(t):
            return False
        
        mapping = {}
        mapped = set([])
        for i in range(len(s)):
            sc = s[i]
            tc = t[i]
            if sc in mapping:
                if mapping[sc] != tc:
                    return False
            elif tc in mapped:
                # uniqueness condition
                return False
            else:
                mapping[sc] = tc
                mapped.add(tc)
        return True
Interview Questions, Strings

Group Anagrams (Leetcode 27)

Another from the archive. This is a nice warm-up or introductory interview question. It is a bit contrived, but I think it exercises a few common tools you’d want to use. You want to group things together that share a common property, and so you want to compare the property but group the things-actual.

Here I use defaultdict, but that’s just out of convenience. I don’t like how to create a sorted string in Python, I wonder if there’s a better way.

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        d = defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            d[key].append(s)
            
        res = []
        for k in d:
            res.append(d[k])
        return res