Sigh, failure is never fun, and it’s never easy. I thought I had a winning strategy for solving LC questions. But when faced with a brand-new problem, I failed.
Today it occurred in my (unamed-company).dev interview:
The problem given was your typical DFS iteration (an easy one, in fact)
# Mountain Rainfall
# Overview
# We want to write a program that determines the
# collection points of rain falling on mountainous terrain.
# One centimeter of rain falls uniformly across a mountain.
# Water flows downhill until it reaches a local minimum.
# Steepest descent, ties break in any way
# Input Specification
# You receive a 2-dimensional array of integers. The integer
# at position (x,y) in the array represents the elevation
# (in kilometers) of the terrain at position (x,y).
# Sample Input:
# [
# [3, 3, 1, -1],
# [2, 3, 3, 1],
# [0, 1, 3, 3]
# ]
# Sample output:
# [
# [0, 0, 0, 6],
# [0, 0, 0, 0],
# [6, 0, 0, 0]
# ]
# [
# [0, 0, 1, 3],
# [1, 0, 0, 1],
# [0, 2, 0, 0]
# ]
# OR
# [
# [0, 0, 0, 7],
# [0, 0, 0, 0],
# [5, 0, 0, 0]
# ]During the interview I did the following breakdown using my strategy:
# Metric
# * Locations at which the water falls
# * The amount of water that falls there
# Constraints
# * If we have a lower location next to it, the water would fall that way
# Simplify Scope
# * [0,0] -> [1,0] -> [2,0]
# *
# * Increment value on a different grid
# Comment Approach
# For a single cellBut after bumbling around for quite a while, the interviewer had to step in and give me some pretty big hints. To diagnose what went wrong, I asked Claude to analyze the transcript and my code.
It seems that I was having two competing ideas in my head:
- We should do DFS on each node and see where it flows.
- We could see where the water flows out of this cell and accumulate it to the next cell. At that next cell we can move all water together.
Unfortunately, the latter makes the implementation way more complex due to state management and code complexity.
Diagnosis
So what went wrong, and why didn’t I stick with the simple DFS solution? Well, first off, I didn’t really do my metric and constraints justice.
Here’s what it should have looked like:
#Metric:
# * Sum of all the water that ends up at each location
#Constraints
# * Water falls on every cell so water needs to flow down from each cell
# * Water will always flow down the steepest part
#Simplify:
# * for a single cell how do we figure out where it goes?
# * It will fall to the minimum spot
# * How do we know if it is the minimum spot? If there are no spots with lower elevation around it
# Pseudocode
# * for each cell:
# * minimum_spot = find_minimum(cell)
# * Minimum_spot += 1
# * find_minimum(cell):
# * set lowest = cell
# * for this cell check all neighbors
# * if out of bounds continue
# * if level >= cell_level: continue
# * if lower:
# * * Find the lowest of the valid
# * if lowest != cell:
# * return find_minimum(lowest)
# * else:
# return cellCode Implementation
# For each item in the grid
dirs = [[1,0], [-1,0],[0,1],[0,-1]]
def flowing_water(grid):
def find_minimum(r,c):
# for this item, check to find the minimum neighbor less than it
steepest_index = (r,c)
steepest_value = grid[r][c]
for dr,dc in dirs:
# If not in bounds return
if (r + dr < 0 or
r + dr >= len(grid) or
c + dc >= len(grid[0]) or
c + dc < 0):
continue
# if value at location is not lesser
if grid[r+dr][c+dc] >= grid[r][c]:
continue
# Find the steepest of the remaining
if grid[r+dr][c+dc] < steepest_value:
steepest_value = grid[r+dr][c+dc]
steepest_index = (r+dr,c+dc)
# dfs on that minimum neighbor if
if steepest_index != (r,c):
return find_minimum(steepest_index[0], steepest_index[1])
# If no neighbors like this then we return the current value
return r,c
flow = [[0] * len(grid[0]) for _ in range(len(grid))]
for r in range(len(grid)):
for c in range(len(grid[0])):
minimum_r, minimum_c = find_minimum(r,c)
flow[minimum_r][minimum_c] += 1
return flow
grid = [
[3, 3, 1, -1],
[2, 3, 3, 1],
[0, 1, 3, 3] ]
print(flowing_water(grid))The key things I missed were:
- Each spot gets rain, so we would need to track where that rain would go.
- Writing out my pseudocode and being able to map it to the parts of my code.
😔
This hurts more because this time around I did sit down and grind, and I did care about the company.
Yet when the time came, I fumbled the opportunity. It sucks because I don’t even know if I can run this process on a new problem either. Every time I run it on a problem I’ve already seen, I have no idea if it feels easy because I’m pattern matching or I’m actually learning the process. Practicing on LC so far doesn’t seem to help because I often end up pattern matching and skipping the pseudocode part.
On top of that, I’ve been on this interview grind for about a month at this point and I’m still failing first rounds. As someone who should be “Senior” it’s so demoralizing. It doesn’t help that the latest advances in AI seem to indicate that all this work I’m doing to upskill myself will become obsolete in the next 2-3 years anyways.
Well ok, no point in thinking about how I’m cooked anyways. It’s time for me to try and apply this to a new problem and see if it actually works.
Practice Problem
https://neetcode.io/problems/pacific-atlantic-water-flow/question?list=neetcode150
#Metric:
# * Find all cells that can flow to both pacific and atlantic
# -> Find all cells that have a path to (top or left edge) and (bottom and right edge)
# Constraints:
# * Water can only flow to spots equal or lesser
# Simplify:
# * For a cell can it flow to both?
# * Does this cell reach both?
# * yes? then we can add this cell to a set of good cells
# * else:
# * are there any cells less than or equal to it?
# * Have we visited this cell before?
# If we have and it is in good cells we can add our current cell to good cells
# * If we haven't visited it before:
# * We can check by running this check on it
# * also add it to visited
# * If this value returns true then we can mark our current cell as good as well
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
ROWS, COLS = len(heights), len(heights[0])
pacific = set()
atlantic = set()
dirs = [[1,0],[0,1],[-1,0],[0,-1]]
def dfs(r,c):
visited.add((r,c))
if (r == 0) or (c == 0):
pacific.add((r,c))
if (r == ROWS - 1) or (c == COLS - 1):
atlantic.add((r,c))
for dr,dc in dirs:
#Borders
if (r+dr < 0 or
r+dr >= ROWS or
c+dc < 0 or
c+ dc >= COLS):
continue
#Lesser
elif heights[r+dr][c+dc] > heights[r][c]:
continue
else:
if (r+dr,c+dc) not in visited:
dfs(r+dr, c+dc)
if (r+dr,c+dc) in pacific:
pacific.add((r,c))
if (r+dr,c+dc) in atlantic:
atlantic.add((r,c))
# visited = [(0,2), (0,3), (1,2), (1,3)]
# pacific = [(0,3), (1,3)]
# atlantic = [(1,4)]
# r,c = (0,2)
visited = set()
for r in range(ROWS):
for c in range(COLS):
if (r,c) not in visited:
dfs(r,c)
both = []
for x in pacific:
if x in atlantic:
both.append(x)
return bothPost-Mortem
OK, so this took me 42 minutes, and I still didn’t do it right. For example, I still had some points where my pseudocode was too vague:
# * Does this cell reach both?What does it mean to reach both? I didn’t define this early on and it led me to assume that we only needed one set instead of a pacific and atlantic set. Luckily I caught it when tracing, but it would have been much faster to catch this in the beginning.
# then we can add this cell to a set of good cellsWithout defining what good cells actually look like it becomes less clear how to actually define this in the code itself.
Claude’s PseudoCode was as follows:
# Data structures: pacific set, atlantic set, visited set
# Base cases: if cell is on top/left edge -> add to pacific
# if cell is on bottom/right edge -> add to atlantic
# For each neighbor <= current cell:
# if not visited: dfs on it
# if neighbor in pacific: add current to pacific
# if neighbor in atlantic: add current to atlantic
# Return intersection of pacific and atlanticThe key differences seem to be:
- concrete definitions of data structures
- definitions of base cases
- content is written as direct code translation rather than English
Well this post is getting long enough, so I’ll do my last practice on my own.