Block Coding Interview: Sorting & Intervals

The rolling window from the phone screen is the array problem Block is known for, but the same pairing rounds also use a few classic problems. There's a format for sending a batch of strings, a pair count with an algebra shortcut, a sort that can only flip prefixes, and intervals that stack on each other. Each one needs a different idea from the deque, and you can say each idea in one sentence before you type.

Some of these have a light payments story and some have none. Encode and Decode Strings becomes line-item notes sent through an API that takes a single string. Count Nice Pairs becomes reference numbers on a reconciliation feed, and Falling Squares becomes campaigns stacked on a Square Dashboard chart. Pancake Sorting has no story at all, so look past the framing and name the structure underneath before you start coding.

The Block angle

In these four, the reason the approach works is most of the solution, so say it before you write the loop. A length prefix means the decoder never reads a note's contents as structure. A key of x minus rev(x) means two references match exactly when their keys are equal. Two flips per round means the sorted block at the bottom of the stack only ever grows, and a strict overlap test means a block touching another edge to edge stays on the floor. Block scores the pairing conversation along with the code, and each of those sentences gives the interviewer something to check while you type.

How Block frames these

None of these is the most reported phone-screen problem. They come from the wider pool of problems tagged to Square, and each tends to come with a second part that keeps the first idea and changes one thing. The encoder may next get a payload that arrives in chunks, and the pair count may be limited to matches within one seller. Pancake sizes can start to repeat, and the chart can grow to a hundred thousand campaigns, at which point the quadratic scan gives way to a segment tree. Each second part is worked in its solution.

Two of these four get easier with a rewrite on paper before any code. Moving rev(refs[j]) across the equals sign turns a condition on pairs into a key on single elements. Writing the length ahead of the payload turns an ambiguous parse into a cursor that only ever lands on record starts. The other two reward keeping it simple. Pancake Sorting needs nothing beyond its two-flip rule, and Falling Squares needs no segment tree until the scale calls for one.

Asked at Block

Four problems from Square's public problem bank: three Mediums, then its one Hard. Solve each in the editor and run the cases the statement doesn't mention, such as an empty batch, a note made only of markers, or two blocks that meet at a single edge, before you open the walkthrough.

Encode and Decode Strings (LC 271): A Length-Prefixed Wire Format

MediumCommonly asked

Problem

A point-of-sale service has to hand a ticket's line-item notes to a receipt service, and the receipt service's API takes exactly one string field. Seller-typed notes can hold any printable ASCII character, including #, digits, commas and pipes, so no separator character is safe to split on.

Build a Codec with two methods. encode(strs) takes a list of strings and returns one string. decode(s) takes a string produced by encode and returns the original list, in order, with every note byte-for-byte intact. Empty notes are legal, and an empty list is legal.

Use a length-prefixed format: each note is written as its length in characters (decimal, no padding), then a single #, then the raw note. So ["lunch","tip"] encodes to "5#lunch3#tip", and an empty list encodes to "". Return the encoded string from encode and the list from decode.

Codec()
encode(["lunch","tip"])→ "5#lunch3#tip"
decode("5#lunch3#tip")→ ["lunch","tip"]

The decoder reads 5, takes the five characters "lunch", then reads 3 and takes "tip". It never looks for a boundary inside a note.

Codec()
encode(["A#1","2#B"])→ "3#A#13#2#B"
decode("3#A#13#2#B")→ ["A#1","2#B"]

Both notes contain "#" and a digit, which wrecks any split-based decoder. Here the reader takes 3 characters after the first marker, lands on "3#" for the second record, and takes 3 more.

Codec()
encode([""])→ "0#"
decode("0#")→ [""]
encode([])→ ""
decode("")→ []

An empty note still writes its zero-length frame, so [""] and [] encode differently and both round-trip.

How this uses the pattern

Frame each note as length, marker, payload. To decode, keep a cursor at the start of a record, find the first "#" at or after it (that one always ends the length digits), parse the number, slice exactly that many characters, and jump the cursor past them. The cursor only ever lands on record starts, so a "#" inside a note is skipped over and never read as structure.

Encode and Decode Strings (LC 271): A Length-Prefixed Wire Format

Click "Run" to execute your code

The Block angle

Encode and Decode Strings is in Square's public problem bank, and it plays like payments plumbing. A batch of line-item notes or transaction memos has to go through an API that takes one string, and text typed by sellers will contain whatever separator you pick, whether a pipe, a comma or a stray "#12". Name that problem before coding, then put each note's length in front of it so the decoder reads a count and takes exactly that many characters. Block likes formats that survive any input for the same reason it likes writes that survive a retry. Follow-ups tend to come next, such as an empty note, a payload where characters and bytes disagree, or "decode it as chunks arrive."

Take it further

A second part streams the payload in chunks that split at arbitrary points, even in the middle of a length prefix. Wrap the decoder in a StreamDecoder whose feed(chunk) returns only the notes completed so far. Keep a buffer of unread text, append each chunk, and run the same cursor loop until the next record is incomplete: either no # has arrived yet, or fewer than n characters follow it. Stop there, keep only the partial tail, and wait for the next chunk. Worked in the solution.

