Trees, Graphs & State

Trees, tries, graphs, union-find, and state machines

Trees index hierarchical or ordered relationships; tries index prefixes; graphs represent arbitrary dependencies or reachability; union-find tracks evolving connectivity; finite-state machines encode temporal behavior. Embedded versions replace recursion and dynamic nodes with caller-provided arrays, indices, and explicit capacity failures.

A breadth-first search uses a queue to discover the fewest unweighted edges; depth-first search uses a stack for reachability and cycle reasoning. Both need visited state or they can repeat forever. Fixed graphs should use an adjacency representation chosen from actual density and maximum vertices.

Topological sorting repeatedly removes zero-indegree vertices. Producing fewer than V vertices proves a cycle exists, but identifying the actual cycle requires an additional DFS/parent trace. Do not promise cycle nodes from Kahn's count alone.

Finite-state machines are graphs whose edges are events and guards. They replace blocking delays with timestamp comparisons and make retries, debouncing, and protocol recovery testable. Every state/event pair needs a documented action, including ignored or impossible events.

Patterns and when they apply

BFS queue

Shortest path in unweighted grid/graph. Cost: O(V+E) and O(V) visited/workspace. Avoid when: Marking visited only when dequeued, causing duplicates.

topological sort

Peripheral initialization dependencies. Cost: O(V+E), detects but does not automatically exhibit a cycle. Avoid when: Treating a cyclic partial order as valid.

union-find

Incremental undirected connectivity and cycle detection. Cost: Near-constant amortized with rank+compression. Avoid when: Using it for directed reachability.

FSM

Non-blocking temporal control. Cost: Explicit state/event matrix. Avoid when: Scattered flags with impossible combinations.

Peripheral ordering

1. Compute indegree for each dependency node.
2. Queue every zero-indegree peripheral.
3. Pop one, append it to order, and decrement its outgoing neighbors.
4. If output count<V, report a dependency cycle.

Every emitted peripheral appears after all prerequisites, using bounded O(V+E) storage and work.

Checklist

• Directed or undirected?
• Weighted or unweighted?
• How is visited represented?
• Is recursion depth bounded?
• Must a cycle merely be detected or exhibited?
• Are all FSM events covered?

Hard - Static Command Trie

A command table stored as a trie so lookup cost depends on the command length rather than the number of commands - a shell with a hundred commands in flash.

Build a compact trie from a fixed command list at initialization, then match input without allocation. Reject duplicate commands and exhausted node storage.

Static trie for command dispatch

Builds a trie over caller-owned node storage at init; trie_add rejects duplicates and exhausted storage. trie_find walks one input byte per step and returns the handler only for exact commands. No allocation after init.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef void (*command_fn)(void);
#define TRIE_MAX_NODES 64u
#define TRIE_CHILDREN 26u   /* a-z command alphabet keeps the table small */

typedef struct {
    int8_t child[TRIE_CHILDREN];   /* node index or -1 */
    command_fn fn;                 /* non-NULL marks a terminal command */
} trie_node_t;

typedef struct {
    trie_node_t *nodes;   /* caller storage, TRIE_MAX_NODES entries */
    size_t capacity;
    size_t used;
} trie_t;

typedef enum { TRIE_OK, TRIE_DUPLICATE, TRIE_FULL, TRIE_BAD_CHAR } trie_status_t;

void trie_init(trie_t *t, trie_node_t *storage, size_t capacity) {
    t->nodes = storage;
    t->capacity = capacity;
    t->used = 1u;   /* node 0 = root */
    for (size_t i = 0u; i < capacity; i++) {
        for (size_t c = 0u; c < TRIE_CHILDREN; c++) storage[i].child[c] = -1;
        storage[i].fn = NULL;
    }
}

