Skip to content
Tutorials Center
My learning

Topics

Lesson 45 of 46 ยท Practice and Review

Classical AI Interview Questions

Thirty classical AI interview questions with short answers: agents, A*, heuristics, CSPs, alpha-beta, logic, planning, probability and robotics, with runnable code.

Interviewers for AI, robotics and game-programming roles rarely ask you to recite a definition. They ask a short question, listen to how you reason, and then push with "why?" and "what if the heuristic is not admissible?". This page collects thirty common questions on classical (non-neural) AI, with answers short enough to say out loud in about a minute. Where a few lines of code make an answer concrete, you can run it.

A strong answer has three parts: the fact, the reason and the trade-off. "A* is optimal" is a fact. "A* is optimal when the heuristic never overestimates, because then the first time it removes the goal from the frontier, no cheaper path can still be hiding in the frontier, but it may need exponential memory" is an answer. Use the exercises to practice the calculations and the cheat sheet for a last-minute review.

1. What is a rational agent?

An agent that picks, for each percept sequence, the action expected to maximize its performance measure given what it knows. Rational does not mean omniscient or always successful: it means making the best decision with the available information, including gathering information when that pays off. See agents and environments.

2. What does PEAS stand for and why use it?

Performance measure, Environment, Actuators, Sensors. Writing the four down before coding forces you to say what "good" means and what the agent can perceive and do. Most real failures come from a wrongly specified performance measure, not from the algorithm.

3. How do you classify a task environment?

By asking: fully or partially observable? Deterministic or stochastic? Episodic or sequential? Static or dynamic? Discrete or continuous? Single or multi-agent? Chess is fully observable, deterministic, sequential, static, discrete and has two agents; driving a car is partially observable, stochastic, sequential, dynamic, continuous and multi-agent. The classification tells you which algorithm family to reach for (types of environments).

4. What are the parts of a search problem?

The initial state, the actions available in each state, a transition model giving the result of an action, a goal test and a path cost. The state space is the graph these define. The art of search is choosing a state representation that is small but captures everything that matters (problem formulation).

Tree search may generate the same state over and over, and on a graph with cycles it can loop forever. Graph search keeps an explored set so each state is expanded once, which costs memory but can turn an exponential search into a linear one. Graph search with A* needs a consistent heuristic (or node reopening) to stay optimal (tree and graph search).

6. Compare BFS, DFS, uniform-cost search and iterative deepening.

Algorithm Complete? Optimal? Time Space
BFS Yes (finite branching) Yes if all step costs are equal O(b^d) O(b^d)
DFS No (infinite or cyclic spaces) No O(b^m) O(bm)
Uniform-cost Yes (positive costs) Yes O(b^(1 + C*/ฮต)) same as time
Iterative deepening Yes Yes if step costs are equal O(b^d) O(bd)

Here b is the branching factor, d the depth of the shallowest goal, m the maximum depth, C* the optimal cost and ฮต the smallest step cost. See uninformed search.

7. When would you choose iterative deepening?

When the search space is large, you do not know the depth of the solution and memory is the limit. It has the memory of DFS and the completeness and optimality of BFS, and the repeated work is small: with b = 10 and d = 5 it generates only about 11 percent more nodes than BFS (uniform-cost and iterative deepening).

8. Explain A* in one minute.

A* is best-first search that orders the frontier by f(n) = g(n) + h(n): g is the exact cost from the start to n, and h is a heuristic estimate of the remaining cost. Uniform-cost search looks only at g, so it spreads out in all directions. Greedy search looks only at h, so it rushes toward the goal and can be fooled by walls. A* combines them. If h is admissible (never overestimates), the first time the goal is removed from the frontier its cost is optimal. If h is also consistent, each node is expanded at most once. It stores every generated node, so memory is the bottleneck (A* search).

9. How do A*, Dijkstra and greedy best-first search differ in practice?

Run all three on the same grid and count expansions. The maze puts the goal close in a straight line but far by walking, a trap for greedy search:

Python UCS, greedy and A* on the same maze

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Uniform-cost search (Dijkstra with unit weights) and A* both find the optimal 14 steps, but A* expands 20 nodes instead of 32 because the heuristic prunes directions that lead away from the goal. Greedy search expands about as many nodes as uniform-cost search here, and returns a path of 30 steps, more than twice as long as the optimum: it keeps trying to get closer in a straight line. A* with h = 0 is exactly Dijkstra's algorithm.

10. What is an admissible heuristic and what is a consistent one?

Admissible: h(n) is never greater than the true cost from n to the goal. Consistent (monotone): h(n) <= c(n, n') + h(n') for every edge, a triangle inequality. Consistency implies admissibility (given h(goal) = 0), but not the other way around. Consistent heuristics make f non-decreasing along any path, which is why each node needs expanding only once (admissible heuristics).

11. How do you design a good heuristic?

Relax the problem (remove constraints) and use the exact cost of the easier problem. In the 8-puzzle, allowing a tile to move to any adjacent square, even an occupied one, gives the Manhattan-distance heuristic; allowing it to jump anywhere gives the misplaced-tiles count. Between two admissible heuristics, the larger one dominates: it expands no more nodes. Another source is a pattern database that stores exact costs for a subproblem. See heuristic functions.

