Without Whitespaces
Reported by candidates from Postman's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The data structure this Postman OA hinges on is a plain DP array, one slot per prefix of the string. Postman reported it in September 2019, and it looks like a string-splitting problem until you see it's counting. You get a digit string, a cap c, and you count the ways to cut it into numbers with no leading zeros, each at most c, answer mod 10^k. Example 1 gives 64 for a seven-digit string, which is 2^6 cuts, so nothing is excluded there. If you blank on the recurrence, StealthCoder is the invisible safety net running during the live OA.
The problem
You are given integers n, c, and k, together with a decimal digit string s of length n. Count how many arrays of nonnegative integers could have produced s when their usual decimal representations were printed consecutively without separators. Every array element must be no greater than c, and no element may have a leading zero except for the value 0 itself. The array may contain any positive number of elements. Return the number of valid arrays modulo 10^k. Function countArrays(n: int, c: long, k: int, s: String) → long Examples Example 1 n = 7 c = 1234567 k = 9 s = "1234567" return = 64 There are 64 valid ways to split the seven-digit string into one or more values no greater than 1234567. The result remains 64 modulo 10^9. Example 2 n = 2 c = 12 k = 3 s = "12" return = 2 The two valid arrays are [12] and [1, 2]. Constraints 1 ≤ n = s.length ≤ 10^4 1 ≤ c ≤ 10^9 1 ≤ k ≤ 18 s contains only decimal digits.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Define dp[i] as the number of ways to split the first i characters. dp[0] = 1. For each i, try every last piece s[j..i-1]. The piece is valid if it has no leading zero (unless it's exactly "0") and its value is at most c. Since c is at most 10^9, a valid piece has at most 10 digits, so the inner loop is capped at 10 and the total work is about 10n. Pitfalls: a piece starting with '0' is only valid when its length is 1. Compare numeric values with a long, not an int. The modulus is 10^k with k up to 18, so adding is safe in a long, but never multiply. Reduce after every addition. The answer is dp[n]. If you freeze, StealthCoder can hand you this recurrence mid-assessment, but the recurrence is only five lines.
Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.
You can drill Without Whitespaces 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 for the candidate who got the OA invite this morning and has 72 hours, not six months.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Postman's OA.
Postman reuses patterns across OAs. Made for the candidate who got the OA invite this morning and has 72 hours, not six months. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Without Whitespaces FAQ
What's the trick in the Postman Without Whitespaces problem?+
Treat it as counting splits with a 1D DP over prefixes. dp[i] sums dp[j] for every valid last piece s[j..i-1]. Validity means no leading zero (except "0") and value at most c. That's the whole problem.
How hard is it really?+
Medium. The idea is a standard partition-counting DP, similar to decode ways. The traps are the leading zero rule, the large modulus 10^k, and bounding the inner loop so it doesn't go quadratic.
Why is the inner loop only about 10 steps?+
Because c is at most 10^9, any piece longer than 10 digits must exceed c. Stop extending the piece once its length passes the digit count of c or its value goes above c. That makes the solution O(10n) instead of O(n^2).
Do I need big integers for modulo 10^k?+
No. k is at most 18, so 10^18 fits in a signed 64-bit long. The DP only adds, so each sum stays under 2 * 10^18, which also fits. Take the mod after each addition and you're safe.
How do I prepare for this in 48 hours?+
Solve decode-ways style DPs until the recurrence is automatic. Then hand-run the two examples here, including the "12" case giving 2. Test strings with zeros like "1001" and a tiny c to confirm your leading-zero and bound checks.