trie_status_t trie_add(trie_t *t, const char *command, command_fn fn) {
    if (t == NULL || command == NULL || fn == NULL || *command == '\0')
        return TRIE_BAD_CHAR;
    size_t cur = 0u;
    for (const char *p = command; *p != '\0'; p++) {
        if (*p < 'a' || *p > 'z') return TRIE_BAD_CHAR;
        int c = *p - 'a';
        if (t->nodes[cur].child[c] < 0) {
            if (t->used == t->capacity) return TRIE_FULL;
            t->nodes[cur].child[c] = (int8_t)t->used++;
        }
        cur = (size_t)t->nodes[cur].child[c];
    }
    if (t->nodes[cur].fn != NULL) return TRIE_DUPLICATE;  /* exact command exists */
    t->nodes[cur].fn = fn;
    return TRIE_OK;
}

command_fn trie_find(const trie_t *t, const char *command) {
    if (t == NULL || command == NULL) return NULL;
    size_t cur = 0u;
    for (const char *p = command; *p != '\0'; p++) {
        if (*p < 'a' || *p > 'z') return NULL;
        int8_t next = t->nodes[cur].child[*p - 'a'];
        if (next < 0) return NULL;      /* path dies: unknown command */
        cur = (size_t)next;
    }
    return t->nodes[cur].fn;            /* NULL unless a command ends here */
}

• A trie turns command lookup into one array hop per character: 'status' is at most 6 hops regardless of whether the table holds 5 commands or 500. Lookup cost depends on the key length, not the table size.
• Shared prefixes share nodes — 'start' and 'status' diverge only at the third character — so a command set packs into far fewer nodes than total characters, which is what makes fixed storage viable.
• A handler pointer only on terminal nodes is what rejects prefixes: 'stat' walks fine but lands on a node with fn == NULL, so it returns unknown-command instead of firing 'start'.
• All nodes come from one caller array with a bump index (used). Failure modes are explicit: TRIE_FULL when storage runs out, TRIE_DUPLICATE on re-registration — both detectable at init, never at runtime.
• Restricting the alphabet to a-z shrinks each node from 256 pointers to 26 int8s: 26 bytes per node instead of 1 KB. Alphabet choice is a memory/throughput design decision, not an afterthought.

Cases the tests must cover

• Add 'start','stop','status': each finds its own handler
• 'sta' and 'starts' return NULL (prefix and extension are not commands)
• Adding 'start' twice → TRIE_DUPLICATE
• Exhausting node storage → TRIE_FULL, previously added commands still work
• Uppercase or digits in a command → TRIE_BAD_CHAR / NULL lookup

How it gets written wrong

• Returning a handler for a prefix that merely reaches an internal node — check fn, not reachability.
• 256-way child arrays per node: correct but ~1 KB per node makes the static table explode.
• Reallocating or mallocing nodes during add; the whole point is fixed init-time storage.

Medium - Memory-Region Lookup

Mapping an address to the memory region that contains it: which peripheral a fault address belongs to, which flash sector an offset is in, which MPU region covers a pointer.

Given sorted non-overlapping address regions, return the region containing an address and reject overlapping regions during initialization.

Memory-map lookup over sorted regions

region_find returns the region containing address in O(log n) over sorted, non-overlapping [start,end) regions. regions_validate rejects overlapping or unsorted input at init. Returns NULL for unmapped addresses.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    uintptr_t start;   /* inclusive */
    uintptr_t end;     /* exclusive */
    uint8_t permissions;
} region_t;

bool regions_validate(const region_t *regions, size_t n) {
    if (regions == NULL && n > 0u) return false;
    for (size_t i = 0u; i < n; i++) {
        if (regions[i].start >= regions[i].end) return false;      /* empty/bad */
        if (i > 0u && regions[i].start < regions[i - 1u].end)
            return false;   /* unsorted or overlapping — reject at boot */
    }
    return true;
}

