How should I practice Generate Complete Inputs for a Supplied Classifier?

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

Is Generate Complete Inputs for a Supplied Classifier associated with General Motors?

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

Generate Complete Inputs for a Supplied Classifier

General Motors● MediumFULLTIMEONSITE INTERVIEW

Problem statement

An integer classifier is already supplied. For this exercise, assume its input domain is every integer x from 0 through maxValue, inclusive. Row i of ranges contains an inclusive interval [low, high].

The supplied classifier checks rows in input order and returns the index of the first interval containing x. If no row contains x, it returns the default label ranges.length:

classify(x):
    for i = 0 .. ranges.length - 1:
        if ranges[i][0] <= x <= ranges[i][1]:
            return i
    return ranges.length

Implement the input generator. Return the smallest possible collection of domain integers whose classifier results cover every reachable label. A label is reachable only if some domain integer actually produces it; an interval completely hidden by earlier rows may be unreachable.

For deterministic output, use exactly the smallest integer producing each reachable label and list those witnesses in increasing label order, including the default label last if it is reachable. The returned numbers therefore need not be numerically sorted. Do not output unreachable labels or any extra witness. The classifier is fixed; do not reorder, merge or modify its rows.

Each generated input produces exactly one label, so one witness for each reachable label is both necessary and sufficient for minimum collection size. Your function returns those generated inputs, not the classifier labels and not the classifier implementation.

Function

generateClassifierInputs(maxValue: int, ranges: int[][]) → int[]

Examples

Example 1

maxValue = 6ranges = [[4,6],[1,5]]return = [4,1,0]

Label0first occurs at4. Label1first occurs at1, because4and5are captured by row0. The default label2first occurs at0. Return[4,1,0]in label order.

Example 2

maxValue = 4ranges = [[0,4],[1,2]]return = [0]

Every domain input is captured by row0. Row1and the default are unreachable, so the minimum complete generated collection is[0].

Example 3

maxValue = 0ranges = []return = [0]

With no classifier rules, the only input0produces the default label0. Generate[0].

Constraints

0 <= maxValue <= 20000.
0 <= ranges.length <= 200.
Every range row contains exactly 2 integers.
Every range endpoint is between 0 and 20000, inclusive.
For every row [low, high], low <= high <= maxValue.
Intervals may overlap, share endpoints or be identical.