DSA in C, built the way firmware actually uses it

Focus: portability across MCUs — never trust plain int/char width again.

• <stdint.h>: uint8_t, int16_t, uint32_t, etc. and why firmware code should always use them
• Signed vs unsigned overflow behavior, integer promotion
• sizeof, alignment basics, endianness (little vs big)
• const, volatile, static qualifiers

1. Write a program that prints sizeof for every stdint.h type on your target.
2. Detect the endianness of the machine at runtime using a union.
3. Show an example where uint8_t wraps silently and explain why that’s dangerous in a loop counter.

#include <stdint.h>
#include <stdio.h>

int is_little_endian(void) {
    uint32_t x = 1;
    return *((uint8_t *)&x) == 1;
}

int main(void) {
    printf("%s endian\n", is_little_endian() ? "Little" : "Big");
    printf("uint8_t=%zu uint16_t=%zu uint32_t=%zu\n",
           sizeof(uint8_t), sizeof(uint16_t), sizeof(uint32_t));
    return 0;
}

Focus: pointer arithmetic and function pointers — the backbone of ISR tables and callback-driven drivers.

• Pointer arithmetic on arrays, pointer vs array decay
• Pointer to pointer, const correctness with pointers
• Function pointers and function-pointer arrays (interrupt vector tables, callback dispatch)
• Void pointers for generic driver APIs

1. Swap two integers using only pointers, no third variable via arithmetic.
2. Traverse an array using pointer arithmetic instead of indexing.
3. Build a 4-entry “interrupt vector table” of function pointers and dispatch by index.

#include <stdio.h>

typedef void (*isr_t)(void);

void uart_isr(void)  { printf("UART interrupt\n"); }
void timer_isr(void) { printf("Timer interrupt\n"); }
void gpio_isr(void)  { printf("GPIO interrupt\n"); }
void default_isr(void){ printf("Unhandled interrupt\n"); }

isr_t vector_table[4] = { uart_isr, timer_isr, gpio_isr, default_isr };

void dispatch(uint8_t irq_num) {
    if (irq_num < 4) vector_table[irq_num]();
}

int main(void) {
    dispatch(1); /* -> Timer interrupt */
    return 0;
}

Focus: knowing exactly where your bytes live — .data, .bss, stack, or a memory-mapped region.

• 1D/2D arrays, row-major layout, address calculation
• Global/static vs stack arrays; why embedded code favors static buffers
• Array decay to pointer in function calls, passing array bounds explicitly

1. Reverse an array in place with O(1) extra memory.
2. Find min and max of an array in a single pass.
3. Given a 2D sensor grid uint16_t grid[ROWS][COLS], compute the flat index formula and verify it manually.

void reverse_array(uint16_t *buf, size_t len) {
    size_t i = 0, j = len - 1;
    while (i < j) {
        uint16_t tmp = buf[i];
        buf[i] = buf[j];
        buf[j] = tmp;
        i++; j--;
    }
}

Focus: parsing raw byte streams (UART/SPI payloads) without a buffer overflow.

• C strings and null termination, why library string calls can be dangerous on fixed buffers
• Writing bounded custom versions: my_strlen, my_strncpy
• Tokenizing a comma-separated sensor line without strtok‘s hidden state

1. Implement strlen and strcpy from scratch.
2. Parse "23.5,61,1013" (temp,humidity,pressure) into three variables without strtok.
3. Explain why gets() and unbounded strcpy() are banned in most firmware coding standards (e.g. MISRA C).

#include <stdint.h>
#include <stdlib.h>

/* returns number of fields parsed, max 8 */
int parse_csv(const char *line, int32_t *out, int max_fields) {
    int count = 0;
    const char *p = line;
    while (*p && count < max_fields) {
        char *end;
        out[count++] = strtol(p, &end, 10);
        if (*end == ',') p = end + 1; else break;
    }
    return count;
}

Focus: mapping C types directly onto hardware registers.

