A strong answer
git bisect is a binary search over commits. You give it one commit where the behavior is good and a later one where it is bad. It checks out a commit roughly halfway between them, you test it, and you mark it good or bad. A bad midpoint means the first bad commit is at or before it; a good one means it is after. Each answer halves the remaining range, so finding the culprit among n commits takes about log₂ n tests: 10 for a thousand commits, 13 for five thousand.
It works because "is this commit broken?" is monotonic over the range: false for every commit before the one that introduced the bug, and true from that commit onward. That is the same structure as searching an answer space, the first "yes" in a "no…no, yes…yes" sequence.
You can automate it with git bisect run ./test.sh, where the script's exit code says good (0), bad (1 to 127, except 125) or skip (125, for commits that can't be tested, such as ones that don't build). Bisect handles non-linear history by choosing commits that split the remaining graph roughly in half.
What breaks it is a predicate that isn't monotonic: a bug that is fixed and reintroduced, a flaky test, or an environment that differs between runs. Then bisect still returns a commit, but it may be the wrong one, so the test must be deterministic and reproduce the original problem.
What the interviewer is listening for
- Binary search over history, and the log₂ n cost.
- The monotonicity requirement, and what violates it.
- Practical use: automating with a script, skipping untestable commits.
Common mistakes
- Describing a linear walk backwards through history.
- Ignoring flaky tests, which silently mislead the search.
- Forgetting to reset with
git bisect resetafterwards.