Skip to question
asic.fyi

Hardware interview practice

Add decimal lists from a fixed pool

MediumFirmware AlgorithmsC

Add two least-significant-digit-first decimal lists from a bounded SRAM node pool into a separate fixed destination pool without partial output.

Starting point

Question code

typedef struct { uint8_t digit; uint8_t next; } digit_node_t;
typedef enum { ADD_OK, ADD_BAD_ARG, ADD_BAD_LIST, ADD_NO_SPACE } add_status_t;
add_status_t add_decimal_lists(const digit_node_t *src, size_t src_count,
    uint8_t a_head, uint8_t b_head, digit_node_t *dst, size_t dst_cap,
    uint8_t *dst_head, size_t *dst_used);
// 0xFF ends a list; src_count is 1..32.
Reviewed example

Work through one case

Input
LSF decimal list A=[9,9] (99); B=[1]
Expected output
destination list=[0,0,1] (100)

The carry propagates through both existing digits and allocates one final canonical digit after the sizing pass confirms capacity.

What to cover

Requirements

  1. Reject bad pointers, overlap, bad digits or links, cycles, and any source node shared by both lists.
  2. Use no heap or recursion and at most two 32-bit visited masks for source validation.
  3. Run a sizing carry pass before writing and return no-space without changing the destination or output metadata.
  4. Write a canonical consecutive result, propagating final carry and representing zero with one zero node.
Continue practicing
Firmware AlgorithmsEnumerate calibration sums with fixed memoryFirmware AlgorithmsParse a bounded Roman board revisionFirmware AlgorithmsFind device-tree depth without recursion