const region_t *region_find(const region_t *regions, size_t n, uintptr_t address) {
    if (regions == NULL) return NULL;
    /* Binary search for the last region with start <= address. */
    size_t lo = 0u, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2u;
        if (regions[mid].start <= address) lo = mid + 1u;
        else hi = mid;
    }
    if (lo == 0u) return NULL;                  /* before the first region */
    const region_t *r = &regions[lo - 1u];
    return address < r->end ? r : NULL;         /* inside, or in a gap */
}

• MPU setup, permission checks, and address decoders all ask the same question: which region owns this address? With regions sorted by start, one binary search answers it — the same lower-bound pattern as calibration tables, aimed at intervals.
• Searching for the last start <= address lands on the only region that could contain the address; a single end comparison then distinguishes 'inside' from 'in a hole between regions'.
• Validation is a separate init-time pass: sorted order and no overlap are preconditions the search relies on, so they are verified once at boot rather than paid for on every lookup.
• Half-open [start, end) intervals make adjacency unambiguous — a region ending at 0x1000 and one starting at 0x1000 neither overlap nor leave a gap.

Cases the tests must cover

• Address exactly at a region start → that region
• Address at region end → NULL or the next region (half-open semantics)
• Address in a gap between regions → NULL
• Overlapping input fails regions_validate
• Single region containing address 0 and UINTPTR_MAX edges

How it gets written wrong

• Linear scans on every lookup; the memory map is static, so sort once and search.
• Closed-interval [start, end] models where end = start of next - 1 invites overflow at UINTPTR_MAX.
• Trusting table order without validation — one overlapping entry silently misroutes every later lookup.

Easy - Non-Blocking Button Debouncer

Every mechanical input on every product. A switch bounces for 5 to 50 ms and produces dozens of spurious edges per press.

Implement a timestamp-driven button FSM producing pressed and released events. It must never delay or busy-wait and must handle tick wrap.

Non-blocking debounce FSM

Consumes timestamped raw samples and emits one event only after a candidate level remains unchanged for debounce_ticks.

#include <stdbool.h>
#include <stdint.h>

typedef enum { BUTTON_NONE,BUTTON_PRESSED,BUTTON_RELEASED } button_event_t;
typedef struct { bool stable,candidate; uint32_t candidate_since,debounce_ticks; } debounce_t;

void debounce_init(debounce_t *d,bool initial,uint32_t ticks,uint32_t now){
    d->stable=initial; d->candidate=initial; d->candidate_since=now; d->debounce_ticks=ticks;
}

button_event_t debounce_update(debounce_t *d,bool raw,uint32_t now){
    if(raw!=d->candidate){d->candidate=raw;d->candidate_since=now;return BUTTON_NONE;}
    if(raw==d->stable)return BUTTON_NONE;
    if((uint32_t)(now-d->candidate_since)<d->debounce_ticks)return BUTTON_NONE;
    d->stable=raw;
    return raw?BUTTON_PRESSED:BUTTON_RELEASED;
}

• A raw transition starts a new candidate interval rather than blocking.
• Unsigned subtraction measures elapsed ticks across one wrap.
• Only a sustained candidate changes stable state and emits an event.

Cases the tests must cover

• clean press/release
• bounce restarts timer
• tick wrap
• zero debounce
• repeated stable samples emit once

How it gets written wrong

• debounce_ticks must be less than half the uint32_t range for unambiguous elapsed-time reasoning.
• Sampling cadence determines when the threshold is observed.

Medium - Retry with Exponential Backoff

Retrying a failed operation - a network request, a sensor read, a flash write - without hammering the thing that just failed.

Implement a non-blocking retry state machine with capped exponential delay, jitter from an injected PRNG, attempt limit, and wrap-safe timing.

Non-blocking retry with capped exponential backoff and jitter

Drives a retry cycle from events and ticks without ever sleeping: RETRY_FIRE (attempt now), RETRY_WAIT (nothing due), RETRY_GIVE_UP (attempts exhausted). Delay doubles per failure up to a cap, decorrelated by an injected PRNG; all timing is wrap-safe.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef enum { RETRY_WAIT, RETRY_FIRE, RETRY_GIVE_UP } retry_action_t;
typedef enum { EV_TICK, EV_SUCCESS, EV_FAILURE } event_t;