12. What do you do when A* runs out of memory?

Trade optimality or time for memory: IDA* repeats depth-first searches with an increasing f limit and uses linear memory; beam search keeps only the best k nodes per level (incomplete); weighted A* uses f = g + wยทh with w > 1 to find a solution faster that costs at most w times the optimum (memory-bounded search).

13. Write a quick solvability check for the 8-puzzle.

Interviewers like this one because it tests whether you see the structure. Half of all arrangements are unreachable. For a 3 by 3 board the puzzle is solvable exactly when the number of inversions (pairs of tiles in the wrong order, ignoring the blank) is even, since every slide changes the inversion count by an even number:

Python Solvability by inversion parity

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Local search and constraint satisfaction

14. What goes wrong with hill climbing and how do you fix it?

It gets stuck on local maxima, plateaus and ridges because it only accepts improvements. Fixes: random restarts, sideways moves, stochastic hill climbing, simulated annealing, or a population method such as a genetic algorithm. The demo climbs a bumpy landscape from 20 random starts:

Python Hill climbing with random restarts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A single run often ends on a small hill (the first start reaches a height of only 1.007), but the best of 20 restarts reaches 2.207, the same as an exhaustive grid search. Restarts work because the cost of one climb is small and different starts reach different hills.

15. Why does simulated annealing sometimes accept worse moves?

To escape local optima. A worse move that lowers the value by ฮ” is accepted with probability exp(-ฮ” / T). At a high temperature T it accepts most moves and wanders; as T is lowered it behaves more and more like hill climbing. With a slow enough cooling schedule it converges to the global optimum with probability 1, but that schedule is too slow to use in practice (annealing and genetic algorithms).

A CSP has variables, domains and constraints. Because the representation is factored, a solver can reason about constraints: it detects dead ends early, propagates the effect of an assignment and uses general heuristics. Generic search treats states as black boxes and cannot do any of this. Map colouring, Sudoku and timetabling are CSPs (CSP formulation).

17. Name the main techniques that make CSP solving fast.

Backtracking search with the most constrained variable first (MRV, then degree), least constraining value first (LCV), and inference: forward checking removes values from neighbours after each assignment, and AC-3 enforces arc consistency across the whole network. Exploiting structure matters too: a tree-structured constraint graph can be solved in linear time, and independent sub-problems can be solved separately (backtracking, propagation).

Games

18. Explain minimax.

Two players alternate: MAX tries to maximize the final utility and MIN tries to minimize it. A depth-first traversal computes the value of a leaf as its utility, of a MAX node as the maximum of its children and of a MIN node as the minimum. It gives optimal play against an optimal opponent for zero-sum, perfect-information games, in O(b^m) time and O(bm) space (games and minimax).

19. Explain alpha-beta pruning in one minute.

Alpha is the best value MAX can already guarantee on the path to the root, and beta is the best value MIN can guarantee. While searching a MIN node, once its value drops to alpha or below, MAX would never choose that node, so the remaining children are skipped; the symmetrical rule applies at MAX nodes with beta. Pruning never changes the result. With the best move ordering it examines about O(b^(m/2)) nodes, so it can search twice as deep in the same time. A small experiment on tic-tac-toe shows the effect:

Python Minimax versus alpha-beta on tic-tac-toe

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both return 0 (a draw with perfect play), but alpha-beta visits 18,297 nodes instead of 549,946, about 3.3 percent, even without any clever move ordering (alpha-beta pruning).

20. What is an evaluation function and what is the horizon effect?

When the tree is too deep to search to the end, you stop at a depth limit and score the position with a heuristic evaluation, usually a weighted sum of features (material, mobility, centre control). The horizon effect is when a bad event just beyond the search depth is invisible, so the program makes delaying moves that only push the problem past its horizon. Quiescence search (keep searching until the position is "quiet") and iterative deepening mitigate it (evaluation functions).

Alpha-beta shines when there is a good evaluation function and a small branching factor (chess). MCTS needs no evaluation function: it grows a tree by repeated simulations, using UCB1 to balance exploring rarely tried moves with exploiting good ones. It copes with huge branching factors (Go) and handles chance and hidden information more naturally. Use expectiminimax when the game has a small number of chance outcomes (MCTS).

Logic

22. What is the difference between implication and entailment?

Implication A -> B is a sentence that is true or false in each model. Entailment KB โŠจ ฮฑ is a relation between sentences: ฮฑ is true in every model in which the KB is true. It is checked by model checking (truth tables) or by inference procedures (propositional logic).

23. What are soundness and completeness of an inference procedure?

Sound: it derives only entailed sentences, so it never proves something false. Complete: it can derive every entailed sentence. Resolution refutation is sound and complete for propositional logic. You need both for a theorem prover that you can trust and that finds all answers.

24. When is forward chaining better than backward chaining?

