Prefix Longest Consecutive-Value Runs
Reported by candidates from ZipRecruiter's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The whole ZipRecruiter question from April 2022 comes down to one hash structure that remembers run lengths at the edges of each consecutive block. If you're taking this OA soon, that's the thing to lock in. You get an array, you walk it left to right, and after every value you report the longest consecutive run in the distinct set so far. The hinted pattern says dynamic programming, but the real work is a hash map with merging. StealthCoder sits invisibly on your screen as a safety net if your mind goes blank mid-assessment, but the idea below is short enough to carry in your head.
The problem
Process values from left to right. For every prefix, consider the set of distinct values seen so far and find the longest run of consecutive integers in that set. Return one run length for every prefix. Repeated values do not extend a run. Function prefixConsecutiveRuns(values: int[]) → int[] Examples Example 1 values = [2,1,3] return = [1,2,3] Each new value extends the only consecutive component. Example 2 values = [3,1,2] return = [1,1,3] The final value joins two singleton components. Constraints 1 <= values.length <= 2000 -1000000000 <= values[i] <= 1000000000
Reported by candidates. Source: FastPrep
Pattern and pitfall
Keep a hash map from value to the length of the run that value belongs to, only trusted at run endpoints. When a new value x arrives, skip it if it's already in the map. Otherwise read left = map[x-1] and right = map[x+1], defaulting to 0. The new length is left + right + 1. Write that length to x, to x - left, and to x + right. Those are the two ends of the merged run. Track a running max and push it into the answer after each element. Each step is O(1), so the total is O(n). The classic pitfall is forgetting the duplicate check, which corrupts lengths. Another is updating interior values, which is unnecessary. Values reach 1e9 in magnitude, so don't use an array indexed by value. If you freeze during the live OA, StealthCoder can surface this merge logic in real time, but you should be able to write it from the description alone.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Prefix Longest Consecutive-Value Runs 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. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass ZipRecruiter's OA.
ZipRecruiter reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Prefix Longest Consecutive-Value Runs FAQ
How hard is the ZipRecruiter prefix consecutive runs problem really?+
Medium. The idea is short once you know it: a hash map storing run length at the endpoints. The difficulty is spotting that you don't need to recompute from scratch each prefix. With n up to 2000 even a slower approach might pass, but the O(n) merge is cleaner.
What's the trick to solving it?+
Store the run length only at the two endpoints of each consecutive block. When a new value x arrives, look up x-1 and x+1, add their lengths plus one, then update the new left and right endpoints. Update the running max and append it to the output.
Do duplicate values change the answer?+
No. The problem says repeated values don't extend a run. Check whether x is already in your map before doing anything. If it is, just append the current max again and move on. Skipping this check gives wrong lengths.
Is this really dynamic programming or something else?+
It's labeled dynamic programming because each answer builds on the previous state. In practice it's a hash map plus interval merging, similar to union-find without the explicit structure. Think of it as incremental state, not a DP table.
How do I prepare for this in 48 hours?+
Code the endpoint-length hash map version of longest consecutive sequence from memory, then adapt it to emit the max after every element. Test on [3,1,2] to confirm the merge case returns [1,1,3]. Also try a duplicate-heavy input and negative values.