Join Sources with Lagged Destination Timestamps
Reported by candidates from Pinterest's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Pinterest sent this one in August 2024, and the detail that matters is the window: a destination timestamp is 0, 1, or 2 seconds after the source timestamp. That's a keyed join with a tiny time band. It looks like SQL dressed up as an array problem. If you've got an OA coming, expect the naive double loop to be the trap, since both tables can hit 20000 rows. StealthCoder sits invisibly on your screen as a safety net if you blank mid-assessment, but the idea here is short enough to hold in your head.
The problem
You are given two materialized tables. Each row of sourceRows is [source, destination, timestamp]. Each row of destinationRows is [destination, timestamp]. Timestamps are nonnegative integer seconds encoded as decimal strings. A source row matches a destination row when their destination values are equal and the destination-row timestamp is zero, one, or two seconds after the source-row timestamp. Equivalently, if the timestamps are sourceTime and destinationTime, then 0 <= destinationTime - sourceTime <= 2. Process destinationRows in input order. For each destination row, append the source of every matching source row in sourceRows input order. Preserve duplicate row occurrences. Rows with no match append nothing. Return the resulting list of source strings. Function matchLaggedSources(sourceRows: String[][], destinationRows: String[][]) → String[] Examples Example 1 sourceRows = [["A","X","10"],["B","X","12"],["C","Y","9"]] destinationRows = [["X","12"],["Y","10"]] return = ["A","B","C"] For [X, 12], sources A and B lag by two and zero seconds. For [Y, 10], source C lags by one second. Example 2 sourceRows = [["first","D","5"],["other","Q","6"],["second","D","6"],["first","D","5"]] destinationRows = [["D","7"],["D","4"],["D","7"]] return = ["first","second","first","first","second","first"] The two identical source rows remain distinct occurrences. The middle destination row has no earlier source within two seconds. Repeating the first destination row repeats its three matches. Example 3 sourceRows = [["late","A","9"],["edge","A","5"],["wrong","B","6"]] destinationRows = [["A","7"]] return = ["edge"] edge is exactly two seconds earlier. late occurs after the destination row, and wrong has another destination. Constraints 1 <= sourceRows.length, destinationRows.length <= 20000 Every source row contains exactly three strings, and every destination row contains exactly two strings. Source and destination strings are non-empty and contain only letters, digits, underscores, and hyphens. Every timestamp is a decimal integer in [0, 10^9]. The returned list contains at most 200000 source occurrences.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Group source rows by destination in a hash map, keeping each group in input order. Each entry stores the timestamp and the source string. For every destination row, look up its group and collect sources where 0 <= destTime - sourceTime <= 2. Scanning a whole group per destination can degrade when one destination dominates, so the safer move is to key by destination plus timestamp. For a destination at time t, check keys t, t-1, t-2. Source order breaks, though. Each bucket holds sources in input order, but merging three buckets needs a sort by original index. Store the index with each source and sort the matches, or merge them. Pitfalls: parse timestamps as integers, keep duplicates as separate occurrences, and don't dedupe. Output can reach 200000 entries, so don't build strings repeatedly. If you freeze live, StealthCoder is the hedge, but this is a hash-map join.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Join Sources with Lagged Destination Timestamps cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Pinterest's OA.
Pinterest reuses patterns across OAs. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Join Sources with Lagged Destination Timestamps FAQ
What's the trick in this Pinterest OA problem?+
Index the source rows in a hash map instead of looping source by destination. Key by destination, then by timestamp. For each destination row at time t, check source timestamps t, t-1 and t-2. That turns a 20000 by 20000 scan into a few lookups per row.
How do I keep the output in source input order?+
Store each source's original index with it. For one destination row, gather matches from the three timestamp buckets, then sort by index before appending the source strings. Each bucket is already ordered, so merging three sorted lists also works and avoids a full sort.
Do duplicate rows count more than once?+
Yes. Example 2 shows two identical source rows producing two separate outputs, and a repeated destination row repeats all its matches. Never use a set for sources or destinations. Store every occurrence in your buckets and emit each one.
How hard is this really?+
Easy to medium. The logic is simple, but the constraints punish a nested loop in the worst case. The real risks are ordering across the three timestamp buckets and forgetting that timestamps are strings that need integer parsing.
How do I prepare in 48 hours?+
Write this one from scratch twice. Practice hash-map grouping, composite keys like destination plus time, and a quick check of the edges: exactly 2 seconds earlier matches, a source after the destination doesn't, and a different destination doesn't. Then test with duplicates.