Count Nice Pairs (LC 1814): Canonical Key, One Hash Map

MediumSometimes asked

Problem

A reconciliation feed carries refs, a list of non-negative integer reference numbers in arrival order. One legacy export writes reference numbers with their decimal digits reversed, so the matcher works with rev(x): the digits of x in reverse order with leading zeros dropped (rev(120) = 21, rev(7) = 7, rev(0) = 0).

Two positions i < j form a matched pair when refs[i] + rev(refs[j]) == refs[j] + rev(refs[i]). Every qualifying pair of positions counts on its own, so equal values at three positions give three pairs.

The feed can hold up to 10^5 entries, each at most 10^9, which means the pair count can pass the 32-bit range. Return the number of matched pairs modulo 1000000007.

Inputrefs = [42,11,1,97]Output2

42 - 24 = 18 and 97 - 79 = 18, so positions 0 and 3 match. 11 - 11 = 0 and 1 - 1 = 0, so positions 1 and 2 match. Two pairs.

Inputrefs = [13,10,35,24,76]Output4

13, 35 and 24 all reduce to -18, which gives three pairs among them. 10 and 76 both reduce to 9 (rev(10) is 1, the leading zero drops), which adds one more.

How this uses the pattern

Move the reversed terms to one side: the condition is equivalent to refs[i] - rev(refs[i]) == refs[j] - rev(refs[j]). Reduce each reference to that key, keep a hash map from key to how many earlier positions produced it, and add the current key's count to the answer before recording it.

Count Nice Pairs (LC 1814): Canonical Key, One Hash Map

Click "Run" to execute your code

The Block angle

Count Nice Pairs is on Square's LeetCode company list, and the hard part is algebra you do before any code. Comparing every reference against every other is quadratic, and a busy seller's daily feed makes that slow enough to matter. Move the reversed terms across and each side depends on one position, so every reference reduces to the key x minus rev(x) and matching pairs are equal keys. Say that rewrite out loud, then count keys in a hash map, the same move the ledger prefix-sum problem uses. Expect follow-ups such as "what overflows here?" and then "only match within the same seller," where the key becomes a tuple.

Take it further

A second part limits matches to references from the same seller. Each row now arrives as [seller_id, ref], and two positions match only when they share a seller and meet the original condition. The algebra stays the same. Build the key as the pair (seller_id, ref - rev(ref)) instead of the integer alone, and the same hash-map count works, because two rows share a tuple exactly when both halves agree. Worked in the solution.

Pancake Sorting (LC 969): Sort With Prefix Reversals

MediumSometimes asked

Problem

A stack of pancakes is given as arr, listed from the top of the stack to the bottom. The stack holds every integer from 1 to n exactly once, where n is len(arr). The only move you have is a flip: pick k with 1 <= k <= n, slide a spatula under the top k pancakes and turn them over, so arr[0..k-1] comes back reversed while everything below stays put.

Sort the stack ascending, smallest on top, using flips only. Many flip sequences sort the same stack, so build yours with this rule, which makes the answer unique. For size from n down to 2, find the pancake whose value is size. If it already sits at index size - 1, emit nothing this round. Otherwise, if it is not already on top, flip k = index + 1 to bring it up, then flip k = size to drop it into position size - 1.

Return the list of k values in the order you apply them. A stack that is already sorted, including a single pancake or an empty stack, returns [].

Inputarr = [3,2,4,1]Output[3,4,2,3,2]

Flip 3 brings the 4 to the top and flip 4 parks it at the bottom, leaving [1,3,2,4]. Flips 2 and 3 park the 3, giving [2,1,3,4], and with the 2 already on top a single flip 2 finishes the round.

Inputarr = [1,2,3]Output[]

Every round finds its pancake already parked at index size - 1, so no flip is emitted.

Inputarr = [4,1,2,3]Output[4,3]

The 4 starts on top, so the round skips the bring-up flip and goes straight to flip 4, giving [3,2,1,4]. The 3 is now on top too, and flip 3 sorts the rest.

How this uses the pattern

Grow a sorted block from the bottom of the stack one pancake per round, largest first. Each round costs at most two flips: one to bring the largest unsorted pancake to the top, one to turn the whole unsorted prefix over and land it at the bottom of that prefix. Check the parked case before the on-top case, since a pancake already in place needs neither flip.

Pancake Sorting (LC 969): Sort With Prefix Reversals

Click "Run" to execute your code

The Block angle

Pancake Sorting is in Square's public problem bank with no payments story, so treat it as a plain greedy construction problem. It suits a pairing round because the output is a list of moves, and the interviewer can't tell a list of moves is right until you explain it. Before you type, say what stays true: after each round the largest remaining pancake has joined a sorted block at the bottom, and no later flip reaches that block. Two flips per round over n - 1 rounds gives a limit of 2n - 2 that the interviewer can check by eye. Square's two-part format makes a second question likely, such as "now the sizes can repeat," which breaks any lookup by value.