• struct padding/alignment, #pragma pack / __attribute__((packed))
• Unions for type punning (e.g. splitting a float into raw bytes)
• Bit-fields for register layouts, and volatile pointers to memory-mapped registers

1. Define a packed struct that models a UART control register with fields: enable(1), parity(2), stop_bits(1), reserved(4).
2. Use a union to inspect the raw bytes of a float.
3. Explain when the compiler is allowed to reorder/pad struct members and how packing avoids it.

#include <stdint.h>

typedef struct __attribute__((packed)) {
    uint8_t enable    : 1;
    uint8_t parity    : 2;
    uint8_t stop_bits : 1;
    uint8_t reserved  : 4;
} uart_ctrl_reg_t;

#define UART_CTRL (*(volatile uart_ctrl_reg_t *)0x4000C000UL)

void uart_enable(void) {
    UART_CTRL.enable = 1;
    UART_CTRL.parity = 0;
}

Focus: the single most-used skill in GPIO/register-level embedded code.

• Set / clear / toggle / check a bit using masks
• Brian Kernighan’s bit-count trick, power-of-two checks
• Shifts vs multiplication/division for fast fixed-point math

1. Write macros SET_BIT, CLR_BIT, TOGGLE_BIT, CHECK_BIT.
2. Count the number of set bits in a uint32_t register value.
3. Check whether a buffer size is a power of two (needed for fast ring-buffer masking — see Day 11).

#define SET_BIT(reg, bit)    ((reg) |=  (1U << (bit)))
#define CLR_BIT(reg, bit)    ((reg) &= ~(1U << (bit)))
#define TOGGLE_BIT(reg, bit) ((reg) ^=  (1U << (bit)))
#define CHECK_BIT(reg, bit)  (((reg) >> (bit)) & 1U)

uint8_t popcount(uint32_t n) {
    uint8_t count = 0;
    while (n) {
        n &= (n - 1);   /* clears the lowest set bit */
        count++;
    }
    return count;
}

int is_power_of_two(uint32_t n) {
    return n && !(n & (n - 1));
}

Focus: reasoning about time/space cost, and why embedded code prefers iteration over recursion.

• Big-O basics: O(1), O(log n), O(n), O(n log n), O(n²)
• Stack frames and why deep recursion is risky with a 1–4 KB task stack
• Review quiz: pointers, structs, bit-fields, arrays (Days 1–6)

1. State the time complexity of linear search, binary search, and bubble sort.
2. Convert a recursive factorial into an iterative one and explain the stack savings.
3. Re-derive Day 6’s popcount and Day 3’s reverse-array from memory, no notes.

/* Recursive: O(n) stack frames -- risky on a 1KB stack for large n */
uint32_t fact_recursive(uint8_t n) {
    return (n <= 1) ? 1 : n * fact_recursive(n - 1);
}

/* Iterative: O(1) stack usage -- preferred in firmware */
uint32_t fact_iterative(uint8_t n) {
    uint32_t result = 1;
    for (uint8_t i = 2; i <= n; i++) result *= i;
    return result;
}

Focus: linked lists without heap fragmentation risk.

• Node structure, insert/delete/traverse
• Why malloc/free are avoided on many MCUs (fragmentation, non-determinism)
• Fixed-size node pool with a free list as a malloc replacement

1. Implement insert-at-head and delete-by-value on a singly linked list.
2. Reverse a singly linked list iteratively.
3. Detect a cycle using Floyd’s slow/fast pointer method.

#define POOL_SIZE 16

typedef struct node { int16_t value; struct node *next; } node_t;

static node_t pool[POOL_SIZE];
static uint8_t pool_used[POOL_SIZE] = {0};

node_t *node_alloc(void) {
    for (uint8_t i = 0; i < POOL_SIZE; i++)
        if (!pool_used[i]) { pool_used[i] = 1; return &pool[i]; }
    return NULL;  /* pool exhausted -- deterministic failure, no fragmentation */
}

