Spotting the Pattern in 10 Seconds
Concepts covered: Two-Pointer
The word that gives it away
The question names the data and never the pattern. The setup says "sorted" in its first or second sentence, usually as an aside, then asks you to find a pair or count matches, or to merge inputs or rewrite one in place. The order is the gift, and the test is whether you noticed it being handed over. A nested loop is a correct answer to every one of these questions, which is why candidates who write one feel fine until the follow-up "can you do better?" arrives with 20 minutes on the clock.
In a data engineering loop the disguise is operational. "Here are 2 ledgers sorted by transaction id, find the ids present in one and missing from the other." "This event log is sorted by timestamp and holds duplicate rows, drop them without allocating a second list." "Does this chain of job dependencies ever loop back on itself?" The ledgers are a pair search over ordered data and the event log is a rewrite in place. The dependency chain is a walk where you can only follow each link forward, and that one-way constraint is its clue, the way "sorted by" and "without allocating" are the clues in the other 2.
The 4 shapes, and how to tell them apart
| Shape | Where the pointers start | What moves them | Question it answers |
|---|---|---|---|
| Opposite ends converging | index 0 and index n-1 | sum too small moves left up, too large moves right down | pair with a given sum, palindrome check |
| Same direction, read and write | both at index 0 | read every step, write only on a kept element | remove duplicates, move zeroes, compact |
| Fast and slow | both at the head | slow 1 node, fast 2 nodes per step | cycle detection, middle of a linked list |
| Two inputs, one cursor each | index 0 of each list | the smaller head advances | merge 2 sorted lists, sort-merge join |
The shape follows from 2 facts: how many inputs there are, and which way you can move. One sorted list and a pair to find means the ends converge. One list that must be rewritten without a copy means read and write. A linked structure you can only walk forward means fast and slow. Two sorted inputs mean 1 cursor on each. The table is the whole decision, and naming the row out loud is what tells the interviewer you have seen this before.
The sentence to say before any code
If the input arrives unsorted and the question still reads like a pair search, the expected answer changes shape: a dict of value to index, checking each number's complement before storing it, runs in O(n) time and O(n) space and keeps the original indexes. Sort-then-converge is the option when memory is the constraint, at O(n log n) time, and it changes the indexes you return. Name both, and ask whether the caller wants positions in the original order. That question is worth more to your score than either code path, because it shows you noticed what sorting destroys.
- 49,995,000
- 10,000
The arithmetic behind the tiles is n times n minus 1 over 2 for the nested loop against at most n for the walk, and it is worth saying with the real input size the interviewer gave you. "Ten thousand rows is 50 million pair checks" lands harder than "quadratic", and it is the number that makes the follow-up land on your terms.
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.