Skip to question
SystemVerilogDesignVerificationFirmwareArchitectureASIC Interview Questions→
/Interview questions/Group diagnostic tags without dynamic allocation

Q115·Free·Firmware

Group diagnostic tags without dynamic allocation

Difficulty
Medium
Topic
Strings
Language
SV
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.
endfunction
Reviewed 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

  1. 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.
  2. Use the exact tag length plus 26 letter counts as the grouping key rather than relying on a hash alone.
  3. Order groups by the first member seen, preserve member order, and publish group_start[0]=0 and group_start[group_count]=count.
  4. Use only bounded workspace and leave all outputs byte-for-byte unchanged for every invalid argument or malformed tag.
Exact question handoffPractice Q115

Solve it in the question bank, keep your progress, and reveal the reviewed solution when your access allows.

Open in question bank →
Solution accessEach time you open this Solution, one Practice Credit is used; it is not permanently unlocked. Premium Solution content also uses one credit per opening.
Continue learning

Firmware Guide

Review algorithms, data structures, fixed-memory reasoning, concurrency, and silicon bring-up.

  • Strings
  • Anagrams
  • Fixed storage
Firmware Guide →
Continue practicing

Related questions

Q100 · Hardware-Software IntegrationPredict and safely read a build-tag prefix serviceMedium→Q064 · Firmware AlgorithmsEnumerate calibration sums with fixed memoryMedium→Q738 · StringsFind the first substringEasyP→Q1115 · Firmware & ValidationBounded byte-string palindrome checkEasyP→
ASIC.FYI · Learn silicon end to end.info@asic.fyi