In a warehouse robot's floor grid, what plays the role of nodes and edges in a graph?
answer
- Ask what one legal robot step is
- The grid itself is the storage
- Four offsets, one small table
- Bounds check before touching the grid
- Degree at most four: corner 2, interior 4
basics
~20 sEach open cell is a node; an edge joins two cells one step apart, up, down, left or right. No edge list exists anywhere: a direction array plus a bounds-and-blocked check produces a cell's neighbors on demand.
solid answer
~40 sThe nodes are the passable cells, identified by their `(row, col)` coordinates, and there is an edge between two cells whenever a robot can step directly between them. Nobody builds that edge set: you keep a direction array such as `{(-1,0), (1,0), (0,-1), (0,1)}` and a small neighbor routine that adds each offset to the current cell, discards anything outside the floor, discards blocked cells, and returns what is left. That routine *is* the adjacency relation. Interior cells have degree 4, edge cells 3, corners 2, so a fully open R-by-C floor has `2RC - R - C` undirected edges — a number you never need to store, because the grid itself is already the storage. Switching to 8-way movement is a change to the direction array, nothing else.
code
pseudocode · 13 linesDIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
NEIGHBORS(r, c):
result = empty list
for d in 0..3:
nr = r + DIRS[d][0]
nc = c + DIRS[d][1]
if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
continue
if grid[nr][nc] == BLOCKED:
continue
add (nr, nc) to result
return resultgo deeper
Be ready to say, in one breath, that cells are nodes and single steps are edges, and to write the four-offset neighbor routine with its bounds and blocked checks in the right order.
Explain why nothing is stored: the grid already encodes the adjacency, so materializing edges duplicates data. Know the degree pattern and that swapping the direction table is how 8-way or one-way movement is expressed.
Show that you decide what a node is before you write any traversal. Demonstrate widening the node when a badge, battery level or carried load changes which steps are legal, and note where a symmetric assumption would break.
Own the modeling contract itself: one neighbor routine that every consumer shares, so movement rules, blocked-cell semantics and directionality live in exactly one place rather than being re-derived in each feature that walks the floor.
## What makes a graph a graph A graph is a set of nodes plus a rule that says which pairs are joined. Teaching examples usually hand you that rule as stored data — a list of neighbors per node, or a matrix of flags. But storage was never part of the definition. If you can answer "given this thing, what can I reach from it in one step?" with a small computation, you have a graph, and it is called an **implicit graph**: the edges exist mathematically but are never materialized. A warehouse floor is the cleanest example. The floor is a rectangle of cells, some open, some occupied by racking or a charging station. A robot moves one cell at a time in the four orthogonal directions. - **Node** = one passable cell, named by its coordinate pair `(row, col)`. - **Edge** = a legal single step between two cells that are orthogonally adjacent and both passable. - **Neighbor rule** = for each of the four offsets, add it to the current coordinate, reject anything off the floor, reject anything blocked. ## The direction array The four offsets `(-1,0), (1,0), (0,-1), (0,1)` — up, down, left, right — are held in one small table so the neighbor routine is a single loop rather than four copy-pasted branches. That matters for more than tidiness: every later change to the movement model is a change to that one table. Add the four diagonals and you have 8-way movement. Remove two entries and you have a robot that can only move down and right. Attach a cost to each offset and you have a weighted grid where a diagonal step costs about 1.41 rather than 1. Two details in the neighbor routine are load-bearing, not optimizations: 1. **Bounds first, then read the grid.** Reading `grid[nr][nc]` before checking that `nr` and `nc` are inside the floor is the classic crash — or, worse, on some layouts it silently reads the wrong row and the robot appears to teleport across the map. The bounds test is part of the edge definition, so it belongs before the blocked test. 2. **Blocked cells are non-nodes, not zero-degree nodes.** Either modeling works, but be consistent. If you later count nodes, or iterate all states, the difference shows up. ## Degrees and edge counts An interior cell has 4 neighbors, a boundary cell 3, a corner 2. Summing degrees over a fully open R-by-C floor and halving gives `R(C-1) + C(R-1) = 2RC - R - C` undirected edges. For a 1000-by-1000 floor that is a million nodes and roughly two million edges. Materializing them would cost tens of megabytes and a full pass over the floor, to reproduce information the grid already contains — which is exactly why grid problems are the canonical implicit graph. ## When the node is bigger than the cell The most common modeling mistake is assuming the node must be the cell. It is whatever fully describes the situation. If a gate opens only while the robot carries a badge, then arriving at cell `(3,4)` with the badge and without it are genuinely different situations — one can pass the gate, one cannot — so the node is the pair `(cell, carrying badge?)` and the state space is twice the floor. If the robot has a battery level that gates certain aisles, the node grows again. Deciding what belongs in the node is the whole modeling step; once it is right, the traversal is mechanical. Direction is the other axis. A one-way conveyor lane means the neighbor rule is asymmetric: the lane generates a forward neighbor but the reverse step is never produced. A stored symmetric picture would have to be rebuilt; a neighbor routine simply consults the lane's direction. ## The checklist to say out loud When an interviewer hands you a story problem, answer four questions before writing anything: what is a node (the smallest complete description of a situation), what is an edge (one atomic legal action), is the relation directed, and do edges carry weights. A grid answers them so quickly that people forget they were answered at all — which is why the same interviewer will follow up with a version where the node is not the cell.
- How does the model change if some aisles are one-way conveyor lanes?The relation becomes directed. The neighbor routine consults the lane's direction and simply never produces the backward step, so the reverse edge does not exist. Anything that assumed symmetry breaks: a search that wants to walk backward from a destination now needs a separate predecessor routine that inverts the lane rule, rather than reusing the same neighbor routine.
- A gate opens only while the robot carries a badge. What is the node now?The pair `(cell, badge held?)`, not the cell. With the badge and without it are different situations because different steps are legal, so the state space doubles and the same cell can legitimately be occupied twice in one search. Keeping the node as the cell alone is the classic under-modeling bug: the search decides the gate is unreachable or reachable for the wrong reason.
- Why must the bounds test run before reading the cell?Because the bounds test is part of the edge definition, not a speed trick. Off-floor coordinates are not nodes at all, so there is nothing to read. Reading first either faults or, on a flattened layout, silently returns a cell from the neighboring row, producing edges that wrap around the floor and a path the robot cannot physically drive.
The floor plan is the graph. Nobody pins a string between every pair of adjacent tiles; you look at where you are standing and see which four tiles you could step onto.
saying these in an interview costs you the question
- Says a grid is not a graph because no edges are stored
- Builds an explicit edge list before searching a grid
- Reads the cell first, then checks bounds
- Assumes every cell has exactly four neighbors
- Assumes the node must always be just the coordinate pair