Back to path
IntermediateLexi · Project 8 of 12 ~5h· 5 milestones

Match phrases with two pointers and a window

Continues from the last build: dsa-lexi-boolean-index

Rung 7 gave Lexi a boolean inverted index: term to set of doc ids, so an AND query on "machine" and "learning" returns every document that contains both words somewhere.

Positional inverted indexesTwo-pointer technique over two sorted listsSliding window over a distance axisTelling O(n*m) apart from O(n+m) by measurementDesigning a fair, apples-to-apples benchmarkOff-by-one boundary reasoning in loop conditionsBuilding a stress-test corpus that exposes an algorithm's weak spotReading a growth curve off timed data
Build this freeBrowse all projectsNo credit card. Already a member?

What you'll build

Lexi stores a positional index, term to doc to sorted list of word positions, and answers phrase queries with a two-pointer walk across the two position lists in O(n+m) time instead of the O(n*m) nested-loop check. A sliding-window variant reuses the same sorted positions to answer near-proximity queries like "machine" and "learning" within 5 words of each other, without rescanning the whole document. A benchmark proves the two-pointer walk actually scales linearly while the naive nested loop scales quadratically, on the exact same find-all-matches task.

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-window/positional_index.pypy
from __future__ import annotations

from collections import defaultdict


def tokenize(text: str) -> list[str]:
    return text.lower().split()


def build_positional_index(docs: dict[int, str]) -> dict[str, dict[int, list[int]]]:
    index: dict[str, dict[int, list[int]]] = defaultdict(lambda: defaultdict(list))
    for doc_id, text in docs.items():
        for position, term in enumerate(tokenize(text)):
            index[term][doc_id].append(position)
    return {term: dict(doc_map) for term, doc_map in index.items()}


def postings_for(index: dict[str, dict[int, list[int]]], term: str, doc_id: int) -> list[int]:
    return index.get(term, {}).get(doc_id, [])

Reading this file

  • index[term][doc_id].append(position)Every occurrence of a term gets its own position recorded, not just a yes/no flag.
  • defaultdict(lambda: defaultdict(list))Two-level default dict so a brand new term or doc never needs a manual init check.
  • return index.get(term, {}).get(doc_id, [])Missing term or doc returns an empty list, so callers never branch on KeyError.
  • for position, term in enumerate(tokenize(text)):enumerate() over the tokenized text is where positions come from, word 0, word 1, and so on.

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

The build, milestone by milestone

  1. 1

    Store word positions, not just presence

    4 guided steps

    Phrase search needs to know WHERE a word sits, not just that it exists somewhere in the document. Position lists are the only structure that carries that information forward without rescanning the raw text on every query.

  2. 2

    Write the naive nested-loop matcher first

    4 guided steps

    You cannot credibly claim O(n+m) later without a real O(n*m) baseline solving the exact same task sitting right next to it. Writing the naive version first also makes the nested-loop cost visible in your own hands before you optimize it away.

  3. 3

    Replace the nested loop with a two-pointer walk

    5 guided steps

    Because both lists are already sorted (positions are appended in text order), you never need to look backward. Whichever cursor points at the smaller position is the one that is behind, advancing only that cursor guarantees every element is visited at most once per list, giving O(n+m) instead of O(n*m).

  4. 4

    Answer near-phrase queries with a sliding window

    4 guided steps

    Real phrase search is rarely just exact adjacency, users also want near-proximity matches. A sliding window over the same sorted positions answers this without going back to raw text, and without repeating the O(n*m) mistake, the trailing edge of the window only ever moves forward.

  5. 5

    Prove O(n+m) beats O(n*m) with a real benchmark

    5 guided steps

    A complexity claim without a timed, growing-input measurement is just an assertion. The only way to make O(n*m) versus O(n+m) undeniable is to make both algorithms solve the identical find-all-matches task on the identical inputs, at multiple sizes, and watch the naive curve bend upward while the two-pointer curve stays straight.

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

positional_index.py exposing build_positional_index() and postings_for()
phrase_search.py exposing naive_phrase_positions(), phrase_positions(), and near_phrase_positions()
benchmark_phrase.py that builds a growing corpus, times both matchers on the same task, and prints a table proving the O(n+m) vs O(n*m) divergence
A short written note (docstring or comment block) explaining why a boolean inverted index cannot answer phrase queries and positions can

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