DescriptionQ589
Q589FWASIC interview problem
Add decimal lists from a fixed pool
TechniquesFWLinked listsFixed memoryValidationAtomic output
DifficultyMedium
TopicFirmware Algorithms
LanguageC
Requirements4 checkpoints
01
Problem
Add two least-significant-digit-first decimal lists from a bounded SRAM node pool into a separate fixed destination pool without partial output.
Type declarationC
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.Example input and output
Use this case to check your interpretationInput
LSF decimal list A=[9,9] (99); B=[1]Output
destination list=[0,0,1] (100)Explanation
The carry propagates through both existing digits and allocates one final canonical digit after the sizing pass confirms capacity.
02
Requirements (4)
- Reject bad pointers, overlap, bad digits or links, cycles, and any source node shared by both lists.
- Use no heap or recursion and at most two 32-bit visited masks for source validation.
- Run a sizing carry pass before writing and return no-space without changing the destination or output metadata.
- Write a canonical consecutive result, propagating final carry and representing zero with one zero node.