Streamed Scalar Item Triplets
Google● MediumNEW GRADPHONE SCREENONSITE INTERVIEWProblem statement
Items arrive one at a time on a belt. arrivals[i] is the integer size of item ID i. Equal sizes still represent separate items.
Keep unconsumed items. Immediately after each arrival, if any three available items satisfy max(size) - min(size) < threshold, package exactly one triple and remove those items from future consideration. A difference equal to the threshold does not qualify.
For deterministic practice, sort available items by (size, item ID). Choose the first qualifying consecutive triple in that order, and return its three item IDs in increasing ID order. If none qualifies, return an empty row for that arrival. At most one group can form per arrival because the preceding state had no valid triple.
Return one row for every arrival. This finite batch represents successive calls to the reported class method: no later item may be used early, and unmatched items are not packaged at the end. If threshold is zero, no triple qualifies.
Function
packageScalarArrivals(arrivals: int[], threshold: int) → int[][]Examples
Example 1
arrivals = [5,8,6,7]threshold = 3return = [[],[],[],[0,2,3]]The first three items have range 3, so they do not fit. Item 3 creates the qualifying sizes 5, 6, 7, whose IDs are [0,2,3].
Example 2
arrivals = [9,1,3,2,10,11]threshold = 3return = [[],[],[],[1,2,3],[],[0,4,5]]When item 3 arrives, sizes 1, 2, 3 form a package with IDs [1,2,3]. After item 5 arrives, the remaining sizes 9, 10, 11 form a second package.
Example 3
arrivals = [4,4,4,4]threshold = 1return = [[],[],[0,1,2],[]]The first three distinct items of size 4 form one package. The fourth item remains unpaired.
Constraints
0 <= arrivals.length <= 100.-10^6 <= arrivals[i] <= 10^6.0 <= threshold <= 10^6.- Arrival order may be arbitrary, and duplicate sizes are allowed.