typedef struct {
    uint32_t base_delay;   /* ticks for the first retry */
    uint32_t max_delay;    /* cap */
    uint8_t max_attempts;
    uint8_t attempts;      /* failures so far */
    uint32_t next_due;     /* tick when the next attempt is allowed */
    uint32_t (*prng)(void *state);  /* injected randomness (testable!) */
    void *prng_state;
} retry_t;

static bool due(uint32_t now, uint32_t deadline) {
    return (int32_t)(now - deadline) >= 0;   /* wrap-safe 'now >= deadline' */
}

retry_action_t retry_update(retry_t *r, uint32_t now, event_t ev) {
    if (ev == EV_SUCCESS) { r->attempts = 0u; return RETRY_WAIT; }
    if (ev == EV_TICK) {
        if (r->attempts == 0u) return RETRY_WAIT;      /* nothing to retry */
        if (!due(now, r->next_due)) return RETRY_WAIT;
        if (r->attempts > r->max_attempts) return RETRY_GIVE_UP;
        return RETRY_FIRE;                             /* caller retries now */
    }
    /* EV_FAILURE: schedule the next attempt with backoff + jitter. */
    r->attempts++;
    if (r->attempts > r->max_attempts) return RETRY_GIVE_UP;
    uint32_t shift = r->attempts - 1u;
    if (shift > 20u) shift = 20u;                       /* bound the shift */
    uint32_t delay = r->base_delay << shift;            /* exponential growth */
    if (delay > r->max_delay || delay < r->base_delay) delay = r->max_delay;
    uint32_t jitter = r->prng != NULL ? r->prng(r->prng_state) % (r->base_delay + 1u) : 0u;
    r->next_due = now + delay + jitter;                 /* wraps safely by design */
    return RETRY_WAIT;
}

• A retry loop that calls delay_ms() blocks the whole firmware. The state machine alternative: remember when the next attempt is due, return control to the scheduler, and let ordinary ticks drive the decision. Zero threads blocked, zero timers allocated.
• Exponential backoff (base, 2x, 4x, 8x, and so on) protects a struggling peer from a reconnect storm; the cap keeps worst-case latency sane; both together are the difference between a polite client and an accidental DoS.
• Jitter — a random slice added to every delay — stops a fleet of devices that failed together from retrying in lockstep. Injecting the PRNG keeps the FSM deterministic under test (inject a stub) and decorrelated in the field.
• All 'has the deadline passed?' logic uses the signed-difference wrap-safe compare, so a 49.7-day uptime rollover mid-backoff changes nothing.
• Give-up is a first-class outcome: after max_attempts the FSM says so and stops scheduling, letting the caller escalate (alert, safe state) instead of retrying forever.

Cases the tests must cover

• Failure then tick before due → WAIT; tick at/after due → FIRE
• Delays follow base, 2x, 4x and never exceed max_delay + jitter bound
• SUCCESS resets the attempt counter; next failure starts from base
• attempts > max_attempts → GIVE_UP, no further due times scheduled
• Tick wrap between scheduling and firing still fires on time

How it gets written wrong

• Unbounded shifts: base << 32 is UB and base << attempts wraps small, creating a hot retry loop.
• No jitter: every node that lost the server at the same outage reconnects on the same millisecond.
• Blocking delays inside the state machine — the FSM exists precisely to avoid them.

Medium - Peripheral Initialization Order

Bringing up peripherals in an order that respects their dependencies: clocks before the peripherals they feed, power rails before the sensors on them, DMA before the driver that uses it.

Topologically sort peripheral dependencies using fixed arrays. If a cycle exists, return the nodes participating in one cycle.

Bounded topological sort