Take it further

A second part drops the permutation guarantee, so sizes are any positive integers and can repeat. Looking up the value size no longer finds anything, so each round takes the maximum of the unsorted prefix instead. The parked check compares the value at index size - 1 with that maximum, because a tied copy already at the bottom of the prefix needs no flips. When a flip is needed, search only the unsorted prefix and take the first copy of the maximum. Each round still uses at most two flips, so the sequence stays within 2n - 2. (Worked in the solution.)

Falling Squares (LC 699): Interval Maxima Without a Segment Tree

HardRarely asked

Problem

A promotions view in Square Dashboard draws a seller's campaigns as a stacked chart on a day axis. Each campaign arrives as [left, side] and is drawn as a square block: it covers the half-open span [left, left + side) and stands side units tall, so a longer campaign draws a bigger block. Blocks are placed one at a time, in the order given.

A new block drops straight down and rests on the tallest earlier block whose span overlaps its own, or on the axis when nothing overlaps. Two spans overlap only when they share some length: a_left < b_right and b_left < a_right. A block whose left edge equals another block's right edge sits beside it and does not rest on it. A landed block never moves.

Return a list where entry i is the height of the tallest stack anywhere on the chart once the first i + 1 blocks have landed.

Inputpositions = [[1,2],[2,3],[6,1]]Output[2,5,5]

Block one covers [1,3) at height 2. The second covers [2,5), overlaps it, and lands on top at 2 + 3 = 5. Nothing sits under [6,7), so the third block rests at 1 and the tallest stack stays 5.

Inputpositions = [[100,100],[200,100]]Output[100,100]

The first block ends at 200 and the second starts at 200. Sharing an edge does not count as overlap, so the second block sits on the axis and the tallest stack is still 100.

Inputpositions = [[1,10],[20,1],[20,1]]Output[10,10,10]

The two small blocks stack to height 2 at day 20. The answer tracks the whole chart, so it keeps reporting the first block at 10.

How this uses the pattern

Keep every landed block as a triple of left edge, right edge and top. For each new block, scan the landed list, take the highest top among blocks that pass the strict overlap test, and land the block at that base plus its side. Append the new triple, then fold its top into a running maximum before recording the answer.

Falling Squares (LC 699): Interval Maxima Without a Segment Tree

Click "Run" to execute your code

The Block angle

Square-tagged problem lists are mostly Medium, and Falling Squares is the Hard that shows up on them. Block runs coding as pairing and scores working code before clever code, so spend the hour on the quadratic sweep. Store each landed block as left, right and top, scan the ones the new block overlaps, and land it on the tallest. Mention the segment tree out loud and build it only when asked. Take care with the overlap test, because a block whose left edge equals another's right edge sits beside it and a non-strict comparison stacks it anyway. A natural second part raises the scale, such as "now the chart holds a hundred thousand campaigns," which calls for coordinate compression.

Take it further

A second part scales the chart to a hundred thousand campaigns, so the quadratic scan has to go. Collect every left and right edge, sort the distinct values, and give each one an index, which turns the axis into at most 2n cells. Build a segment tree over those cells that answers "tallest top in this range" and applies "raise this range to at least h". Each drop becomes one range query for the base and one range update for the new top, both logarithmic, and the running maximum works exactly as before. (Worked in the solution.)

Key Takeaways

✓Block's array rounds go beyond the rolling window into classic problems with a light payments framing, such as a batch of strings sent through a one-field API, references on a reconciliation feed, or campaigns on a dashboard chart. Look past the framing and name the structure.
✓Frame variable-length data with its length. A delimiter fails the moment a seller types it, while a count followed by exactly that many characters round-trips anything, including a note full of markers.
✓Look for the algebra before the loop. Rewriting the pair condition so each side depends on one position turns a quadratic comparison into one hash-map pass, the same move behind the ledger prefix-sum count.
✓Get the plain version working and mention the faster one. A two-flips-per-round pancake sort and a quadratic interval scan are finished answers in a pairing round, and the segment tree can wait until a follow-up raises the scale.

Next up:Graphs & Trees Premium

The next lesson and 9 more Block lessons are Premium. $49 a year, less than $1 a week · Cancel anytime

How Block frames these

Asked at Block

Encode and Decode Strings (LC 271): A Length-Prefixed Wire Format

Problem

Encode and Decode Strings (LC 271): A Length-Prefixed Wire Format

Count Nice Pairs (LC 1814): Canonical Key, One Hash Map

Problem

Count Nice Pairs (LC 1814): Canonical Key, One Hash Map

Pancake Sorting (LC 969): Sort With Prefix Reversals

Problem

Pancake Sorting (LC 969): Sort With Prefix Reversals

Falling Squares (LC 699): Interval Maxima Without a Segment Tree

Problem

Falling Squares (LC 699): Interval Maxima Without a Segment Tree

Key Takeaways

Know what Block asks before you walk in.