Snowflake·Data Scientist·Onsite - Coding / Algorithms
- Implement an O(n^2) solution to find all unique triplets in an array that sum to zero, using sorting and two pointers. Prove your duplicate-skipping logic is correct on adversarial inputs like an array of all zeros.
- Generalize the triplet sum problem to an arbitrary target T and then to k-sum for k >= 4 with pruning. What time complexity do you achieve, and how do you prevent integer overflow when summing large values?
- If the array has 5 million elements and memory is capped at 512 MB, how would you approach finding all triplets using an external-memory strategy? What is the I/O complexity? And if exact enumeration is infeasible, how would you approximate the count of unique triplets using probabilistic sketches?
- Given a frequency map of values rather than the raw array, compute the number of unique triplets summing to a target T in O(m^2) time where m is the number of distinct values. Handle edge cases where two or all three values in a triplet are the same.
“The basic two-pointer approach I knew cold.”