Sorts a directed graph of at most 32 vertices represented by adjacency bitmasks. Returns false for a cycle or invalid edge.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool topo_sort(const uint32_t *edges,size_t vertices,uint8_t *order){
    if(!edges||!order||vertices==0u||vertices>32u)return false;
    uint8_t indegree[32]={0}; uint8_t queue[32]; size_t head=0u,tail=0u,out=0u;
    uint32_t valid=vertices==32u?UINT32_MAX:((UINT32_C(1)<<vertices)-1u);
    for(size_t u=0u;u<vertices;++u){
        if((edges[u]&~valid)!=0u)return false;
        for(size_t v=0u;v<vertices;++v)if((edges[u]&(UINT32_C(1)<<v))!=0u)++indegree[v];
    }
    for(size_t v=0u;v<vertices;++v)if(indegree[v]==0u)queue[tail++]=(uint8_t)v;
    while(head<tail){size_t u=queue[head++];order[out++]=(uint8_t)u;uint32_t row=edges[u];for(size_t v=0u;v<vertices;++v)if((row&(UINT32_C(1)<<v))!=0u&&--indegree[v]==0u)queue[tail++]=(uint8_t)v;}
    return out==vertices;
}

• indegree counts unmet prerequisites for each vertex.
• The queue owns exactly the zero-indegree vertices ready to emit.
• If fewer than V are emitted, remaining vertices participate in or depend on a cycle.

Cases the tests must cover

• single vertex
• chain
• diamond dependencies
• disconnected DAG
• self-loop
• multi-node cycle
• edge outside vertex range

How it gets written wrong

• This representation intentionally favors tiny dense embedded graphs; adjacency lists give O(V+E) for larger sparse graphs.
• Returning false detects a cycle but does not enumerate one.

Medium - Validate a Bounded BST

Validating a structure loaded from persistent storage before trusting it - a tree read back from flash whose contents may be corrupted or from an older firmware.

Validate a binary search tree iteratively using a caller-provided stack. Define whether duplicate keys are accepted and enforce that rule globally.

Iterative BST validation with inherited bounds

Returns true when every node satisfies the global BST rule with strict inequality (duplicate keys rejected) using a caller-provided stack of capacity frames. Returns false for violations; a NULL tree is valid. Failing due to stack exhaustion is reported as false only when depth exceeds capacity — callers size capacity to tree height.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct tree_node {
    struct tree_node *left, *right;
    int32_t key;
} tree_node_t;

typedef struct {
    const tree_node_t *node;
    int64_t low;    /* exclusive lower bound inherited from ancestors */
    int64_t high;   /* exclusive upper bound */
} frame_t;

bool bst_valid(const tree_node_t *root, frame_t *stack, size_t capacity) {
    if (root == NULL) return true;
    if (stack == NULL || capacity == 0u) return false;
    /* int64 bounds mean INT32_MIN/MAX keys never collide with the sentinels */
    size_t depth = 0u;
    stack[depth++] = (frame_t){ root, INT64_MIN, INT64_MAX };
    while (depth > 0u) {
        frame_t f = stack[--depth];
        if ((int64_t)f.node->key <= f.low || (int64_t)f.node->key >= f.high)
            return false;   /* strict: duplicates are invalid everywhere */
        if (f.node->left != NULL) {
            if (depth == capacity) return false;   /* stack too small */
            /* Left child inherits our low bound and our key as new high. */
            stack[depth++] = (frame_t){ f.node->left, f.low, f.node->key };
        }
        if (f.node->right != NULL) {
            if (depth == capacity) return false;
            /* Right child inherits our key as new low and our high bound. */
            stack[depth++] = (frame_t){ f.node->right, f.node->key, f.high };
        }
    }
    return true;
}

