CORE JOBS
Artificial Intelligence interview questions
Short answers on the fundamentals, for the technical round of core-job interviews. 22 questions for DS & AI students; the numericals show the working.
Companies do not publish their interview questions; these are ours.
Search
Search notesHow does breadth-first search work, and when is it complete and optimal?
Breadth-first search expands the shallowest unexpanded node first, using a FIFO queue. It is complete when the branching factor is finite, and optimal when every step costs the same. Its time and memory both grow as for a goal at depth .
What is the difference between depth-first and breadth-first search in memory use and completeness?
Depth-first search keeps only the current path and the unexpanded siblings along it, about memory for branching factor and maximum depth , while breadth-first search stores a whole level, for a shallowest goal at depth . Breadth-first search is complete when is finite. Depth-first search is not: it can descend an infinite path forever, and in a finite space with cycles it loops unless repeated states are checked.
Why does iterative deepening search combine the strengths of depth-first and breadth-first search?
It runs depth-limited depth-first search with limits 0, 1, 2 and so on. It needs only memory like depth-first search, yet it finds the shallowest goal like breadth-first search when step costs are equal. The repeated work is small because most nodes lie at the deepest level.
Why is A* search optimal when its heuristic is admissible?
An admissible heuristic never overestimates the true remaining cost, so never exceeds the cost of the best solution through a node. When a goal is chosen for expansion, no frontier node can lead to a cheaper goal. This argument is for tree search. Graph search needs consistency as well.
What is the difference between greedy best-first search and A* search?
Greedy best-first search orders the frontier by the heuristic alone, so it chases the node that looks closest to the goal. A* orders by , adding the cost already paid. Greedy search is fast but neither optimal nor always complete. A* is optimal with an admissible heuristic.
What is a consistent heuristic, and how does it relate to an admissible one?
A heuristic is consistent if for every step from to a successor , a triangle inequality, and at goals. Every consistent heuristic is admissible, but not the reverse. With consistency, never decreases along a path, so A* graph search expands each node once at its best cost.
A MAX root has three MIN children. Their leaves, read left to right, are (3, 12, 8), (2, 4, 6) and (14, 5, 2). Alpha-beta pruning visits children and leaves left to right. How many leaves are evaluated, and what is the root value?
Alpha-beta evaluates 7 of the 9 leaves, and the root value is 3, the same as plain minimax gives. Once the second MIN node reads 2, which is no better than the 3 MAX already has, its other two leaves cannot change the result.
WORKING
- First MIN node reads 3, 12, 8 and returns 3, so at the root.
- Second MIN node reads 2. Since , MAX will never choose it, so 4 and 6 are pruned: 1 leaf read.
- Third MIN node reads 14, 5, 2. Its value only drops to 2 at the last leaf, so all 3 are read.
- Root value ; leaves read .
Propositional and predicate logic
Logic notesWhat is the difference between a tautology, a contradiction and a satisfiable formula?
A tautology is true under every assignment, and a contradiction is false under every assignment. A satisfiable formula is true under at least one assignment, so every tautology is satisfiable and no contradiction is. A formula is a tautology exactly when its negation is a contradiction.
What does it mean for a knowledge base to entail a sentence?
A knowledge base entails a sentence , written , when every assignment that makes all of true also makes true. Equivalently, is unsatisfiable. This is a statement about meaning, which is separate from whether a proof procedure finds a derivation.
Why does proof by resolution add the negation of the goal to the clauses?
Resolution is a refutation method. It shows by showing that is unsatisfiable, which is reached when the empty clause is derived. All sentences must first be in clause (CNF) form. Resolution is sound, and refutation-complete for propositional logic.
Over the three propositional variables , and , in how many of the 8 truth assignments is true?
The formula is true in 5 of the 8 assignments, because only 3 assignments make it false: those where is true and is false. An implication is false only in that case.
WORKING
- An implication is false only when its premise is true and its conclusion is false.
- Premise is true for 3 of the 4 settings of .
- Conclusion is false in 1 way, so the formula is false in rows.
- True rows .
Why is "every student likes some course" written with an implication after the universal quantifier and a conjunction after the existential one?
The sentence is . The implication limits the claim to students, since a conjunction after would say everything is a student. The conjunction after asserts that such a course exists, while an implication there would be satisfied by anything that is not a course.
What is unification in first-order logic, and why is the occurs check needed?
Unification finds a substitution that makes two expressions identical, ideally the most general one. For and it gives . The occurs check rejects binding a variable to a term that contains it, such as with , which would create an infinite term.
Four propositional variables , , and give 16 truth assignments. How many of them satisfy the clause ?
The clause is satisfied by 14 of the 16 assignments, since only 2 assignments make it false. A disjunction fails only when every literal is false, which fixes false, true and false, and leaves free.
WORKING
- A disjunction is false only when every literal is false.
- That needs false, true and false: 1 setting of .
- Variable is free, so there are 2 falsifying assignments.
- Satisfying assignments .
Reasoning under uncertainty
Uncertainty notesWhat is a Bayesian network, and how does it give the joint distribution?
A Bayesian network is a directed acyclic graph with one node per random variable and a conditional table at each node. The joint distribution is the product of these tables: . When each node has few parents, this stores far fewer numbers than the full joint table.
Boolean variables and have no parents, has parents and , and has parent . How many independent probabilities does this Bayesian network need, and how many does the full joint table need?
The network needs 8 independent probabilities, against 15 for the full joint table over four Boolean variables. Each Boolean node needs one number per setting of its parents, for Boolean parents, so the network stores .
WORKING
- A Boolean node with Boolean parents needs probabilities.
- : 1, : 1, : , : .
- Network total .
- Full joint .
How do chain, fork and collider structures differ in d-separation?
In a chain and a fork , the path is blocked when is observed. A collider is the reverse: the path is blocked while neither nor any descendant of is observed, and observing either opens it.
Why is variable elimination cheaper than inference by enumeration?
Enumeration sums the full joint product for every combination of the hidden variables, repeating the same sub-products many times. Variable elimination sums out one variable at a time and stores the result as a factor that is reused. Its cost depends on the elimination order, and a poor order can still be expensive.
What is the difference between rejection sampling and likelihood weighting?
Rejection sampling draws full samples from the prior and throws away those that disagree with the evidence, which wastes many samples when the evidence is unlikely. Likelihood weighting fixes the evidence variables, samples only the others, and weights each sample by the probability of the evidence given its parents.
How does Gibbs sampling estimate a posterior probability?
Gibbs sampling fixes the evidence variables and starts from an arbitrary state. It repeatedly resamples one non-evidence variable at a time from its distribution given its Markov blanket. In the long run the states visited follow the posterior, so the fraction of states with the query value estimates it. Successive samples are correlated.
Rejection sampling draws 1000 samples from a network. The evidence is true in 200 of them, and the query variable is true in 150 of those 200. What is the estimate of ?
The estimate of is 0.75, based on the 200 samples that agree with the evidence. The other 800 are rejected, and the estimate is the fraction of kept samples with true, .
WORKING
- Samples that disagree with are rejected: discarded.
- Only the 200 consistent samples are counted.
- .
For events and , , and . What is ?
By Bayes' rule, is about 0.774. The denominator comes from summing and , so the probability of rises from 0.3 to about 0.77 once is known.
WORKING
- .
- .
- .
- .
More interview questions: Data Structures and Algorithms · Probability and Statistics · Machine Learning · Linear Algebra · Database Management and Warehousing
Who hires and how they select: IT jobs for DS & AI
Artificial Intelligence: notes, formula sheet and past questions