Two Pointers in Data Engineering

Concepts covered: Two-Pointer, List Modification

The 4th shape, 2 inputs with 1 cursor each, is the one you run in production without calling it two pointers. With 2 sorted inputs you make 1 pass and advance whichever head is smaller. That is the merge step of merge sort, the sort-merge join that Postgres and Spark run (as do most warehouse engines), the reconciliation of a bank file against a ledger, and the compaction of a change log. An interviewer on a data platform team asks this version, because it tells them whether you understand what a join costs.

Reconciling 2 sorted ledgers

def reconcile(bank_ids, ledger_ids):
    """Both lists sorted ascending. Returns ids missing from each side."""
    i = j = 0
    missing_from_ledger, missing_from_bank = [], []
    while i < len(bank_ids) and j < len(ledger_ids):
        if bank_ids[i] == ledger_ids[j]:
            i += 1
            j += 1
        elif bank_ids[i] < ledger_ids[j]:
            missing_from_ledger.append(bank_ids[i])
            i += 1
        else:
            missing_from_bank.append(ledger_ids[j])
            j += 1
    missing_from_ledger.extend(bank_ids[i:])
    missing_from_bank.extend(ledger_ids[j:])
    return missing_from_ledger, missing_from_bank

Walk it on bank_ids = [101, 102, 104, 107] and ledger_ids = [101, 103, 104, 107, 109]. The decision at every step reads the 2 heads and moves the smaller, which is the retire-the-element-that-cannot-match argument from the pair search, applied across 2 inputs: a bank id smaller than the ledger head can never match anything later in the ledger, so it's reported and left behind.

The result is ([102], [103, 109]) after 5 comparisons, and no id was compared against more than 2 others. The same loop with the equality branch emitting a joined row instead of advancing in silence is an inner join; with the smaller-head branches emitting rows it is a full outer join. Say which join your branches implement, because that sentence is the bridge the interviewer is waiting to cross.

What the SQL engine does with it

Both inputs are sorted on the join key, at O(n log n) each, and then the merge is 1 pass. The alternative is a hash join: build a dict from the smaller side, probe with the larger, O(n + m) time and O(min(n, m)) memory. The follow-up is when you would choose the merge, and the answer is when neither side fits in memory, or when both arrive already sorted, such as 2 partitioned Parquet files written with a sort order on the key, where the sort is already paid for and the join streams.

Hash join

• Build a dict from the smaller side, probe with the larger
• O(n + m) time with no sort required
• Memory holds the whole smaller side
• Default in Spark and Postgres when one side fits

Sort-merge join

• 1 cursor on each sorted input, smaller head advances
• O(n log n) to sort, then 1 streaming pass
• Once both inputs are sorted, memory holds the current row from each side plus a buffer for runs of equal keys
• Chosen when neither side fits or both arrive sorted

CDC compaction: keep the last change per key

A change data capture log holds every update to a row, and the serving table wants the latest state per key. Sorted by (key, ts), that is the read and write loop with the comparison on the key, and the write cursor keeping the last row of each run rather than the first. Dedup on a sorted event stream is the same loop keeping the first, with the comparison recs[read]['event_id'] != recs[write]['event_id']. In SQL, keep-first dedup is ROW_NUMBER() OVER (PARTITION BY key ORDER BY ts) = 1, and keep-last compaction needs ORDER BY ts DESC in the same window. The sorted requirement is identical for both: without it, a repeat of an earlier key arrives after a different key, and the check against the last kept record misses it.

def latest_per_key(changes):
    """changes sorted by (key, ts). Keeps the last change per key, in place."""
    if not changes:
        return 0
    write = 0
    for read in range(1, len(changes)):
        if changes[read]["key"] == changes[write]["key"]:
            changes[write] = changes[read]      # newer change, same key
        else:
            write += 1
            changes[write] = changes[read]
    return write + 1

Do

• Say "the input is sorted, so" before the first line of code
• Name the shape: converging, read and write, fast and slow, or 1 cursor each
• State the invariant and which pointer is safe to discard on each branch
• Return indexes or a count when asked, and say what the tail holds
• Give the complexity with the real input size, in pairs checked

Avoid

• Write the nested loop first and wait to be asked for better
• Reach for a set or dict when the question said in place
• Guard a 2-hop move with a 1-hop check
• Claim O(1) space while a cleaning step allocates a copy
• Run a merge or dedup on input nobody has sorted

About this lesson

This section is part of the Two Pointers: Beginner lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.