• The famous wrong answer checks each node only against its children. The counterexample — a node 9 in the left subtree of 8 under a parent of 4 — satisfies every local check and breaks the global rule. Correct validation carries the full (low, high) window down from all ancestors.
• Each child frame tightens exactly one side of the window: left children must stay below the parent's key, right children above it. A violation at any depth is then caught by one comparison against its inherited window.
• Explicit frames on a caller stack replace recursion: worst-case memory is the tree height in a known location, not an unbounded call stack — mandatory when this validator runs on a 2 KB-task RTOS thread.
• Bounds live in int64_t so real keys at INT32_MIN/MAX cannot alias the sentinels, and strict comparison on both sides implements the no-duplicates rule globally.
• Iterative pre-order with an explicit stack is O(n) time and O(height) space — and height, not n, is what the caller must budget for (a balanced 1M-node tree needs just 20 frames).

Cases the tests must cover

• Classic balanced BST validates true
• Violation deep in a subtree (9 in the left of 8) returns false
• Duplicate key anywhere returns false (strict rule)
• Keys equal to INT32_MIN / INT32_MAX handled without sentinel collision
• Degenerate (linked-list) tree needs depth == height frames

How it gets written wrong

• Local parent-child checks: they accept globally invalid trees. This is the single most common BST interview mistake.
• Recursing: a degenerate 10k-node tree blows a typical RTOS task stack.
• Using the key type for bounds with ±infinity sentinels — real extreme keys then falsely fail.

Medium - Shortest Path Through a Fault Grid

Shortest path through a grid of blocked and clear cells - routing on a fault map, path planning on a small robot, finding a clear channel through a spectrum map.

Find the shortest four-direction path through a fixed obstacle grid with BFS using caller-owned queue and distance buffers.

BFS shortest path through an obstacle grid

Returns the number of steps of the shortest 4-direction path from start to goal, or -1 when unreachable. Caller provides queue (rows*cols points) and distance array (rows*cols int16). Blocked cells hold 1 in the grid.

#include <stddef.h>
#include <stdint.h>

typedef struct { uint16_t r, c; } point_t;

int grid_shortest(const uint8_t *grid, size_t rows, size_t cols,
                  point_t start, point_t goal,
                  point_t *queue, int16_t *distance) {
    if (grid == NULL || queue == NULL || distance == NULL ||
        rows == 0u || cols == 0u) return -1;
    size_t total = rows * cols;
    for (size_t i = 0u; i < total; i++) distance[i] = -1;   /* -1 = unvisited */
    size_t qh = 0u, qt = 0u;
    size_t s = (size_t)start.r * cols + start.c;
    if (grid[s] != 0u) return -1;             /* start is inside an obstacle */
    distance[s] = 0;
    queue[qt++] = start;
    static const int dr[4] = { -1, 1, 0, 0 };
    static const int dc[4] = { 0, 0, -1, 1 };
    while (qh < qt) {
        point_t cur = queue[qh++];
        int16_t d = distance[(size_t)cur.r * cols + cur.c];
        if (cur.r == goal.r && cur.c == goal.c) return d;   /* first hit = shortest */
        for (int k = 0; k < 4; k++) {
            int nr = (int)cur.r + dr[k];
            int nc = (int)cur.c + dc[k];
            if (nr < 0 || nc < 0 || (size_t)nr >= rows || (size_t)nc >= cols)
                continue;                                     /* off the map */
            size_t idx = (size_t)nr * cols + (size_t)nc;
            if (grid[idx] != 0u || distance[idx] != -1) continue; /* wall or seen */
            distance[idx] = (int16_t)(d + 1);
            queue[qt++] = (point_t){ (uint16_t)nr, (uint16_t)nc };
        }
    }
    return -1;   /* queue drained without reaching the goal */
}