void node_free(node_t *n) {
    pool_used[n - pool] = 0;
}

node_t *list_push_front(node_t *head, int16_t value) {
    node_t *n = node_alloc();
    if (!n) return head;
    n->value = value;
    n->next = head;
    return n;
}

Focus: circular structures for round-robin task lists.

• Doubly linked list insert/delete with prev/next
• Circular linked list, sentinel-free traversal
• Use case: round-robin cooperative task scheduler

1. Implement a circular linked list of “task” nodes and a function that advances to the next task.
2. Implement delete on a doubly linked list in O(1) given only a node pointer.
3. Detect whether a linked list is circular vs NULL-terminated.

typedef struct task { const char *name; struct task *next; } task_t;

task_t t1 = {"Sensor",   NULL};
task_t t2 = {"Comms",    NULL};
task_t t3 = {"Logger",   NULL};

void build_ring(void) {
    t1.next = &t2; t2.next = &t3; t3.next = &t1;  /* circular */
}

task_t *scheduler_tick(task_t *current) {
    return current->next;   /* O(1) round robin advance */
}

Focus: fixed-capacity stacks for expression parsing and undo buffers.

• Array-backed stack: push/pop/peek, overflow/underflow checks
• Use case: balanced-bracket validation for a config parser

1. Implement a fixed-capacity stack of int16_t with overflow protection.
2. Check whether a string of brackets "{[()]}" is balanced.
3. Evaluate a postfix expression, e.g. "5 3 + 2 *", using the stack.

#define STACK_CAP 32
typedef struct { char data[STACK_CAP]; int8_t top; } stack_t;

void stack_init(stack_t *s)        { s->top = -1; }
int  stack_push(stack_t *s, char c){
    if (s->top >= STACK_CAP - 1) return 0;
    s->data[++s->top] = c; return 1;
}
int  stack_pop(stack_t *s, char *out) {
    if (s->top < 0) return 0;
    *out = s->data[s->top--]; return 1;
}

int is_balanced(const char *expr) {
    stack_t s; stack_init(&s);
    for (const char *p = expr; *p; p++) {
        if (*p=='('||*p=='['||*p=='{') stack_push(&s, *p);
        else if (*p==')'||*p==']'||*p=='}') {
            char open;
            if (!stack_pop(&s, &open)) return 0;
            if ((*p==')' && open!='(') ||
                (*p==']' && open!='[') ||
                (*p=='}' && open!='{')) return 0;
        }
    }
    return s.top == -1;
}

Focus: the single most important data structure in embedded firmware — UART/SPI/DMA buffering.

• Array-based FIFO queue, head/tail indices
• Circular (ring) buffer: power-of-two sizing for masking instead of modulo
• Full vs empty ambiguity and how to resolve it (count field or one-slot-wasted trick)

1. Implement a ring buffer of uint8_t with capacity 64 (power of two) for RX bytes.
2. Explain why capacity must be a power of two when using & (CAP-1) instead of % CAP.
3. Add overflow detection that increments a dropped-byte counter instead of corrupting data.

#define RB_CAP 64   /* must be power of two */

typedef struct {
    uint8_t buf[RB_CAP];
    uint16_t head;   /* write index */
    uint16_t tail;   /* read index */
    uint16_t count;
} ring_buf_t;

void rb_init(ring_buf_t *rb) { rb->head = rb->tail = rb->count = 0; }

int rb_push(ring_buf_t *rb, uint8_t byte) {
    if (rb->count == RB_CAP) return 0;      /* full */
    rb->buf[rb->head] = byte;
    rb->head = (rb->head + 1) & (RB_CAP - 1);
    rb->count++;
    return 1;
}

int rb_pop(ring_buf_t *rb, uint8_t *out) {
    if (rb->count == 0) return 0;           /* empty */
    *out = rb->buf[rb->tail];
    rb->tail = (rb->tail + 1) & (RB_CAP - 1);
    rb->count--;
    return 1;
}

