DescriptionQ347
Q347FWASIC interview problem
Enumerate calibration sums with fixed memory
TechniquesFWBacktrackingFixed memoryCapacityWatchdog
DifficultyMedium
TopicFirmware Algorithms
LanguageC
Requirements4 checkpoints
01
Problem
Enumerate dictionary-ordered combinations of distinct positive calibration values that sum to a target, allowing reuse without heap allocation or partial output.
Type declarationC
typedef struct { uint32_t first; uint8_t len; } combo_ref_t;
typedef enum { CS_OK, CS_BAD_ARG, CS_NO_SPACE, CS_SEARCH_LIMIT } cs_status_t;
cs_status_t calibration_sets(const uint8_t *value, size_t n,
uint8_t target, uint8_t *flat, size_t flat_cap,
combo_ref_t *ref, size_t ref_cap,
size_t *need_flat, size_t *need_ref);
// Search limit: 20000 entered states per pass.Example input and output
Use this case to check your interpretationInput
values=[2,3,6,7]; target=7Output
combinations=[[2,2,3],[7]]Explanation
Values may be reused within a combination, but traversal indices keep combinations ordered and prevent permutation duplicates.
02
Requirements (4)
- Validate, copy, and sort 1 through 12 distinct values from 1 through 32 and a target from 1 through 64.
- Use an explicit stack of at most 65 frames and stop before entering search state 20001.
- Run identical sizing and writing traversals, checking every count and output-index calculation.
- Publish required sizes only for success or no-space and preserve both destination buffers on every non-success return.