EF-T01: Stable Case-Insensitive Label Groups

Exercise contract#

Given a sequence of ASCII labels, return groups of labels that are equal after converting ASCII A-Z to a-z. Groups must appear in the order their first member appears. Within each group, preserve every original label's spelling and input order. Empty strings are valid labels. Duplicate labels remain separate output entries. Return an empty list for empty input. Reject a non-ASCII label; Unicode case folding and normalization are outside this exercise.

Constraints

• 0 <= number of labels <= 100,000.
• Each label is an ASCII string with length at most 100; the empty string is valid.
• Case-insensitive equality changes only ASCII letters A-Z to a-z.
• Do not sort the input, groups, or group contents.
• Preserve duplicate occurrences and original spelling exactly.

Examples

["Api", "DB", "api", "Cache", "db"]

[["Api", "api"], ["DB", "db"], ["Cache"]]The normalized keys are api, db, api, cache, db. The first api creates group zero, the first db creates group one, and cache creates group two.

["", "A", "", "a", "A"]

[["", ""], ["A", "a", "A"]]The empty label is a valid key, and duplicate labels remain present in their original order.

Derive the approach#

Baseline: For each label, scan the groups already created and compare its normalized form with the first member's normalized form. This preserves order but can compare the same keys repeatedly, taking quadratic time in the number of labels.

1. The output needs first-seen group order, so append a group only when its normalized key appears for the first time.
2. The output also needs original spelling and occurrence order, so normalize only the lookup key and append the untouched label.
3. Map each normalized key to the index of its group in the output array.
4. On a repeated key, append to the existing group; on a new key, record the next output index before appending the new group.
5. Validate the ASCII boundary before normalization so the implementation does not imply broader text equivalence.

Time

O(C) expected time, where C is the total number of ASCII characters plus the number of labels.

Space

O(C) output space and O(U) map entries for U distinct normalized labels, excluding normalized-key storage already counted within O(C).

Assumptions

Map operations are expected O(1), ASCII lowercasing is linear in label length, and the output must retain every input occurrence.

Three-stage hint ladder#

Reveal only the smallest useful step. Any revealed hint should be recorded as assistance.

Reference solutions#

Open these after an attempt or when working in Learn mode. Viewing either solution is not independent-success evidence.

def group_ascii_labels(labels):
    groups = []
    group_index = {}

    for label in labels:
        if not isinstance(label, str) or not label.isascii():
            raise ValueError("labels must be ASCII strings")
        key = label.lower()
        if key not in group_index:
            group_index[key] = len(groups)
            groups.append([])
        groups[group_index[key]].append(label)

    return groups

static List<List<String>> groupAsciiLabels(List<String> labels) {
    List<List<String>> groups = new ArrayList<>();
    Map<String, Integer> groupIndex = new HashMap<>();

    for (String label : labels) {
        if (label == null || !label.chars().allMatch(character -> character < 128)) {
            throw new IllegalArgumentException("labels must be ASCII strings");
        }
        String key = label.toLowerCase(Locale.ROOT);
        Integer index = groupIndex.get(key);
        if (index == null) {
            index = groups.size();
            groupIndex.put(key, index);
            groups.add(new ArrayList<>());
        }
        groups.get(index).add(label);
    }
    return groups;
}

Deterministic test plan#

Transfer and follow-ups#

• If Unicode case folding or normalization is required, define the normalization form and locale behavior before changing the key function.
• If groups must be sorted, identify whether sorting applies to normalized keys, original labels, or both; this changes the order contract and complexity.

Explain why the map stores output indices rather than complete groups, and why normalization applies to keys but not output values.

Authorship and review#

Original Engineering Foundry prompt, examples, explanations, and verification programs using standard algorithmic techniques. This is not attributed to an employer and is not evidence of interview frequency.

Engineering Foundry original · Codex self-review on 2026-09-05 · independent human editorial review is not claimed.

Evidence IDs: RA-DSA-CURRICULUM-EXPANSION-2026-09