Micro-questions over the state-space search module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The collection that does not exist
1. How does “search” here differ from searching a sorted array?
Answer
The array existed — you could print it. Here there is no list of board positions: only a starting state, a rule for what is one move away, and a test for being finished.
2. How large are the 8-puzzle and 15-puzzle state spaces?
Answer
181,440 reachable configurations and about respectively. Nobody is building that list.
3. State the key reframing.
Answer
The data structure being searched is generated by the search itself — an implicit graph with vertices and edges and all the usual properties, existing only as a function.
4. What follows once you see it that way?
Answer
The algorithms you already know turn out to be the complete answer — and the only thing separating them is what container holds the states waiting to be looked at.
B. The vocabulary
5. What is a state, and what property must it have?
Answer
A complete description of one configuration, containing everything needed to decide what happens next. It must be hashable if you want duplicate detection — hence tuples rather than lists.
6. What is the successor function?
Answer
Also the transition model or move generator — the function returning every state reachable in one step. It is the edge list of the implicit graph, computed on demand.
7. What is the goal test, and what is the subtlety?
Answer
A predicate deciding whether a state is a solution. It is a test, not a known state — “checkmate” describes a huge family of boards, not one board.
8. What is the frontier, and why is it the most useful fact in the lesson?
Answer
The states discovered but not yet expanded. Which container you use for it decides which algorithm you are running.
9. What is the explored set?
Answer
Also closed/visited — the states already expanded, kept so you never process one twice.
10. Tree search versus graph search?
Answer
Tree search has no explored set — every route to a state is a separate discovery. Graph search has one, so each state is expanded at most once.
11. What are and , and what do they give together?
Answer
Branching factor (average successors — 2–4 for the 8-puzzle, ~35 for chess) and solution depth. Together they give the size of the search: roughly nodes.
12. Define complete and optimal.
Answer
Complete: guaranteed to find a solution if one exists. Optimal: guaranteed to find the cheapest one. DFS on an infinite space is not complete, and is not optimal for anything.
C. The one function
13. What varies between the five algorithms?
Answer
Only frontier.pop(). The explored set, goal test, successor expansion and reconstruction are identical.
14. Give the frontier → algorithm table.
Answer
| Frontier | Pops | Algorithm | Optimal? |
|---|---|---|---|
| stack (LIFO) | most recent | DFS | no |
| queue (FIFO) | earliest | BFS | yes, uniform costs |
| min-heap on | cheapest so far | uniform-cost / Dijkstra | yes, any costs |
| min-heap on | most promising | greedy best-first | no |
| min-heap on | best estimated total | A* | yes, if admissible |
15. DFS returned a 49,285-move solution to a puzzle three moves from solved. Is it broken?
Answer
No — it is doing exactly what it promises, which is to find a solution. It found one by wandering most of the state space. That gap between “a solution” and “the solution” is what the whole table is about.
D. Uninformed versus informed
16. Which algorithms are uninformed, and what does that mean?
Answer
DFS, BFS and uniform-cost — they use nothing but the structure of the space. A* and greedy are informed: they use a heuristic estimate of distance remaining.
17. On the hardest 8-puzzle (31 moves), why did BFS expand 181,439 states?
Answer
The entire reachable space. To prove a 31-move solution is shortest, it had to rule out every shorter one.
18. What did A* achieve on the same instance?
Answer
The same optimal answer from 20,291 expansions — a ninth of the work. The heuristic is the entire difference.
19. What did greedy best-first achieve?
Answer
100 expansions and a 47-move path — 200× faster and 52% worse. That is the trade when you stop counting the cost already paid.
20. Compare zero, misplaced-tiles and Manhattan heuristics.
Answer
All optimal (all admissible); expansions 181,439 / 143,840 / 20,291. Manhattan does 7× less work than misplaced-tiles, which barely beats nothing.
21. Why does Manhattan dominate misplaced-tiles?
Answer
For every state its estimate is at least as large — a tile out of place contributes at least 1 to both, usually more to Manhattan. A larger admissible heuristic is closer to the truth, prunes more, and never expands more nodes.
22. State the design goal for a heuristic.
Answer
Get as large as you can without ever exceeding the true remaining cost.
23. Where do both heuristics come from?
Answer
The standard recipe — solve a relaxed version exactly. Misplaced-tiles solves “a tile can teleport anywhere in one move”; Manhattan solves “tiles can pass through each other”. Both relaxations are easier, so their answers can never exceed the real one.
E. Tree versus graph search
24. The 8-puzzle space is finite, so tree search must terminate. How much extra does dropping the explored set cost?
Answer
1.2× at depth 2, 60× at depth 10, and still climbing.
25. Why, exactly?
Answer
The state space is finite, but the search tree is not. Slide a tile left then back: tree search sees a brand-new node two levels deeper. Every round trip spawns a whole new subtree, and round trips grow exponentially with depth.
26. State the bounds.
Answer
Graph search is bounded by the number of states, 181,440. Tree search is bounded by nothing. With a stack instead of a queue it does not terminate at all.
27. Give the practical rule and its exceptions.
Answer
If a state can be reached by more than one route — almost always — you need an explored set. Exceptions: genuine trees (backtracking over decision sequences) and cases where memory forbids it.
F. Iterative deepening
28. What problem does it solve, and how?
Answer
Storing every state is memory, and memory usually runs out before time does. IDS runs depth-limited DFS with the limit rising from 0.
29. Why is the re-exploration not as wasteful as it sounds?
Answer
With branching factor , the last level holds a fraction of all nodes, so everything above it adds only a constant factor — about 11% extra for .
30. What is the trade?
Answer
Memory drops from to , and you still get BFS’s optimal answer.
31. What is IDA*?
Answer
The same trick applied to A* — bounding on instead of depth.
G. Tie-breaking
32. Why do plateaus happen, and what do they cost?
Answer
Many states share the same priority, so the comparison is a coin flip and the search has no reason to prefer any of them. How you break the tie decides whether the search drives toward the goal or spreads sideways.
33. Give the three standard rules.
Answer
- Prefer larger among equal — equivalently smaller .
- Prefer the more recently discovered state — depth-first-ish within a plateau.
- Add a tiny multiple of (scale by ) — biases toward the goal at bounded optimality cost.
H. Modelling
34. What is the real work, and what is an interviewer usually testing?
Answer
Turning a vague problem into states and successors. The algorithms are a table lookup.
35. Give the five modelling questions.
Answer
- What is a state? The minimum information determining what happens next.
- What are the moves? One deterministic, complete successor function.
- What is the goal test? Often a property rather than a specific state.
- What does a move cost? Equal → BFS; varying → uniform-cost; estimable remaining → A*.
- Is the space finite? If not, DFS is off the table.
36. What goes wrong if the state carries too much? Too little?
Answer
Too much: identical situations look different, defeating duplicate detection. Too little: the successor function cannot do its job.
37. Model the word ladder and regex matching.
Answer
Word ladder: state = current word; successors = words one letter away; goal = equals target.
Regex matching: state = (pattern index, text index); successors = consume a character or not; goal = both indices at the end.
38. Why are dependency resolution and regex matching the ones worth noticing?
Answer
Neither looks like a search problem until you name the state — and then the whole catalogue becomes available.
I. Traps
39. What happens if you use an unhashable state?
Answer
A Python list cannot go in a set, so duplicate detection silently becomes impossible. Use tuples, frozensets, or a canonical string.
40. Why must the state not carry a step counter or timestamp?
Answer
Two identical boards compare unequal and the explored set stops working. The state is the minimum that determines the future.
41. When is goal-testing on push safe, and when is it a bug?
Answer
Safe for BFS with uniform costs. A bug for uniform-cost and A*: the first discovery may be via an expensive route, while the first expansion is guaranteed cheapest.
42. What is the solvability trap?
Answer
Half of all 8-puzzle configurations are unreachable from the goal — the permutation parity is invariant under legal moves. A search for one explores all 181,440 states and correctly reports failure, after doing the maximum possible work. Check solvability first when the problem has such an invariant.
43. Summarise the lesson in one sentence.
Answer
Name the state and the successor function and the problem becomes a graph you never build — after which the only decisions left are what the frontier is and how good your heuristic is.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- State-Space Search — the module
- A\* — Question Bank
- Backtracking — the genuine-tree case
Software engineering
Infrastructure & security
Computer science
Hardware & engineering