Back to path
AdvancedLexi · Project 11 of 12 ~6h· 5 milestones

Expand queries with backtracking and a greedy cut

Continues from the last build: dsa-lexi-editdistance

Lexi can now fix a single typo term with edit distance, rung 10 turns "pyhton" into "python" and moves on.

Backtracking recursion with explicit undoBranch-and-bound pruning on a cost budgetGreedy heuristic design and its failure modesCombinatorial complexity estimation before running codeTimed benchmarking across growing input sizesAvoiding shared mutable state across recursive branchesDesigning a strategy dispatcher based on measured costScoring functions that combine multiple signals
Build this freeBrowse all projectsNo credit card. Already a member?

What you'll build

Lexi expands multi-term queries by backtracking through candidate combinations with branch-and-bound pruning on a cost budget, falls back to a greedy top-beam cut when the search space is too large to exhaust, and a dispatcher picks between the two based on the estimated size of the space. You can point at a real benchmark table showing pruning cut 8-term search work by roughly 250x versus brute force, and a real worked example where the greedy cut provably misses the query expansion that the exhaustive search finds.

See how we teach, before you sign up

You don't just get code dumped on you. Every starter file and every solution is explained line-by-line, in plain English. Here's one real file from this project:

lexi_rung11/query_expansion.pypython
from dataclasses import dataclass


@dataclass(frozen=True)
class Candidate:
    word: str
    cost: int


def brute_force_expand(term_candidates: list) -> list:
    """Naive cartesian product, no pruning. Starter baseline."""
    results: list = []

    def build(i: int, chosen: list, cost_so_far: int) -> None:
        if i == len(term_candidates):
            results.append((tuple(chosen), cost_so_far))
            return
        for cand in term_candidates[i]:
            chosen.append(cand.word)
            build(i + 1, chosen, cost_so_far + cand.cost)
            chosen.pop()

    build(0, [], 0)
    return results

Reading this file

  • class Candidate:Same Candidate shape rung 10 produces per term, carried forward unchanged.
  • def brute_force_expand(term_candidates: list) -> list:The baseline you will benchmark, feel explode, then replace with pruning.
  • chosen.pop()Undo is what makes this backtracking rather than plain nested loops.

That's 1 of 8 explained code blocks in this single project.

The build, milestone by milestone

  1. 1

    Model per-term candidates the whole-query search will combine

    4 guided steps

    You cannot backtrack or prune over a decision you haven't represented yet. Every later structure, the recursion tree, the budget check, the greedy cut, operates on these per-term candidate lists, get the shape right here and the rest of the rung is about search strategy, not data modeling.

  2. 2

    Build the brute-force expander and feel the explosion on a real clock

    4 guided steps

    You need the pain to be measured, not assumed. A real timed table showing 625 combinations at 4 terms balloon to 390,625 at 8 terms, with wall-clock time growing from under a millisecond to half a second, is what justifies every design decision in the rest of this rung. Skip this and pruning looks like premature optimization instead of a necessity.

  3. 3

    Add branch-and-bound pruning and measure how much work it skips

    5 guided steps

    Pruning is what turns an unusable search into a usable one without giving up correctness, the pruned search still finds the true best combination under the budget, it just refuses to waste time exploring combinations that were already mathematically dead. That guarantee, same answer as brute force, dramatically less work, is the entire value of backtracking over brute force.

  4. 4

    Add a greedy cut for when even pruning is too slow

    5 guided steps

    Backtracking with pruning is still exponential in the worst case, some queries have enough terms and candidates that even a tight budget leaves too many nodes to visit inside a search box's latency budget. Greedy trades the correctness guarantee for a hard cap on work, O(k) in the number of terms, and you need to know exactly what that trade costs you, not just that it's faster.

  5. 5

    Dispatch between exhaustive and greedy based on measured search size

    5 guided steps

    This is the decision the whole rung has been building toward: never pick a search strategy by habit, pick it by the measured or estimated size of the problem in front of you. A dispatcher that always reports which path it took also means nothing downstream silently inherits a greedy result believing it's exhaustive.

What's inside when you start

3 starter files, ready to clone
5 guided milestones
5 full reference solutions
8 code blocks explained line-by-line
5 "is it working?" checks
4 interview questions it prepares you for

You'll walk away with

query_expansion.py with Candidate, brute_force_expand, backtrack_expand, greedy_expand, expand_query
benchmark_expansion.py producing a timed table across at least 4 growing term counts
A written or printed worked example where greedy_expand provably misses the exhaustive best
test_expansion.py covering pruning correctness (backtrack_expand finds the same best as brute force under a budget) and greedy's local behavior

This is portfolio-grade. Build it free.

Sign up to unlock every milestone step-by-step, the code skeletons, full reference solutions, and checkable tasks, with your progress saved as you build.

Start building