• BFS explores in rings of equal distance: every cell at distance d is dequeued before any cell at distance d+1. So the first time the goal is dequeued, its distance is provably the shortest — that is the entire algorithm.
• The distance array doubles as the visited set: -1 means untouched, anything else is the step count from the start. One array, two jobs, zero extra memory.
• Neighbor deltas come from two small tables ({-1,1,0,0} / {0,0,-1,1}) instead of four hand-written blocks — adding diagonals later is a 4-line change, and typos in copy-pasted blocks are eliminated.
• All storage is caller-owned and exactly rows*cols entries: a cell is enqueued at most once, so the queue can never overflow its budget — the property that makes BFS firmware-safe.
• Returning the distance instead of the path keeps RAM at O(cells); if you also need the route, store a parent direction per cell and walk back from the goal.

Cases the tests must cover

• Open 3x3 grid corner to corner → 4 steps
• Goal walled in by obstacles → -1
• Start == goal → 0
• Single-file corridor forces the unique path length
• distance[] reports the true BFS level for every reachable cell

How it gets written wrong

• Marking a cell visited when dequeued instead of when enqueued — cells get queued many times and the queue overflows.
• DFS: it finds a path but not the shortest one; on grids DFS also recurses deep.
• Signed/unsigned confusion on row-1 when row is 0 — compute neighbors in int and bounds-check before casting.

Medium - Detect Wiring Connectivity Cycles

Detecting connectivity and cycles in a wiring or bus topology - finding an accidental loop in a daisy chain, or grouping nodes that share a segment.

Process undirected net connections and report the first edge that creates a cycle using fixed disjoint-set arrays with path compression and union by rank.

First cycle edge with union-find

Processes undirected edges in order and returns the index of the first edge whose endpoints are already connected (closing a cycle), or -1. Caller provides parent[0..nodes) and rank[0..nodes); both are initialized by this function.

#include <stddef.h>
#include <stdint.h>

typedef struct { uint16_t a, b; } edge_t;

static uint16_t find_root(uint16_t *parent, uint16_t x) {
    /* Path halving: every other node along the climb points one level
       higher, flattening the tree toward O(alpha(V)) amortized lookups. */
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

ptrdiff_t first_cycle_edge(const edge_t *edges, size_t edge_count,
                           uint16_t nodes, uint16_t *parent, uint8_t *rank) {
    if (edges == NULL || parent == NULL || rank == NULL) return -1;
    for (uint16_t i = 0u; i < nodes; i++) {
        parent[i] = i;   /* everyone starts as their own set */
        rank[i] = 0u;
    }
    for (size_t e = 0u; e < edge_count; e++) {
        uint16_t a = edges[e].a, b = edges[e].b;
        if (a >= nodes || b >= nodes) return -1;   /* edge outside the node set */
        uint16_t ra = find_root(parent, a);
        uint16_t rb = find_root(parent, b);
        if (ra == rb) return (ptrdiff_t)e;         /* already connected: cycle */
        /* Union by rank: attach the shallower tree under the deeper one. */
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
    }
    return -1;   /* the wiring is a forest — no cycles */
}

• Union-find tracks which nodes are already in the same connected island. A new edge between two islands merges them; an edge inside one island closes a loop. 'Same island?' is just 'same root?', answered in near-constant time.
• Two optimizations do all the work. Path halving flattens trees during find, and union by rank keeps them shallow by always attaching the smaller tree under the bigger one. Together they give the famous O(alpha(V)) — effectively constant.
• In wiring/netlist terms: the first cycle edge is the first redundant connection, exactly what a harness checker or a power-domain validator needs to flag, with its position in the original list.
• Everything runs on caller arrays of V entries — deterministic memory, no allocation, which is why this pattern survives in bootloader validation code.
• Self-loops (a == b) are cycles by this definition: find_root(a) == find_root(a) fires immediately, which is the correct answer for netlists.

Cases the tests must cover

• Path graph 0-1,1-2,2-3 → -1 (no cycle)
• Triangle: the third edge index is returned
• Self-loop edge reports itself immediately
• Two separate cycles: only the first one's closing edge index returns
• Edge referencing node >= nodes → -1 without corrupting state

How it gets written wrong

• Skipping path compression and rank: a chain graph degrades finds to O(V) and the whole pass to O(E·V).
• Recursing in find_root: pathological deep trees blow the stack; the iterative path-halving form is two lines.
• Returning the edge value instead of its index — the caller needs the position in the connection list to report the fault.

Medium - Count Reachable Peripherals

Deciding whether a state machine can still reach a safe state from where it is, or whether a node is still reachable after a link drops.

Given an edge-list power-dependency graph and a failed node, count how many nodes are reachable from it with BFS, using a caller-provided visited bitmap and queue.

BFS reachability with a bitmap

Counts nodes reachable from start (start included). Invalid arguments return 0. Caller provides the queue and a zeroed visited bitmap.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    uint8_t nodes;
    uint8_t edge_src[8];
    uint8_t edge_dst[8];
    uint8_t edge_count;
} graph_t;

