Graphs and Grids

Graphs are not a side topic at Databricks, they are the shape of the product. A Spark query compiles into a directed acyclic graph of stages, where each stage waits on the ones it depends on. The Delta table beneath it is a tree of data files and log entries. Underneath both sits a cluster, a set of nodes wired together with real costs on the links between them. So a graph problem in the coding round is the structure the company works in every day. The problems tend to carry that flavor: dependency ordering, region counting, cheapest routes under a constraint.

Three moves cover almost all of it. You flood fill to find connected regions in a grid. You topologically sort to order a DAG by its dependencies. When the edges carry costs and you want the cheapest path, you run a weighted search. The traversal underneath is always breadth-first or depth-first; what changes is the bookkeeping you layer on top. Learn the three skeletons cold and the work in the room becomes choosing the right one and getting the edges and the visited set exact.