Both are sound and complete on Horn clauses and run in linear time for propositional logic. Forward chaining is data-driven: it derives everything that follows from the facts, which suits monitoring or when many conclusions are needed. Backward chaining is goal-driven: it works from a query and touches only relevant rules, which suits answering a specific question, and it is the engine of Prolog (resolution and chaining).

25. What is SAT and why does it matter?

Deciding whether a propositional formula has a satisfying assignment. It is NP-complete, yet modern solvers (DPLL with unit propagation, then CDCL with clause learning) handle millions of variables on structured problems, so many planning, verification and scheduling problems are solved by encoding them as SAT (SAT solving).

26. What does first-order logic add and what does it cost?

Objects, relations and quantifiers, so one rule such as "all humans are mortal" replaces a clause per individual. The cost is that entailment is only semi-decidable: a prover can confirm that a sentence is entailed, but may run forever on one that is not. Inference needs unification to match patterns with variables (first-order logic).

Planning, probability and robotics

27. What is classical planning and what is the frame problem?

Planning finds a sequence of actions that turns an initial state into one satisfying a goal, with a deterministic, fully observable world described by STRIPS or PDDL actions (preconditions, add list, delete list). The frame problem is stating what does not change when an action runs. STRIPS sidesteps it with an assumption: everything not on the add or delete list stays the same (classical planning, planning heuristics).

28. Why are Bayesian networks compact?

Because they encode conditional independence. A joint distribution over n binary variables needs 2^n - 1 numbers, but a network where each variable has at most k parents needs only about n ยท 2^k. The joint is the product of each variable's probability given its parents. Exact inference can still be exponential in the worst case, so approximate sampling methods are used on large networks (Bayesian networks).

29. Filtering, smoothing and Viterbi: what is the difference?

All work on a hidden Markov model. Filtering estimates the current state from all observations so far (the forward algorithm). Smoothing estimates a past state using observations from after it too. Viterbi finds the single most likely sequence of states, which is different from picking the most likely state at each step. A Kalman filter is the same idea for continuous states with Gaussian noise, and a particle filter represents the belief with samples (HMMs and filtering).

30. What is an MDP and how do value iteration and policy iteration differ?

A Markov decision process has states, actions, a stochastic transition model, rewards and a discount factor; the solution is a policy mapping states to actions. Value iteration repeatedly applies the Bellman update V(s) = max_a ฮฃ P(s'|s,a)[R + ฮณV(s')] until it converges, then extracts the policy. Policy iteration alternates between evaluating the current policy and improving it, usually in fewer iterations but with a more expensive step. If the state is not observable you have a POMDP, which is much harder (MDPs).

Bonus questions you may get. Forward versus inverse kinematics: forward maps joint angles to the end-effector pose and always has one answer; inverse maps a pose to joint angles and may have zero, one or many solutions (kinematics). Why plan with A on a grid but RRT in a robot arm's configuration space?* The grid has few dimensions and a cheap exact search; a six-joint arm has a continuous six-dimensional space where grids explode, and sampling-based planners such as RRT scale much better (path planning). Why did deep learning overtake classical AI? Hand-written rules and models do not scale to messy perception, but search, planning, logic and probabilistic reasoning remain the right tools wherever you need guarantees, explanations or little data (what is classical AI).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which combination guarantees that A* graph search returns an optimal solution without reopening nodes?

    A consistent heuristic makes f non-decreasing along paths, so the first time a node is expanded its g value is already optimal. Consistency implies admissibility.
  2. 2. In the maze demo, greedy best-first search returned a path of 30 steps while A* returned 14. Why?

    Greedy search orders nodes by h alone. A heuristic that ignores walls can lure it along a long detour. A* adds g, so detours become visible in f.
  3. 3. What does alpha-beta pruning change about minimax?

    Pruning only skips branches that cannot affect the decision at the root, so the minimax value is the same and fewer nodes are examined.
  4. 4. Which statement about hill climbing with random restarts is true?

    Random restarts reduce the chance of ending on a poor local maximum. Accepting worse moves by temperature describes simulated annealing, not restarts.
  5. 5. Why is forward chaining or backward chaining enough for Horn clauses, while general propositional logic needs resolution?

    With at most one positive literal per clause, a rule has a single conclusion and chaining can follow it. General clauses such as 'P or Q' need resolution to be handled completely.

Summary

  • Good answers state the fact, the reason and the trade-off, and name the algorithm's conditions (admissible, consistent, finite, zero-sum).
  • A* orders by g + h; optimal with an admissible heuristic (graph search wants consistency); memory is its weakness, fixed by IDA*, beam search or weighted A*.
  • Heuristics come from relaxing the problem; the larger admissible heuristic dominates.
  • Local search needs a way to escape local maxima: restarts, annealing or populations.
  • CSP solvers combine MRV, LCV, forward checking and AC-3; alpha-beta gives the same value as minimax with far fewer nodes.
  • Entailment, soundness and completeness are the vocabulary of logic; SAT solvers make logic practical.
  • Probability and decision tools (Bayes nets, HMMs, MDPs) and robotics (kinematics, path planning) complete the picture.

Next: Classical AI Cheat Sheet.