static void mark(uint8_t *visited, uint8_t node)
{
    visited[node / 8U] |= (uint8_t)(1U << (node % 8U));
}

static bool seen(const uint8_t *visited, uint8_t node)
{
    return (visited[node / 8U] & (uint8_t)(1U << (node % 8U))) != 0U;
}

size_t reachable_count(const graph_t *g, uint8_t start, uint8_t *queue, uint8_t *visited_bitmap)
{
    size_t qh = 0U, qt = 0U, count = 0U;
    uint8_t i;
    if ((g == NULL) || (queue == NULL) || (visited_bitmap == NULL) || (start >= g->nodes)) return 0U;
    queue[qt++] = start;
    mark(visited_bitmap, start);
    while (qh < qt) {
        uint8_t cur = queue[qh++];
        ++count;
        for (i = 0U; i < g->edge_count; ++i) {       /* edge list: no matrix */
            if ((g->edge_src[i] == cur) && !seen(visited_bitmap, g->edge_dst[i])) {
                mark(visited_bitmap, g->edge_dst[i]);
                queue[qt++] = g->edge_dst[i];
            }
        }
    }
    return count;
}

int main(void)
{
    graph_t g = { 6U, { 0U, 0U, 1U, 3U }, { 1U, 2U, 3U, 4U }, 4U };  /* 0>1 0>2 1>3 3>4; 5 isolated */
    uint8_t queue[6];
    uint8_t visited[1] = { 0U };
    assert(reachable_count(&g, 0U, queue, visited) == 5U);
    visited[0] = 0U;
    assert(reachable_count(&g, 2U, queue, visited) == 1U);
    visited[0] = 0U;
    assert(reachable_count(&g, 9U, queue, visited) == 0U);
    return 0;
}

• Marking at enqueue time (not dequeue) prevents duplicate queue entries.
• A bitmap costs nodes/8 bytes; a bool array costs nodes bytes.
• The queue never holds more than nodes entries: bounded workspace.

Cases the tests must cover

• chain plus branch counts all five
• leaf reaches only itself
• out-of-range start returns 0
• isolated node counts itself only
• cycle does not re-enqueue visited nodes

How it gets written wrong

• Marking at dequeue time enqueues duplicates and can overflow the queue.
• Forgetting to zero the visited bitmap poisons every later query.

More in Embedded DSA

• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
• Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
• Lists, Pools & ArenasIntrusive linked lists, fixed-block pools, arena allocators and why malloc is banned in most firmware. Ten problems on owning memory with a bound you can prove before the board ships.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• Sorting Under ConstraintWhich sort survives a 512-byte stack and a fixed deadline. Insertion sort for small nearly-sorted windows, heapsort when the worst case must be provable, counting sort for byte keys, and a bounded-depth quicksort - six problems with complete C11 solutions.
• Heaps & SchedulingBinary heaps as timer wheels and task schedulers, and wrap-safe time comparison - the bug that only shows up 49 days after the board is deployed. Eight problems with complete solutions.
• Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
• Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
• Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.