Skip to question
asic.fyi

Hardware interview practice

Enumerate calibration sums with fixed memory

MediumFirmware AlgorithmsC

Enumerate dictionary-ordered combinations of distinct positive calibration values that sum to a target, allowing reuse without heap allocation or partial output.

Starting point

Question code

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.
Reviewed example

Work through one case

Input
values=[2,3,6,7]; target=7
Expected output
combinations=[[2,2,3],[7]]

Values may be reused within a combination, but traversal indices keep combinations ordered and prevent permutation duplicates.

What to cover

Requirements

  1. Validate, copy, and sort 1 through 12 distinct values from 1 through 32 and a target from 1 through 64.
  2. Use an explicit stack of at most 65 frames and stop before entering search state 20001.
  3. Run identical sizing and writing traversals, checking every count and output-index calculation.
  4. Publish required sizes only for success or no-space and preserve both destination buffers on every non-success return.
Continue practicing
Firmware AlgorithmsAdd decimal lists from a fixed poolFirmware AlgorithmsParse a bounded Roman board revisionFirmware AlgorithmsFind device-tree depth without recursion