Focus: combining stacks and queues to solve slightly harder problems.

• Implementing a queue using two stacks (and vice versa)
• Reversing the first K elements of a queue using a stack

1. Implement a FIFO queue using two LIFO stacks.
2. Reverse a string in place using a fixed-size stack.
3. Given a stream of sensor readings, keep only the last N in a ring buffer and compute a running average.

typedef struct { stack_t in, out; } queue2_t;

void q2_init(queue2_t *q) { stack_init(&q->in); stack_init(&q->out); }

void q2_enqueue(queue2_t *q, char c) { stack_push(&q->in, c); }

int q2_dequeue(queue2_t *q, char *out) {
    if (q->out.top < 0) {
        char tmp;
        while (stack_pop(&q->in, &tmp)) stack_push(&q->out, tmp);
    }
    return stack_pop(&q->out, out);
}

Focus: array-based heaps for priority-based task scheduling.

• Array representation of a complete binary tree, index math: parent=(i-1)/2, children=2i+1/2i+2
• Min-heap insert (sift-up) and extract-min (sift-down)

1. Implement heap_insert and heap_extract_min on a fixed array.
2. Use the heap to schedule tasks by priority number (lower runs first).

#define HEAP_CAP 16
static int16_t heap[HEAP_CAP];
static uint8_t heap_size = 0;

void heap_insert(int16_t value) {
    if (heap_size >= HEAP_CAP) return;
    uint8_t i = heap_size++;
    heap[i] = value;
    while (i > 0) {
        uint8_t parent = (i - 1) / 2;
        if (heap[parent] <= heap[i]) break;
        int16_t tmp = heap[parent]; heap[parent] = heap[i]; heap[i] = tmp;
        i = parent;
    }
}

Focus: rebuild each structure from memory, then combine two of them.

1. From memory, re-implement the ring buffer (Day 11) and the pool-backed linked list (Day 8).
2. Merge two sorted fixed arrays into a third fixed array without extra dynamic memory.
3. Design (on paper) a small fixed-capacity LRU cache using an array + indices — no heap.

Focus: traversing trees without recursion, using an explicit stack array.

• Binary tree node structure, depth, height
• Recursive traversal recap, then converting inorder traversal to an iterative version with an explicit stack

1. Implement iterative inorder traversal using a fixed-size explicit stack (no recursion).
2. Compute the height of a binary tree iteratively using level-order traversal.

typedef struct tnode { int16_t val; struct tnode *l, *r; } tnode_t;

#define TSTACK_CAP 32

void inorder_iterative(tnode_t *root) {
    tnode_t *stack[TSTACK_CAP];
    int8_t top = -1;
    tnode_t *cur = root;

    while (cur != NULL || top >= 0) {
        while (cur != NULL) {
            stack[++top] = cur;
            cur = cur->l;
        }
        cur = stack[top--];
        printf("%d ", cur->val);
        cur = cur->r;
    }
}

Focus: sorted lookup structures built once at init time, e.g. calibration tables.

• BST insert/search/delete, in-order gives sorted output
• Iterative (non-recursive) insert and search

1. Implement iterative BST insert and search.
2. Find the minimum and maximum value in a BST iteratively.

tnode_t *bst_insert(tnode_t *root, tnode_t *new_node) {
    if (root == NULL) return new_node;
    tnode_t *cur = root;
    while (1) {
        if (new_node->val < cur->val) {
            if (cur->l == NULL) { cur->l = new_node; break; }
            cur = cur->l;
        } else {
            if (cur->r == NULL) { cur->r = new_node; break; }
            cur = cur->r;
        }
    }
    return root;
}

Focus: building a full heap from an unsorted array in one pass.

• Sift-down (heapify) operation, building a heap in O(n)
• Max-heap for “highest priority task first” scheduling

1. Implement heapify(arr, n, i) and use it to build a max-heap from an array.
2. Use the max-heap to repeatedly extract the highest-priority task.

