How should I practice Streaming Triple Packing by Size Threshold?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Streaming Triple Packing by Size Threshold associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Streaming Triple Packing by Size Threshold

Google● MediumNEW GRADONSITE INTERVIEW

Learn

Problem statement

Items arrive on a conveyor belt one at a time. sizes[i] is the positive integer size of the next item.

Keep every unpacked item. After each arrival, if three unpacked sizes a <= b <= c satisfy c - a < threshold, immediately pack and remove one such triple.

When more than one triple is possible, choose the lexicographically smallest sorted triple. Return every packed triple, with each triple sorted, in the order it is packed. Items left unpacked after the final arrival are not returned.

Function

packTriples(sizes: int[], threshold: int) → int[][]

Examples

Example 1

sizes = [5,1,4,3,9,2]threshold = 3return = [[3,4,5]]

After size 3 arrives, the sorted available sizes are [1,3,4,5]. Triple [3,4,5] has range 2, which is strictly below 3, so it is packed. The remaining values never form another valid triple.

Example 2

sizes = [1,2,3,10,11,12]threshold = 3return = [[1,2,3],[10,11,12]]

Each consecutive block of three has range 2 and is packed as soon as its third item arrives.

Example 3

sizes = [0,10,20,11]threshold = 15return = [[0,10,11]]

When 11 arrives, both [0,10,11] and [10,11,20] are valid. The lexicographically smaller triple [0,10,11] is chosen.

Constraints

1 <= sizes.length <= 5000.
0 <= sizes[i] <= 1000000000.
1 <= threshold <= 1000000000.