Q115FreeFirmware
Group diagnostic tags without dynamic allocation
Interview prompt
Question
Group as many as 32 fixed-record lowercase diagnostic tags into anagram families without heap allocation, while preserving both first-group order and member input order.
Candidate starting point
Implementation scaffold
typedef struct { byte text[17]; } diag_tag_t;
typedef struct {
byte unsigned len;
byte unsigned letter_count[26];
} tag_signature_t;
function automatic bit build_signature(
input diag_tag_t tag,
output tag_signature_t signature
);
// Implement here: build_signature.
endfunction
function automatic bit same_signature(
input tag_signature_t left,
input tag_signature_t right
);
// Implement here: same_signature.
endfunction
// ref is required for the output aggregates: an output formal is copy-out and
// cannot preserve its caller value on failure. This corrected interface makes
// the stated all-or-nothing contract implementable.
function automatic bit group_tags(
input diag_tag_t tags[32],
input int unsigned count,
ref byte unsigned order[32],
ref byte unsigned group_start[33],
ref int unsigned group_count
);
tag_signature_t signatures[32];
byte unsigned staged_order[32];
byte unsigned staged_start[33];
bit assigned[32];
int unsigned write_index = 0;
int unsigned staged_group_count = 0;
// Implement here: validate, group by stable signatures, and publish staged outputs.
endfunctionReviewed example
Trace one case
Input
tags=["eat","tea","tan","ate"]Expected output
groups=[["eat","tea","ate"],["tan"]]The letter-count key groups the three anagrams, while first-group and member encounter order remain unchanged.
What to cover
Requirements
- Validate every active record before writing: a terminator must occur within 17 bytes, length must be 1 through 16, and all characters must be lowercase ASCII.
- Use the exact tag length plus 26 letter counts as the grouping key rather than relying on a hash alone.
- Order groups by the first member seen, preserve member order, and publish group_start[0]=0 and group_start[group_count]=count.
- Use only bounded workspace and leave all outputs byte-for-byte unchanged for every invalid argument or malformed tag.
