Implement a function that returns all unique triplets (i, j, k) of indices whose values sum to a target T, with strong performance and deduplication guarantees. Inputs: integer array A of length n (2 ≤ n ≤ 200,000), values in [−10^9, 10^9]; integer T (|T| ≤ 10^9). Outputs: list of triplets of values (a, b, c) in nondecreasing order per triplet and lexicographically sorted overall; no duplicate triplets allowed. Constraints and sub-questions: 1) Provide an O(n^2) time, O(1) extra-space (beyond output) solution for T=0 using sorting + two pointers. Prove correctness of your duplicate-skipping logic in adversarial cases like A=[0,0,0,0,0]. 2) Generalize to arbitrary T and to k-sum (k≥4) with pruning. What complexity do you achieve and how do you prevent integer overflow? 3) Streaming/scale twist: If n can be 5×10^6 and memory caps at 512 MB, outline an external-memory approach (e.g., chunked sort + k-way merge or hashed buckets) and estimate I/O complexity. How would you approximate the count of unique triplets with a given T using sketches if exact enumeration is infeasible? 4) Bonus: Given frequency map F of values instead of A, compute the number of unique triplets summing to T in O(m^2) where m=|support(F)|, carefully handling cases where values repeat (e.g., x=x=y or x=y=z). Provide formulas and edge-case handling.

This question evaluates algorithmic problem-solving skills in array processing, deduplication and combinatorial counting, external-memory and streaming algorithm design, and complexity analysis including integer overflow considerations.

How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Snowflake during technical interviews.

Solve and optimize 3Sum and variants at scale | Snowflake Interview Question

Implement a function that returns all unique triplets (i, j, k) of indices whose values sum to a target T, with strong performance and deduplication guarantees. Inputs: integer array A of length n (2 ≤ n ≤ 200,000), values in [−10^9, 10^9]; integer T (|T| ≤ 10^9). Outputs: list of triplets of values (a, b, c) in nondecreasing order per triplet and lexicographically sorted overall; no duplicate triplets allowed. Constraints and sub-questions:

Provide an O(n^2) time, O(1) extra-space (beyond output) solution for T=0 using sorting + two pointers. Prove correctness of your duplicate-skipping logic in adversarial cases like A=[0,0,0,0,0].
Generalize to arbitrary T and to k-sum (k≥4) with pruning. What complexity do you achieve and how do you prevent integer overflow?
Streaming/scale twist: If n can be 5×10^6 and memory caps at 512 MB, outline an external-memory approach (e.g., chunked sort + k-way merge or hashed buckets) and estimate I/O complexity. How would you approximate the count of unique triplets with a given T using sketches if exact enumeration is infeasible?
Bonus: Given frequency map F of values instead of A, compute the number of unique triplets summing to T in O(m^2) where m=|support(F)|, carefully handling cases where values repeat (e.g., x=x=y or x=y=z). Provide formulas and edge-case handling.

Provide an O(n^2) time, O(1) extra-space (beyond output) solution for T=0 using sorting + two pointers. Prove correctness of your duplicate-skipping logic in adversarial cases like A=[0,0,0,0,0].
Generalize to arbitrary T and to k-sum (k≥4) with pruning. What complexity do you achieve and how do you prevent integer overflow?
Streaming/scale twist: If n can be 5×10^6 and memory caps at 512 MB, outline an external-memory approach (e.g., chunked sort + k-way merge or hashed buckets) and estimate I/O complexity. How would you approximate the count of unique triplets with a given T using sketches if exact enumeration is infeasible?
Bonus: Given frequency map F of values instead of A, compute the number of unique triplets summing to T in O(m^2) where m=|support(F)|, carefully handling cases where values repeat (e.g., x=x=y or x=y=z). Provide formulas and edge-case handling.

Solve and optimize 3Sum and variants at scale

Quick Overview

Comments (0)

Solve and optimize 3Sum and variants at scale

Quick Overview

Comments (0)