Loading page…
Watch the pattern move.
One animated lecture per lesson: the Kestrel task, the first attempt that is too slow, the idea traced step by step, and the template you will write in the interview. Each one stops for quick checkpoints and opens its lesson when you want to read it.
your progress…
M3 · Hashing2 lectures · 26 min
#1 · M311 minHash table internalsHash table internalsKestrel Pay must answer whether a payment id was stored, for a million ids and 20,000 requests a second. Scanning a list costs about 100 seconds of work for each second of traffic. A hash function turns the key into a bucket, so a lookup reads one bucket. Collisions are handled by chaining or probing, and the table doubles when the load factor passes about three quarters, which keeps inserts amortised constant time.3 checkpoints · 26 chapters
#2 · M315 minSeen-set and complementSeen-set and complementKestrel Pay must find which two payments in a batch of 100,000 add up to a disputed total. Trying every pair makes about 5 billion checks and takes about 50 seconds. A hash set remembers the values already read, and a hash map from value to position turns each question into one lookup: the complement, the target minus the value. Look first and store afterwards, keep the first position, and the pass costs O(n) time.3 checkpoints · 27 chapters
M4 · Two pointers5 lectures · 51 min
#3 · M411 minOpposite endsOpposite endsKestrel Freight wants two waiting parcels that fill a truck's spare capacity exactly. The first attempt checks every pair, about 1.25 billion checks at a central hub. On a list sorted by weight, one pointer at each end rules out one parcel with every comparison, so the pass is O(n) with O(1) extra memory.3 checkpoints · 26 chapters
#4 · M410 minRead and write pointersRead and write pointersA Kestrel Freight dock gate must remove no-read scans from a fixed buffer in place, in scan order. Deleting each no-read and sliding the rest moves about a billion values on a full buffer. A read pointer that visits every scan and a write pointer that moves only for kept scans copy each kept scan once: O(n) time and O(1) extra memory.3 checkpoints · 26 chapters
#5 · M410 minThree-way partitionThree-way partitionKestrel Freight must group the parcels on a loading belt by priority class, express, standard and economy, in one turn of the belt. Counting and writing back is correct but takes two turns. Three pointers grow the express block from the front and the economy block from the back, so every parcel is checked once: exactly n steps and O(1) extra memory.3 checkpoints · 26 chapters
#6 · M410 minMerging sorted sequencesMerging sorted sequencesKestrel Freight needs one timeline from two sorted lists of gate scans, rebuilt every second. Joining and sorting is correct but about four times too slow, because it ignores the order each list already has. Two pointers take the smaller front each step and copy the rest when a list runs out: n plus m steps. The same walk finds shared values and overlapping time slots.3 checkpoints · 24 chapters
#7 · M410 min3-sum3-sumKestrel Stream must list every distinct group of three tracks that fills a twelve-minute block. Checking every group takes about 45 seconds at 3,000 tracks. Sorting a copy, fixing the first value and running the opposite-ends pair search on the rest makes it order n squared. Skipping repeated first values and equal values after a match keeps each block once.3 checkpoints · 25 chapters
M5 · Sliding window4 lectures · 38 min
#8 · M58 minSliding window: fixed and variable windowsSliding window: fixed and variable windowsKestrel Stream needs the busiest stretch of a launch day. The first attempt re-adds every window and needs about 600 billion additions a refresh. Neighbouring windows share almost everything, so a running total that subtracts one value and adds one makes the pass linear; the same idea, with a window that grows and shrinks, finds the longest or shortest stretch under a rule.3 checkpoints · 27 chapters
#9 · M59 minWindows with countsWindows with countsKestrel Stream's rights team must find every place a channel played a full mix back to back, in any order. The first attempt recounts every window and needs about 715 billion count updates a night. Neighbouring windows change only two counts, and a matched counter makes each check constant time, so the whole report runs in minutes.3 checkpoints · 26 chapters
#10 · M510 minAt most K and exactly KAt most K and exactly KKestrel Stream needs the longest session that touches at most two categories, and the number of sessions that touch exactly two. The first attempt extends from every start and needs about a trillion steps on the worst night. One window that only moves forward finds the longest in O(n), adding right minus left plus one counts every valid session, and exactly K is at most K minus at most K minus 1.3 checkpoints · 26 chapters
#11 · M511 minMinimum covering windowMinimum covering windowKestrel Stream sells sponsored blocks: the shortest stretch of a channel's schedule that plays every sponsored track as often as required. The first attempt extends from every start and needs about 2.8 trillion reads a night. One window that grows until it covers and shrinks while it covers, with a missing counter, finds the earliest shortest block in O(n + m).3 checkpoints · 26 chapters
