Category Archives: Graphs

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.
Graphs, Interview Questions

Network Delay Time (Leetcode)

This is a classic algorithm, and from the archive! It is just Dijkstra’s algorithm, and in fact this sort of formulation is exactly how my undergrad algorithms professor tried to have us develop the intuition of how it worked. I appreciate that this formulation at least suggests something of an approachable motivation, measuring network latency and similar.

class Solution(object):
    def networkDelayTime(self, times, n, k):
        # Cache neighbors and their weights
        neighbors = {u : [] for u, _, _ in times}
        for u, v, w in times:
            neighbors[u].append((v, w))
            
        # Djikstra's
        worklist = [k]
        cost = {k: 0} # cost to reach k
        while worklist:
            u = worklist.pop()
            c = cost[u]
            if u not in neighbors:
                continue # its a sink
            for v, w in neighbors[u]:
                if v not in cost or cost[v] > w + c:
                    cost[v] = w + c
                    worklist.append(v)
        
        # Return requested result
        if len(cost) != n:
            return -1
        return max(cost.values())

Discussion

This was originally “easy” on Leetcode, according to my notes. I think with some thought this can be an approachable, or independently derivable algorithm. (A different professor I had pointed to Dijkstra as an advantage of being early on in a new field: if you are, you can name all the “obvious” results after yourself!) I wouldn’t say this is an obvious algorithm, but the idea that you “update your neighbors” when you receive new information is something that is worth getting a measurement on, interview-ish speaking.

Glad to finally get another graph algorithm on the books. The others are here.

Graphs, Interview Questions

Is Graph Bipartite? (Leetcode)

Another classic question, and another from the archives. This one’s nice enough where I took a stab at it in Python for readability.

class Solution(object):
    def isBipartite(self, graph):
        color = {}
        wl = []
        for x, ns in enumerate(graph):
            if x in color: continue
            wl = [x]
            color[x] = 1
            while wl:
                u = wl.pop()
                for w in graph[u]:
                    if w in color and color[w] == color[u]: return False
                    if w not in color:
                        color[w] = 1 - color[u]
                        wl.append(w)
        return True

Thoughts

  • The 1 - color[u] trick is handy. It’s a quick way to have 2 options, sort of like not‘ing a boolean variable. Something to teach new people.
  • I think there is the possibility that many of the same node is added to wl. I think I need another seen set to make sure we’re not iterating too often. Well, it passed.
  • The outermost loop is always a bit annoying: it’d be nice to promise that the graph is always connected. It’s good to know how to handle that situation, so I suppose that’s OK.
  • The term color here is because a bipartite graph is the same as a 2-colorable graph. Graph-coloring is a core combinatoric question. This solution overall follows from the observation that “if U is on the left, then all neighbors of U must be on the right, and vice-versa”. Instead of left/right, we use 2 colors (which in this case are… integers).
  • This is basically an extension of DFS. There is probably an opportunity for more cleverness.

Finally, a graph algorithm! More to come, I imagine. They’re all collected here.