A set of dynamic programming problems commonly appearing in Snowflake and similar companies' OAs (HackerRank format, Java or C++ only). Reported problems include: (1) Array Halving: given an array and positive integer d, repeatedly extract the maximum element, halve it, and put it back — d times total; return the sum remaining. Naive sort+binary-search is O(d log n) and TLEs when d=2,000,000 and n=100,000. (2) Bit Manipulation / Subset Selection: exhaustive enumeration of 2^36 subsets is infeasible; requires Inclusion-Exclusion or advanced filtering, but even that only passes ~50% of cases. (3) Constrained 0-1 Knapsack DP: capacity c can reach 10^6, making the standard O(n·c) DP table exceed memory; must re-dimension the DP state (e.g., dp over the number of items t rather than capacity). (4) Non-overlapping Intervals / Call Scheduling DP: given calls with start/end times and values, find the maximum total value of non-overlapping calls; sort by start time, use a TreeMap keyed by end time to binary-search for the latest non-overlapping predecessor.
| Approach | Notes |
|---|---|
| Greedy + sort for non-overlapping intervals | Sorting by end time and greedily selecting compatible intervals finds the maximum count but not maximum value; DP is required when values differ. |
| Inclusion-Exclusion for bit manipulation subset problem | Reduces brute-force 2^36 search but still only passes ~50% of test cases in reported attempts; problem may be #P-hard in general. |
| Sliding window for vowel substring subproblem | First find all-vowel substrings, then apply sliding window within each; works for the substring counting variant but is a different problem than the DP knapsack. |
Common mistakes: Using sort + binary-search re-insertion for array halving instead of a max-heap, leading to TLE; Implementing standard 0-1 knapsack with capacity as DP dimension when c=10^6, causing MLE; Attempting brute-force 2^36 enumeration for the bit manipulation problem; Having the correct algorithm for non-overlapping intervals but being unable to implement it in the required language (Java/C++) due to unfamiliarity; Running out of time on the third problem after spending too long on the first two
What passers do: Being familiar enough with DP patterns (knapsack, interval scheduling) to code them quickly and correctly; Practicing with past OA problems found on candidate-report forums — candidates who had seen the exact problems beforehand passed; Using a max-heap (priority queue) for the array halving problem rather than sort+binary-search; Using TreeMap with end time as key to efficiently find the best non-overlapping predecessor in the call scheduling DP
Why people fail: Recognizing the correct approach but failing to implement it correctly in Java/C++ under time pressure; Getting the knapsack DP dimension wrong (capacity instead of item count) and running out of memory; Only passing ~50% of test cases on the bit manipulation problem despite applying Inclusion-Exclusion; Having seen the problems before but still failing to pass all test cases due to subtle constraints
Edge cases probed: d up to 2,000,000 with array size 100,000 — O(d log n) with naive sort+binary-search TLEs; Knapsack capacity c up to 10^6 — standard O(n*c) DP exceeds memory; Bit enumeration space 2^36 — brute force is completely infeasible; Uniqueness of call start times (asked in thread reply: 'are start times unique?')
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 103 Snowflake questions, refreshed monthly from new candidate reports.