void heapify(int16_t *arr, uint8_t n, uint8_t i) {
    uint8_t largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        int16_t tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
        heapify(arr, n, largest);
    }
}

void build_max_heap(int16_t *arr, uint8_t n) {
    for (int8_t i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
}

Focus: O(1)-extra-memory sorts that fit tiny RAM budgets.

• Bubble/selection sort basics (O(n²), rarely used but good to know)
• Insertion sort in depth — adaptive, in-place, great for nearly-sorted streaming sensor data

1. Implement insertion sort and count the number of shifts it performs.
2. Explain why insertion sort is often chosen on MCUs for small/nearly-sorted arrays over quicksort.

void insertion_sort(int16_t *arr, uint8_t n) {
    for (uint8_t i = 1; i < n; i++) {
        int16_t key = arr[i];
        int8_t j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Focus: quicksort without recursion, so it can’t overflow a small task stack.

• Quicksort partitioning, average O(n log n)
• Replacing recursive calls with an explicit index-range stack, bounding max stack depth

1. Implement quicksort using an explicit stack of (low, high) index pairs instead of recursion.
2. Explain worst-case O(n²) quicksort behavior and one mitigation (e.g. median-of-three pivot).

uint8_t partition(int16_t *arr, uint8_t low, uint8_t high) {
    int16_t pivot = arr[high];
    uint8_t i = low;
    for (uint8_t j = low; j < high; j++) {
        if (arr[j] < pivot) {
            int16_t t = arr[i]; arr[i] = arr[j]; arr[j] = t;
            i++;
        }
    }
    int16_t t = arr[i]; arr[i] = arr[high]; arr[high] = t;
    return i;
}

void quicksort_iterative(int16_t *arr, uint8_t n) {
    uint8_t stack[32][2];   /* bounded stack: max ~log2(n) depth pairs */
    int8_t top = -1;
    stack[++top][0] = 0; stack[top][1] = n - 1;

    while (top >= 0) {
        uint8_t low = stack[top][0], high = stack[top][1]; top--;
        if (low >= high) continue;
        uint8_t p = partition(arr, low, high);
        stack[++top][0] = low;   stack[top][1] = p - 1;
        stack[++top][0] = p + 1; stack[top][1] = high;
    }
}

Focus: O(1) command lookup tables — no heap, fixed slots, linear probing.

• Hash functions (simple modulo, djb2-style)
• Collision resolution: linear probing on a fixed-size array
• Use case: string command → handler function lookup

1. Implement a fixed-size hash table (16 slots) with linear probing for string keys.
2. Insert commands "LED_ON", "LED_OFF", "STATUS" and resolve a lookup.

#define HT_CAP 16
typedef struct { const char *key; void (*handler)(void); uint8_t used; } ht_entry_t;
static ht_entry_t table[HT_CAP];

uint32_t hash_str(const char *s) {
    uint32_t h = 5381;
    while (*s) h = ((h << 5) + h) + (uint8_t)(*s++);  /* djb2 */
    return h;
}

void ht_insert(const char *key, void (*handler)(void)) {
    uint32_t idx = hash_str(key) % HT_CAP;
    for (uint8_t tries = 0; tries < HT_CAP; tries++) {
        uint32_t slot = (idx + tries) % HT_CAP;
        if (!table[slot].used) {
            table[slot].key = key; table[slot].handler = handler;
            table[slot].used = 1; return;
        }
    }
}

void (*ht_lookup(const char *key))(void) {
    uint32_t idx = hash_str(key) % HT_CAP;
    for (uint8_t tries = 0; tries < HT_CAP; tries++) {
        uint32_t slot = (idx + tries) % HT_CAP;
        if (!table[slot].used) return NULL;
        if (table[slot].used && strcmp(table[slot].key, key) == 0)
            return table[slot].handler;
    }
    return NULL;
}

Focus: combine bit manipulation, structs, function pointers and hashing into one firmware-style module.

1. Extend Day 20’s hash table so each command handler receives an argument string.
2. Re-derive iterative quicksort (Day 19) and BST insert (Day 16) from memory.
3. Write a short note comparing when you’d choose a BST vs a hash table on an MCU with 8–32 KB RAM.

Focus: searching fixed lookup/calibration tables efficiently.

• Linear search, when it’s actually the right choice (small/unsorted n)
• Iterative binary search, off-by-one pitfalls

1. Implement iterative binary search on a sorted ADC calibration table.
2. Find the closest value (not exact match) in a sorted array — useful for lookup-table interpolation.

int16_t binary_search(const int16_t *arr, uint8_t n, int16_t target) {
    int16_t lo = 0, hi = n - 1;
    while (lo <= hi) {
        int16_t mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Focus: quantifying stack usage — a 512-byte–1KB task stack does not forgive deep recursion.

• Estimating stack frame size, worst-case recursion depth
• Tail recursion and why most embedded compilers won’t reliably optimize it — convert manually

1. Convert recursive Fibonacci to an iterative O(n) version.
2. Convert recursive GCD (Euclid’s algorithm) to iterative.
3. Given a stack frame of ~32 bytes and a 1KB stack, compute the max safe recursion depth.

uint32_t fib_iterative(uint8_t n) {
    uint32_t a = 0, b = 1;
    for (uint8_t i = 0; i < n; i++) {
        uint32_t next = a + b;
        a = b; b = next;
    }
    return a;
}

Focus: small fixed graphs — sensor networks, dependency/init-order resolution.

• Adjacency matrix vs adjacency list, memory tradeoffs for small node counts
• Iterative BFS using a static queue array, iterative DFS using a static stack array

1. Represent an 8-node sensor network as an adjacency matrix and run BFS from node 0.
2. Use DFS to detect whether the module-init dependency graph has a cycle.

#define N_NODES 8
uint8_t adj[N_NODES][N_NODES];  /* 1 = edge exists */

void bfs(uint8_t start) {
    uint8_t visited[N_NODES] = {0};
    uint8_t queue[N_NODES], head = 0, tail = 0;

    queue[tail++] = start; visited[start] = 1;
    while (head != tail) {
        uint8_t node = queue[head++];
        printf("Visit %d\n", node);
        for (uint8_t n = 0; n < N_NODES; n++) {
            if (adj[node][n] && !visited[n]) {
                visited[n] = 1;
                queue[tail++] = n;
            }
        }
    }
}

Focus: a deterministic, fragmentation-free replacement for malloc/free.

• Fixed-block pool design, intrusive free list stored inside unused blocks
• O(1) alloc and free, deterministic worst-case timing

1. Implement pool_alloc() / pool_free() for fixed 32-byte blocks.
2. Explain why this design has no fragmentation compared to a general-purpose heap.

#define BLOCK_SIZE 32
#define BLOCK_COUNT 16

typedef struct free_block { struct free_block *next; } free_block_t;

static uint8_t pool_mem[BLOCK_SIZE * BLOCK_COUNT];
static free_block_t *free_list = NULL;

void pool_init(void) {
    free_list = NULL;
    for (int i = BLOCK_COUNT - 1; i >= 0; i--) {
        free_block_t *b = (free_block_t *)&pool_mem[i * BLOCK_SIZE];
        b->next = free_list;
        free_list = b;
    }
}

void *pool_alloc(void) {
    if (!free_list) return NULL;
    void *block = free_list;
    free_list = free_list->next;
    return block;
}

void pool_free(void *block) {
    free_block_t *b = (free_block_t *)block;
    b->next = free_list;
    free_list = b;
}

Focus: FSMs as a data structure — arrays of structs + function pointers, not nested switch statements.

• State/event transition tables represented as 2D arrays or structs
• Entry/exit action function pointers per state

1. Design a table-driven FSM for a push-button debouncer (Idle, Debounce, Pressed).
2. Add an entry-action callback that fires whenever a state changes.

typedef enum { ST_IDLE, ST_DEBOUNCE, ST_PRESSED, ST_COUNT } state_t;
typedef enum { EV_BTN_DOWN, EV_TIMEOUT, EV_BTN_UP, EV_COUNT } event_t;

static const state_t transition_table[ST_COUNT][EV_COUNT] = {
    /*              EV_BTN_DOWN     EV_TIMEOUT     EV_BTN_UP */
    /* ST_IDLE   */ {ST_DEBOUNCE,   ST_IDLE,       ST_IDLE},
    /* ST_DEBOUNCE*/{ST_DEBOUNCE,   ST_PRESSED,    ST_IDLE},
    /* ST_PRESSED*/ {ST_PRESSED,    ST_PRESSED,    ST_IDLE},
};

state_t fsm_step(state_t current, event_t ev) {
    return transition_table[current][ev];
}

Focus: revisiting Day 11’s ring buffer for true ISR-to-main-loop safety.

• Why a shared count field is unsafe between an ISR (producer) and main loop (consumer)
• Single-producer/single-consumer buffer using only volatile head/tail, no shared count, no locks

1. Rewrite the Day 11 ring buffer to use only volatile head/tail (no count) so it’s safe for one ISR writer and one main-loop reader.
2. Explain why this pattern still breaks with two producers (multiple ISRs) without a critical section.

#define SPSC_CAP 64  /* power of two */

typedef struct {
    uint8_t buf[SPSC_CAP];
    volatile uint16_t head;  /* written only by producer (ISR) */
    volatile uint16_t tail;  /* written only by consumer (main loop) */
} spsc_rb_t;

/* Called from ISR */
int spsc_push(spsc_rb_t *rb, uint8_t byte) {
    uint16_t next = (rb->head + 1) & (SPSC_CAP - 1);
    if (next == rb->tail) return 0;   /* full */
    rb->buf[rb->head] = byte;
    rb->head = next;                  /* single atomic-ish write */
    return 1;
}

/* Called from main loop */
int spsc_pop(spsc_rb_t *rb, uint8_t *out) {
    if (rb->tail == rb->head) return 0; /* empty */
    *out = rb->buf[rb->tail];
    rb->tail = (rb->tail + 1) & (SPSC_CAP - 1);
    return 1;
}

Focus: wire together the ring buffer, hash dispatcher and FSM into one realistic module.

1. Design a UART command processor: bytes land in the Day 27 ring buffer from an RX ISR; the main loop pops bytes, assembles a line, looks up the command in the Day 20 hash table, and dispatches a handler.
2. Add a small FSM (Day 26 style) with states WAIT_START, READ_LINE, DISPATCH to drive the parser.
3. Add a fixed-block pool (Day 25) to hand out small “command result” structs to handlers.

void uart_rx_isr(void) {
    uint8_t byte = UART_READ_DATA_REG();   /* hardware read */
    spsc_push(&rx_rb, byte);
}

void main_loop_step(void) {
    static char line[64]; static uint8_t idx = 0;
    uint8_t byte;
    while (spsc_pop(&rx_rb, &byte)) {
        if (byte == '\n') {
            line[idx] = '\0';
            void (*handler)(void) = ht_lookup(line);
            if (handler) handler();
            idx = 0;
        } else if (idx < sizeof(line) - 1) {
            line[idx++] = byte;
        }
    }
}

Focus: simulate interview pressure — 90 minutes, no notes, then review.

1. Reverse a singly linked list iteratively, then reverse it recursively and compare stack cost.
2. Detect a cycle in a linked list (Floyd’s algorithm) and find the cycle’s starting node.
3. Implement a ring buffer from a blank file, including overflow handling, in under 10 minutes.
4. Given a 32-bit register value, write a function that returns the position of the lowest set bit without a loop (hint: n & -n).

Focus: integrate the month’s structures into one coherent firmware module.