Embedded DSA Interview Questions: Recursion and Linked Lists (Q74–Q123)

Part 3 of the seven-part Embedded Firmware DSA Interview Guide — 50 questions answered at full depth for embedded, firmware and senior technical roles.

Recursion and linked lists are the heart of the pointer round. What separates linked list interview questions for embedded roles from the general software version is that every answer has to survive a stack budget, an allocator that may not exist, and a worst case you can actually state out loud. These fifty answers do that.

---

Recursion and linked list interview questions for embedded roles

• Q74. What is recursion?
• Q75. Tail recursion?
• Q76. Head recursion?
• Q77. Tree recursion?
• Q78. Indirect recursion?
• Q79. Nested recursion?
• Q80. Fibonacci recursion?
• Q81. Memoization?
• Q82. Tower of Hanoi?
• Q83. Taylor series by recursion?
• Q84. Factorial?
• Q85. Power function?
• Q86. nCr by recursion?
• Q87. Recurrence relation?
• Q88. Space complexity of recursion?
• Q89. Stack overflow?
• Q90. Recursive linked list traversal?
• Q91. When is recursion a bad idea?
• Q92. Recursive binary search?
• Q93. How do you convert recursion to iteration?
• Q94. What is a singly linked list and what does it cost per node?
• Q95. What does a doubly linked list buy you over a singly linked list?
• Q96. What is a circular linked list and how do you stop traversing it?
• Q97. Why use a sentinel node in a circular doubly linked list?
• Q98. How do you insert a node at the head of a linked list?
• Q99. How do you insert a node at the tail of a linked list?
• Q100. How do you insert a node at a given position?
• Q101. How do you delete a node from a linked list?
• Q102. How do you reverse a linked list iteratively?
• Q103. How do you reverse a linked list recursively?
• Q104. How do you find the middle node in a single pass?
• Q105. How do you detect a loop in a linked list?
• Q106. How do you find the start and length of a linked list loop?
• Q107. How do you remove duplicates from a sorted linked list?
• Q108. How do you insert into a sorted linked list?
• Q109. How do you merge two sorted linked lists?
• Q110. How do you concatenate two linked lists?
• Q111. How do you find where two linked lists intersect?
• Q112. How do you delete the nth node from the end in one pass?
• Q113. How do you reverse a linked list in groups of k?
• Q114. How do you deep copy a linked list with random pointers?
• Q115. Why choose a linked list over an array?
• Q116. Array versus linked list: how do the complexities compare?
• Q117. How much memory overhead does a linked list really cost?
• Q118. Why is a linked list slower than an array on real hardware?
• Q119. Where are circular linked lists used in firmware?
• Q120. Where does an RTOS use linked lists internally?
• Q121. How do you implement a free list and pool allocator?
• Q122. Can you build a lock free linked list on a microcontroller?
• Q123. What are the real embedded uses of linked lists?

---

Questions 74 to 123, explained fully. This completes Sections 1 to 6, which is 123 of the 248 question bank.

---

Section 5: Recursion

---

Q74. What is recursion?

Say this out loud A function that solves a problem by calling itself on a smaller version of the same problem. It needs two things to be correct: a base case that returns without recursing, and a recursive case that strictly reduces the problem size so the base case is always reached. Every call consumes a stack frame, so the maximum depth is bounded by the stack you have.

The full explanation

Recursion is not a loop written oddly. It is a different way of decomposing a problem. A loop says “repeat this action”. Recursion says “this problem is the same problem, one size smaller, plus a little work”.

The two mandatory parts:

int factorial(int n) {
    if (n <= 1) return 1;              /* BASE CASE: stops the recursion */
    return n * factorial(n - 1);       /* RECURSIVE CASE: smaller problem */
}

If you remove the base case you get infinite recursion, and on a microcontroller that means a stack overflow within microseconds, which usually presents as a hard fault at a random address rather than a helpful message.

What actually happens in memory, traced for factorial(4)

Each call gets its own stack frame with its own copy of n. The frames stack up on the way down and unwind on the way back.

call chain going down:                stack grows downward

factorial(4)   n=4, waiting on factorial(3)     <-- frame 1
  factorial(3) n=3, waiting on factorial(2)     <-- frame 2
    factorial(2) n=2, waiting on factorial(1)   <-- frame 3
      factorial(1) n=1, BASE CASE, returns 1    <-- frame 4

returning back up:

      returns 1
    returns 2 * 1 = 2
  returns 3 * 2 = 6
returns 4 * 6 = 24

Four frames existed simultaneously at the deepest point. If each frame is 16 bytes, factorial(1000) needs 16 KB of stack, which most microcontrollers do not have.

The mental model that makes recursion click

Trust the recursive call. When writing factorial, do not try to trace the whole chain in your head. Assume factorial(n-1) already returns the correct answer, and ask only: given that, what do I do with it? This is the “leap of faith”, and it is how you write correct recursive code quickly. It works because induction works: if the base case is right and each step is right given the previous, the whole thing is right.

Why it matters in firmware

The depth is the whole story. Recursion is acceptable when the depth is provably small and bounded by something other than input size. A balanced binary tree of a million nodes has depth 20, which is fine. A linked list of a million nodes has depth a million, which is not.

---

Q75. Tail recursion?

Say this out loud The recursive call is the last thing the function does, and its result is returned unmodified with no pending work in the caller’s frame. That means the frame can be reused instead of stacked, so a compiler can convert it into a plain loop, making the space O(1). GCC and Clang do this at -O2, but the standard does not require it, so I never rely on it in code that must not overflow.

The full explanation

Compare the two carefully. The difference is one multiplication.

/* NOT tail recursive: after the call returns, there is still work to do */
int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);            /* must keep n alive to multiply afterwards */
}

/* Tail recursive: nothing happens after the call */
int fact_tail(int n, int acc) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, n * acc);  /* the multiply happens BEFORE the call */
}

In the first version, the frame must survive the call because n is needed for the multiply once the result comes back. In the second, the frame has nothing left to do, so the compiler can overwrite it.

What the compiler generates

fact_tail at -O2 becomes:

fact_tail:
    cmp   r0, #1
    ble   .done
.loop:
    mul   r1, r1, r0        @ acc = acc * n
    subs  r0, r0, #1        @ n = n - 1
    cmp   r0, #1
    bgt   .loop             @ a BRANCH, not a call. No stack growth at all.
.done:
    mov   r0, r1
    bx    lr

The call disappeared entirely. This is tail call optimisation, and it is why functional languages can recurse a million deep.

The accumulator pattern

Converting non tail recursion to tail recursion generally means adding a parameter that carries the work forward instead of leaving it pending. That is the acc above. It is the same transformation you apply to make list reversal iterative.

Why it matters in firmware

Do not depend on it. The optimisation is not guaranteed, it is disabled at -O0, and a debug build of code that relies on it will overflow the stack while your release build passes. If the algorithm needs unbounded depth, write the loop yourself. Say this in the interview, because “the compiler will optimise it” is a junior answer and “the compiler usually optimises it but I would not bet a product on it” is a senior one.

---

Q76. Head recursion?

Say this out loud The recursive call happens before the function’s own work, so all the work happens during the unwind. It cannot be turned into a loop directly, and it is the natural shape for anything you want to process in reverse order.

The full explanation

/* head recursion: recurse first, then act */
void print_reverse(const char *s) {
    if (*s == '\0') return;
    print_reverse(s + 1);              /* go all the way to the end first */
    putchar(*s);                       /* then print on the way back */
}

Trace for "abc":

print_reverse("abc")   calls print_reverse("bc")
  print_reverse("bc")  calls print_reverse("c")
    print_reverse("c") calls print_reverse("")
      print_reverse("") returns immediately

unwinding:
    prints 'c'
  prints 'b'
prints 'a'

output: cba

Compare with tail recursion, which prints on the way down and gives abc.

That is the whole idea: the position of the work relative to the call decides the order of the output. Recursion gives you reverse order for free, which is why it appears in linked list reversal, postorder tree traversal, and expression evaluation.

Why it matters in firmware

Head recursion cannot be tail call optimised, so its stack usage is genuinely O(n). Printing a 5000 node list in reverse this way will overflow a task stack. The iterative equivalent needs an explicit stack, which uses heap or a fixed buffer instead, but at least you control the size and can fail gracefully.

---

Q77. Tree recursion?

Say this out loud A function that calls itself more than once per invocation. The number of calls grows exponentially in the depth, while the stack depth grows only linearly, because the branches execute one at a time rather than simultaneously.

The full explanation

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);    /* two calls, so the call tree branches */
}

The call tree for fib(5)

                    fib(5)
              /                \
          fib(4)               fib(3)
         /      \             /      \
     fib(3)    fib(2)     fib(2)    fib(1)
     /    \    /    \     /    \
 fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
 /    \
fib(1) fib(0)

Count the nodes: 15 calls to compute fib(5). fib(3) is computed twice from scratch, fib(2) three times, fib(1) five times. The work is duplicated massively.

The number of calls is roughly 1.618^n, the golden ratio to the n. So fib(40) needs about 300 million calls, which takes seconds even on a fast machine. fib(50) takes minutes.

But the stack depth is only n. This is the point candidates miss. At any single moment, only one path from the root to a leaf exists on the stack. The left subtree completes and its frames are released before the right subtree starts. So time is exponential, space is linear.

The fix, two ways

Memoization, which is Q81. Or the iterative version, which is O(n) time and O(1) space:

int fib_iter(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int t = a + b;
        a = b;
        b = t;
    }
    return b;
}

Where tree recursion is genuinely correct

Binary tree traversal. traverse(left) then traverse(right) is tree recursion, and it is the right implementation, because the tree structure itself is what is being followed and there is no duplicated work.

---

Q78. Indirect recursion?

Say this out loud Function A calls B, and B calls A. There is still a cycle, just spread across more than one function, so all the same depth concerns apply. It shows up naturally in recursive descent parsers.

bool is_even(unsigned n);
bool is_odd(unsigned n);

bool is_even(unsigned n) { return (n == 0) ? true  : is_odd(n - 1); }
bool is_odd (unsigned n) { return (n == 0) ? false : is_even(n - 1); }

That example is deliberately silly, but the real case is not:

/* a recursive descent expression parser */
int parse_expression(void);   /* handles + and - , calls parse_term */
int parse_term(void);         /* handles * and / , calls parse_factor */
int parse_factor(void);       /* handles numbers and (expression), calls parse_expression */

parse_factor calls parse_expression when it encounters a parenthesis, closing the cycle. This structure is how almost every hand written parser and command interpreter is built, including AT command handlers and configuration file readers.

Why it matters in firmware

Indirect recursion is much harder to see. A static analyser looking for direct self calls will miss it, and a code reviewer scanning one file will miss it entirely. Worst case stack analysis tools must build the whole call graph and detect cycles, and when they find one they usually just report “unbounded” and give up. If you need a provable stack bound, you must either eliminate the cycle or add an explicit depth counter:

static int depth = 0;
int parse_expression(void) {
    if (++depth > MAX_NEST) { depth--; return ERR_TOO_DEEP; }
    ...
    depth--;
    return result;
}

That depth limit is a real security control, not a formality. Deeply nested input is a standard denial of service technique against parsers.

---

Q79. Nested recursion?

Say this out loud The argument to the recursive call is itself a recursive call, so the function’s own result determines how deep the next call goes. The Ackermann function is the classic example. It appears in complexity theory and essentially never in production code.

int ackermann(int m, int n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));   /* nested: inner call feeds outer */
}

ackermann(4, 2) is a number with 19729 digits. The function is famous for being computable but growing faster than any primitive recursive function, which is why it was invented.

It is worth knowing the name so you recognise it, and worth saying plainly that its practical significance is zero apart from one place: the inverse Ackermann function α(n) appears in the complexity of union find with path compression, where it is under 5 for any input that fits in the universe, which is why that structure is described as effectively constant time.

---

Q80. Fibonacci recursion?

Covered mechanically in Q77. What matters for interviews is being able to state all three versions and their costs immediately.

The expected interview flow is: write the naive one, immediately say why it is bad and draw the duplicated subtree, then write the iterative one. Mentioning the matrix power version is a bonus that shows range.

Overflow is worth mentioning too: fib(47) exceeds a signed 32 bit int, and fib(93) exceeds 64 bit.

---

Q81. Memoization?

Say this out loud Caching the result of each distinct subproblem so it is computed only once. It converts exponential tree recursion into linear time, at the cost of a table. It is top down dynamic programming, as opposed to bottom up tabulation which fills the same table with a loop.

The full explanation

#define MAXN 100
static long memo[MAXN];
static bool has[MAXN];

long fib_memo(int n) {
    if (n <= 1) return n;
    if (has[n]) return memo[n];        /* already computed, return immediately */

    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    has[n] = true;
    return memo[n];
}

Why it collapses the tree

Redraw the fib(5) tree with memoization. The first descent computes fib(4), fib(3), fib(2), fib(1), fib(0) on the way down the leftmost path. Every other node in the tree is now a cache hit that returns instantly without recursing.

             fib(5)
            /      \
        fib(4)     fib(3)  <- HIT, returns from the table
       /      \
   fib(3)     fib(2)  <- HIT
  /      \
fib(2)   fib(1)

15 calls become 9, and for larger n the saving is the difference between exponential and linear. Each value from 0 to n is computed exactly once, so it is O(n).

Memoization versus tabulation

For firmware, tabulation wins, because it has no stack cost and its memory is a single statically sized array visible in the linker map.

The has flag detail. Using a sentinel value such as 0 or -1 to mean “not computed” only works if that value can never be a legitimate answer. fib(0) is 0, so a zero sentinel is wrong here. A separate boolean array, or initialising to a value outside the possible range, avoids the bug. Interviewers notice when you handle this.

---

Q82. Tower of Hanoi?

Say this out loud Move n minus 1 discs from the source peg to the auxiliary peg, move the largest disc to the destination, then move the n minus 1 discs from auxiliary to destination. The recurrence is T(n) = 2T(n-1) + 1, giving 2^n - 1 moves, with O(n) stack depth.

The full explanation

void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to);                       /* clear the way */
    printf("move disc %d: %c -> %c\n", n, from, to);   /* the one real move */
    hanoi(n - 1, via, to, from);                       /* bring them back on top */
}

Worked trace for n = 3, from A to C via B

move disc 1: A -> C
move disc 2: A -> B
move disc 1: C -> B
move disc 3: A -> C      <-- the largest disc, moved exactly once
move disc 1: B -> A
move disc 2: B -> C
move disc 1: A -> C

7 moves total, which is 2^3 - 1

Solving the recurrence, which they may ask for

T(n) = 2T(n-1) + 1
     = 2(2T(n-2) + 1) + 1 = 4T(n-2) + 3
     = 8T(n-3) + 7
     = 2^k T(n-k) + (2^k - 1)

Set k = n so that T(0) = 0:

T(n) = 2^n * 0 + 2^n - 1 = 2^n - 1

The legend has 64 discs. At one move per second that is about 585 billion years.

Why the parameter swapping is the whole trick

Notice the third argument rotates position in each recursive call. In the first call, the destination becomes the via peg. In the second, the source becomes the via peg. Writing those two lines correctly, without hesitating, is what the question actually tests. It is checking whether you can trust the recursive step without unfolding it mentally.

---

Q83. Taylor series by recursion?

Say this out loud Evaluate e^x = 1 + x/1! + x^2/2! + ... by carrying the running power and factorial down through the recursion in an accumulator, so each term costs one multiply and one divide instead of recomputing x^n and n! from scratch. Horner’s form is the numerically stable way to write it.

The naive version and why it is bad

double taylor_bad(double x, int n) {
    if (n == 0) return 1.0;
    return power(x, n) / factorial(n) + taylor_bad(x, n - 1);
}

Each term recomputes a power and a factorial from zero, so the total work is O(n squared), and factorial(n) overflows for n above 20 even in a double’s integer range.

The accumulator version

double taylor(double x, int n) {
    static double p = 1.0, f = 1.0;    /* running power and factorial */
    if (n == 0) { p = f = 1.0; return 1.0; }

    double r = taylor(x, n - 1);       /* compute the shorter series first */
    p = p * x;                         /* one multiply gets the next power */
    f = f * n;                         /* one multiply gets the next factorial */
    return r + p / f;
}

O(n) total. Note this is head recursion: the recursive call comes first, so the terms accumulate on the unwind, from smallest exponent upward, which is also better numerically because you add the small terms before the large ones.

The static here is a real defect though: it makes the function non reentrant and it must be reset on every top level call. In an interview, point that out and offer the version that passes the state explicitly, or better, the iterative one:

double exp_horner(double x, int n) {
    double s = 1.0;
    for (int i = n; i >= 1; i--) {
        s = 1.0 + x * s / i;           /* Horner: no powers, no factorials, no overflow */
    }
    return s;
}

Horner’s form is the answer that earns real credit. It computes the same series with n multiplies and n divides, never computes a large power or factorial at all, so nothing overflows, and it is the standard way polynomials are evaluated in DSP and control code.

---

Q84. Factorial?

The mechanics are in Q74 and Q75. What makes it an interview question is the overflow discussion.

int factorial(int n) {
    if (n < 0) return -1;              /* undefined for negatives, handle it */
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Overflow points to know:

Signed overflow in C is undefined behaviour, not merely a wrong answer, so the compiler is free to assume it never happens and optimise on that basis. Using unsigned types makes the wraparound defined, and adding an explicit check makes it correct:

uint64_t factorial_checked(unsigned n, bool *ok) {
    uint64_t r = 1;
    *ok = true;
    for (unsigned i = 2; i <= n; i++) {
        if (r > UINT64_MAX / i) { *ok = false; return 0; }   /* check BEFORE multiplying */
        r *= i;
    }
    return r;
}

Dividing to test rather than multiplying and then checking is the correct pattern, because the multiply that overflows has already lost the information you would need to detect it.

---

Q85. Power function?

Say this out loud Naive repeated multiplication is O(n). Exponentiation by squaring is O(log n): if the exponent is even, square the result of half the exponent, and if odd, multiply by one extra base. The critical detail is computing the half exactly once into a temporary.

double power(double x, int n) {
    if (n == 0) return 1.0;
    if (n < 0)  return 1.0 / power(x, -n);

    double half = power(x, n / 2);     /* ONE recursive call, stored */
    if (n % 2 == 0) return half * half;
    else            return half * half * x;
}

The trap

return power(x, n/2) * power(x, n/2);   /* WRONG: two calls, back to O(n) */

This looks identical and is exponentially worse, because the call tree branches instead of forming a chain. It is the same mistake as naive Fibonacci, hiding in a different costume, and interviewers plant it deliberately.

Worked trace, power(2, 10)

power(2, 10) -> half = power(2, 5)
  power(2, 5) -> half = power(2, 2)
    power(2, 2) -> half = power(2, 1)
      power(2, 1) -> half = power(2, 0) = 1
                     odd, so 1 * 1 * 2 = 2
    even, so 2 * 2 = 4
  odd, so 4 * 4 * 2 = 32
even, so 32 * 32 = 1024

4 multiplications instead of 10. For an exponent of 1000000 it is 20 multiplications instead of a million.

The iterative version, which is what you would ship

uint64_t ipow(uint64_t base, uint32_t exp) {
    uint64_t result = 1;
    while (exp > 0) {
        if (exp & 1) result *= base;   /* bit set: include this power */
        base *= base;                  /* square for the next bit position */
        exp >>= 1;
    }
    return result;
}

This is walking the binary representation of the exponent. O(log n) time, O(1) space, no recursion.

Why it matters in firmware

Modular exponentiation, which is this exact algorithm with a % m after each step, is the core operation in RSA and Diffie Hellman. Every secure boot implementation and every TLS handshake on a constrained device runs this loop. For a security oriented role, mentioning that the naive version leaks the exponent through timing, and that real implementations use a constant time ladder that performs the same operations regardless of the bit values, is a strong signal.

---

Q86. nCr by recursion?

Say this out loud Pascal’s identity: C(n, r) = C(n-1, r-1) + C(n-1, r), with base cases of r == 0 or r == n returning 1. Naively it is exponential with heavy duplication, exactly like Fibonacci, so memoize it or build Pascal’s triangle bottom up for O(n times r).

long nCr(int n, int r) {
    if (r == 0 || r == n) return 1;
    return nCr(n - 1, r - 1) + nCr(n - 1, r);
}

Why the identity is true, which is a good thing to be able to explain: pick any specific item. Either it is in your chosen subset, in which case you need r-1 more from the remaining n-1, or it is not, in which case you need all r from the remaining n-1. Those cases are disjoint and cover everything, so the counts add.

The bottom up version

long nCr_dp(int n, int r) {
    long row[64] = {0};
    row[0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = (i < r ? i : r); j > 0; j--)   /* backwards, in place */
            row[j] += row[j - 1];
    return row[r];
}

Iterating j downward is what lets a single row be updated in place, because each entry depends only on values to its left that have not been overwritten yet. That trick shows up throughout dynamic programming, most famously in the knapsack problem.

The direct multiplicative form, which avoids the whole issue

uint64_t nCr_mult(uint32_t n, uint32_t r) {
    if (r > n - r) r = n - r;          /* symmetry: C(n,r) == C(n,n-r), pick the smaller */
    uint64_t result = 1;
    for (uint32_t i = 1; i <= r; i++) {
        result = result * (n - r + i) / i;   /* exact at every step, no fractions */
    }
    return result;
}

O(r) time, O(1) space, and it never computes a factorial so it does not overflow nearly as early. The division is always exact because the product of any i consecutive integers is divisible by i factorial.

---

Q87. Recurrence relation?

Say this out loud An equation defining a function’s cost in terms of its cost on smaller inputs. Solve it by substitution, by drawing the recursion tree, or by the master theorem, which handles the common divide and conquer form directly.

The master theorem

For T(n) = a * T(n/b) + f(n), where a is the number of recursive calls, n/b is the size of each subproblem, and f(n) is the work done outside the calls, compare f(n) against n^(log_b a):

Applied to the algorithms you actually need

Note that the master theorem only applies when the subproblem is n/b, a constant fraction. Recurrences with n-1 need substitution instead, which is why Hanoi and worst case quick sort are handled separately.

The recursion tree method, for intuition

Draw merge sort’s tree. Level 0 does n work in 1 node. Level 1 does n/2 work in each of 2 nodes, so n total. Level 2 does n/4 in each of 4 nodes, so n again. Every level does n work, and there are log n levels, so the total is n log n. That picture is faster than the theorem and easier to reproduce under pressure.

---

Q88. Space complexity of recursion?

Say this out loud Maximum stack depth multiplied by the frame size. The frame is larger than the declared locals suggest, because it also holds saved registers, spilled temporaries, the return address, and alignment padding. I get the real number from the compiler with -fstack-usage rather than estimating it.

The full explanation

A frame typically contains:

+---------------------------+
| saved LR (return address) |  4 bytes
+---------------------------+
| saved callee registers    |  4 bytes each, r4 to r11 as needed
+---------------------------+
| local variables           |
+---------------------------+
| spilled temporaries       |  values that did not fit in registers
+---------------------------+
| outgoing arguments 5+     |  arguments beyond the first four
+---------------------------+
| alignment padding         |  to keep SP 8 byte aligned
+---------------------------+

So a function whose only local is a single int may still use 24 bytes of stack. Never estimate from the source.

Measuring it for real

arm-none-eabi-gcc -fstack-usage -O2 -c main.c
cat main.su

Produces lines such as:

main.c:42:5:fib    16    static
main.c:60:5:parse  48    dynamic

static means the compiler knows the exact frame size. dynamic means it uses a VLA or alloca and the size is unknown, which is a red flag in firmware.

Whole program worst case analysis then means finding the deepest path through the call graph and summing the frame sizes, and adding the worst case interrupt nesting on top, because an ISR pushes its own frame onto whichever stack was active.

Depth versus total calls, the distinction to state clearly

fib makes exponentially many calls but only ever holds n frames at once, because the left subtree finishes and its frames are released before the right subtree starts. Getting this right in the interview is a clear differentiator.

---

Q89. Stack overflow?

Say this out loud Recursion depth exceeds the allocated stack, so writes go past its boundary into adjacent memory. Without an MPU there is no fault at the moment it happens, so it silently corrupts a neighbouring task’s stack or control block, and the crash appears somewhere completely unrelated.

Why it is worse on embedded than on a desktop

On Linux, the stack has a guard page below it. Touching it raises a segfault immediately, pointing at the exact overflowing function. On a Cortex M with no MPU configured, the memory below a task stack is just another task’s stack. You overwrite it, both tasks continue running with corrupted data, and the failure appears minutes later in the innocent task.

Detection, in order of usefulness

1. Pattern fill and high water mark. Fill the stack with a known value at task creation, and periodically scan from the bottom to find how far the pattern has been overwritten.

#define STACK_FILL 0xA5A5A5A5u

size_t stack_high_water(const uint32_t *base, size_t words) {
    size_t used = words;
    for (size_t i = 0; i < words; i++) {
        if (base[i] != STACK_FILL) break;   /* first modified word from the bottom */
        used--;
    }
    return used;
}

FreeRTOS provides this as uxTaskGetStackHighWaterMark. If it ever reads below about 20 percent headroom, increase the stack. This is the practical answer.

2. MPU guard region. Configure a small no access region immediately below each task stack. An overflow then raises a MemManage fault at the exact instruction, with the address in MMFAR. This turns a silent corruption into an immediate, debuggable fault.

3. ARMv8-M stack limit registers. MSPLIM and PSPLIM are hardware bounds. If SP goes below the limit, the core faults immediately with no MPU region needed. Available on Cortex M23, M33, and later.

4. RTOS overflow hooks. FreeRTOS checking method 1 verifies SP against the limit at each context switch, which is cheap but only catches overflows that persist across a switch. Method 2 also checks that the last bytes of the stack still hold the fill pattern, which catches more but still not everything, since a deep frame can jump straight over the checked region.

5. Compile time analysis. -fstack-usage plus a call graph tool gives a provable worst case for code with no recursion and no indirect calls. Recursion or function pointers break the proof, which is a large part of why safety standards restrict both.

---

Q90. Recursive linked list traversal?

Say this out loud It is elegant and it is the wrong choice for firmware. The recursion depth equals the list length, so the input controls the stack depth without bound. I write the iterative version and say why.

/* the elegant version, which I would not ship */
void print_list(const node_t *n) {
    if (n == NULL) return;
    printf("%d ", n->data);
    print_list(n->next);           /* depth == list length */
}

/* the version that ships */
void print_list_iter(const node_t *n) {
    for (; n != NULL; n = n->next) printf("%d ", n->data);
}

The recursive version is actually tail recursive, so GCC at -O2 will turn it into the loop. But at -O0, which is what your debug build uses, it will not, and a 2000 node list at 24 bytes per frame needs 48 KB of stack. Your debug build crashes and your release build does not, which is the worst possible failure mode to debug.

Where recursion on a list is genuinely useful

Reverse order processing, since it gets the unwind for free (Q76 and Q103). Even there, the depth problem remains, so for a list of unknown length the iterative version with an explicit bounded stack is the correct engineering choice.

---

Q91. When is recursion a bad idea?

A checklist you can recite:

1. When the depth depends on input size. Any list, any string, any received buffer length. The input is then a control over your stack, and if the input comes from outside the device that is a denial of service vector.
2. In an interrupt handler. ISR stack budgets are tiny, and on Cortex M the ISR runs on whichever stack was active, so a deep ISR can overflow a task stack that was already nearly full.
3. In any task with a small fixed stack. Which in an RTOS is every task.
4. When the code must pass MISRA C or DO-178C. MISRA C:2012 Rule 17.2 prohibits recursion outright, because worst case stack usage cannot be proven.
5. When an equally clear loop exists. factorial and list traversal are strictly worse recursively. There is no elegance argument for a version that can crash.
6. When the same subproblem is recomputed. Naive Fibonacci. Either memoize or go bottom up.

Where recursion is the right answer

• Balanced tree operations, where depth is log n and provably under about 32 for any realistic n
• Divide and conquer where the subproblem is a fraction of the input: merge sort, quick sort
• Backtracking search, where the depth is bounded by the problem structure such as board size
• Parsers, with an explicit nesting depth limit
• Any code that runs on a host rather than a target

The complete spoken answer: I use recursion when the depth is bounded by the structure rather than by the input, and I write a loop otherwise. On a target with a 1 KB task stack and 24 byte frames I have roughly 40 levels of headroom, so a balanced tree is fine and a linked list is not.

---

Q92. Recursive binary search?

int bsearch_rec(const int *a, int lo, int hi, int key) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if      (a[mid] == key) return mid;
    else if (a[mid] <  key) return bsearch_rec(a, mid + 1, hi, key);
    else                    return bsearch_rec(a, lo, mid - 1, key);
}

Both recursive calls are tail calls, so a compiler at -O2 converts this back into the iterative loop and the stack cost disappears. At -O0 the depth is log n, which for any array that fits in a microcontroller’s memory is at most about 20 frames, so this is one of the rare cases where the recursive version is genuinely safe.

Still write the iterative one by default. It is the same number of lines and it is correct at every optimisation level.

---

Q93. How do you convert recursion to iteration?

Say this out loud Tail recursion becomes a loop that updates the parameters in place. Non tail recursion needs an explicit stack, because you must store the state that the frame would have held, plus a marker telling you which stage you were at when you return to a node.

Case 1, tail recursion. Mechanical.

/* recursive */
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

/* iterative: the parameters become loop variables */
int gcd_iter(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

The rule: replace the recursive call with an assignment to the parameters, and wrap it in a loop whose exit condition is the base case.

Case 2, single non tail call. Use an explicit stack.

Case 3, tree recursion with work after the call. This is the hard one, and the classic example is iterative postorder traversal.

Preorder is easy, because the work happens before the children:

void preorder_iter(node_t *root) {
    node_t *stack[MAX_DEPTH];
    int top = 0;
    if (root) stack[top++] = root;

    while (top > 0) {
        node_t *n = stack[--top];
        visit(n);
        if (n->right) stack[top++] = n->right;   /* right pushed first */
        if (n->left)  stack[top++] = n->left;    /* so left pops first */
    }
}

Postorder is hard, because when you pop a node you cannot tell whether you are arriving at it for the first time or returning to it after its children. That is exactly the information the return address in a stack frame was carrying for you. So you must store it explicitly:

typedef struct { node_t *n; int stage; } frame_t;

void postorder_iter(node_t *root) {
    frame_t stack[MAX_DEPTH];
    int top = 0;
    if (root) stack[top++] = (frame_t){ root, 0 };

    while (top > 0) {
        frame_t *f = &stack[top - 1];
        if (f->stage == 0) {
            f->stage = 1;
            if (f->n->left)  stack[top++] = (frame_t){ f->n->left, 0 };
        } else if (f->stage == 1) {
            f->stage = 2;
            if (f->n->right) stack[top++] = (frame_t){ f->n->right, 0 };
        } else {
            visit(f->n);
            top--;
        }
    }
}

The stage field is a hand rolled program counter. That is the general insight worth stating: converting recursion to iteration means building the call frame yourself, and the frame contains not just the locals but also the position in the function you must resume at.

Why it matters in firmware

The explicit stack is a fixed size array in .bss whose size appears in your linker map. Overflow is detectable with an if (top >= MAX_DEPTH) return -ENOSPC; and you fail cleanly instead of corrupting memory. That is the entire argument for this transformation, and it is worth saying in exactly those terms.

---

Section 6: Linked Lists

---

Q94. What is a singly linked list and what does it cost per node?

Say this out loud Nodes holding data and a pointer to the next node, with a head pointer and a null terminated tail. Insert and delete are O(1) once you are positioned, search and indexing are O(n), and you pay one pointer of overhead per node plus allocator overhead, with no memory locality.

typedef struct node {
    int          data;
    struct node *next;
} node_t;

node_t *head;

head -> [10|*] -> [20|*] -> [30|*] -> NULL

The empty list is head == NULL. That single case is the source of most of the branches in list code, and the sentinel node in Q97 is how you get rid of them.

The complexity table you must be able to produce instantly

---

Q95. What does a doubly linked list buy you over a singly linked list?

Say this out loud Each node also carries a pointer to its predecessor. That buys O(1) deletion given only a pointer to the node itself, and backward traversal, at the cost of a second pointer per node and one extra pointer update per operation.

typedef struct dnode {
    int           data;
    struct dnode *prev;
    struct dnode *next;
} dnode_t;

NULL <- [10] <-> [20] <-> [30] -> NULL

The one operation that justifies it

void dll_remove(dnode_t **head, dnode_t *n) {
    if (n->prev) n->prev->next = n->next;
    else         *head = n->next;          /* n was the head */
    if (n->next) n->next->prev = n->prev;
}

O(1), with only n in hand. In a singly linked list this is O(n) because you must walk from the head to find the predecessor. That difference is why every RTOS ready queue, timer list, and wait list is doubly linked: when a task blocks or a timer is cancelled, you have the task control block already, and removal must be constant time inside a critical section.

Cost accounting. On a 32 bit target, a doubly linked node holding a single int is 12 bytes, of which 8 is overhead. That is 200 percent overhead before the allocator adds its own header.

---

Q96. What is a circular linked list and how do you stop traversing it?

Say this out loud The last node points back to the first, so there is no NULL terminator and traversal must stop by detecting a return to the starting node rather than by hitting NULL.

    +-> [10] -> [20] -> [30] --+
    |                          |
    +--------------------------+

void circular_traverse(node_t *start) {
    if (start == NULL) return;
    node_t *p = start;
    do {
        visit(p);
        p = p->next;
    } while (p != start);          /* do-while, not while, or you never enter */
}

The do while is required. A plain while (p != start) never executes even once, since p equals start immediately.

Why anyone uses it

Round robin scheduling. Every node is reachable from every other node, and advancing is unconditional: current = current->next with no wraparound check and no end of list branch. Also useful for a repeating playlist, a menu that wraps, and a fixed pool of buffers cycled forever.

Typically you keep a pointer to the tail rather than the head, because from the tail both tail and tail->next, which is the head, are O(1), giving constant time insertion at both ends with a single pointer.

---

Q97. Why use a sentinel node in a circular doubly linked list?

Say this out loud Both directions wrap, and a dummy head node that is always present means the list is never empty from the code’s point of view. Every insertion and deletion becomes a single uniform case with no NULL checks and no head special case. This is the Linux kernel list_head.

   +--------------------------------------+
   |                                      |
   +-> [SENTINEL] <-> [10] <-> [20] <-----+

An empty list is the sentinel pointing at itself in both directions.

typedef struct list_head {
    struct list_head *next, *prev;
} list_head_t;

static inline void list_init(list_head_t *l) { l->next = l->prev = l; }

static inline void list_add(list_head_t *new, list_head_t *prev, list_head_t *next) {
    next->prev = new;
    new->next  = next;
    new->prev  = prev;
    prev->next = new;
}

static inline void list_add_tail(list_head_t *new, list_head_t *head) {
    list_add(new, head->prev, head);
}

static inline void list_del(list_head_t *n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
    n->next = n->prev = NULL;
}

Look at list_del. Two assignments. No branches at all. No check for head, no check for tail, no check for empty, because the sentinel guarantees prev and next are never NULL. That is the entire reason for the design, and being able to explain it is a strong senior signal.

The intrusive part, which is the other half of the idea

The node is embedded inside the object rather than pointing at it:

typedef struct {
    uint32_t     id;
    uint32_t     priority;
    list_head_t  link;          /* the list node lives INSIDE the task */
} task_t;

Given a list_head_t *, you recover the owning task_t * by subtracting the member offset:

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

#define list_entry(ptr, type, member) container_of(ptr, type, member)

task_t *t = list_entry(node, task_t, link);

Why intrusive lists matter enormously in firmware

• No allocation. The list node is part of the object, which already exists. Adding a task to a queue cannot fail and cannot fragment memory.
• Bounded time. Insert and remove are a fixed number of pointer writes, which is what you need inside a critical section with interrupts disabled.
• Multiple memberships. Put two list_head_t members in the struct and the same object can be in two lists simultaneously, for example a global list of all timers and a per priority ready queue.

If an interviewer asks how an RTOS manages its ready queues, this is the complete answer.

---

Q98. How do you insert a node at the head of a linked list?

void push_front(node_t **head, int v) {
    node_t *n = malloc(sizeof *n);
    if (!n) return;
    n->data = v;
    n->next = *head;       /* point the new node at the old first node */
    *head   = n;           /* then move the head */
}

The order of those two lines is the entire question. Reversing them loses the list:

*head   = n;               /* head now points at n */
n->next = *head;           /* n->next points at n itself. Infinite loop, list leaked. */

Drawn out, inserting 5 into [10, 20]:

before:  head -> [10] -> [20] -> NULL
                 new: [5|?]

step 1:  n->next = *head
         head -> [10] -> [20] -> NULL
                  ^
         [5|*] ---+

step 2:  *head = n
         head -> [5] -> [10] -> [20] -> NULL

The node_t ** is required so the function can modify the caller’s head pointer. That is Q20 applied.

O(1) always, regardless of list length. This is the operation linked lists are actually good at.

---

Q99. How do you insert a node at the tail of a linked list?

/* O(n) without a tail pointer */
void push_back(node_t **head, int v) {
    node_t *n = malloc(sizeof *n);
    if (!n) return;
    n->data = v;
    n->next = NULL;

    if (*head == NULL) { *head = n; return; }   /* empty list special case */

    node_t *p = *head;
    while (p->next != NULL) p = p->next;        /* walk to the last node */
    p->next = n;
}

Note the loop condition is p->next != NULL, not p != NULL. You must stop on the last node, not past it, because you need to write to its next field.

With a tail pointer, O(1)

typedef struct { node_t *head, *tail; size_t len; } list_t;

void list_push_back(list_t *l, node_t *n) {
    n->next = NULL;
    if (l->tail) l->tail->next = n;
    else         l->head = n;               /* was empty */
    l->tail = n;
    l->len++;
}

Maintaining a tail pointer costs 4 bytes and one assignment per operation, and it turns append from O(n) to O(1). Any list used as a FIFO queue must have one. The only cost is that removal from the middle must also update the tail if you removed the last node, which is easy to forget.

The pointer to pointer version, which removes the empty list branch entirely

void push_back_pp(node_t **head, node_t *n) {
    node_t **pp = head;
    while (*pp) pp = &(*pp)->next;     /* walk to the pointer that is NULL */
    n->next = NULL;
    *pp = n;                           /* write through it, head or tail, same code */
}

pp ends up pointing at either the caller’s head variable, if the list is empty, or at the last node’s next field. Writing through it works identically in both cases. This is the technique from Q20 and it is worth showing off.

---

Q100. How do you insert a node at a given position?

int insert_at(node_t **head, int pos, int v) {
    if (pos < 0) return -1;

    node_t **pp = head;
    for (int i = 0; i < pos; i++) {
        if (*pp == NULL) return -1;        /* position beyond the end */
        pp = &(*pp)->next;
    }

    node_t *n = malloc(sizeof *n);
    if (!n) return -1;
    n->data = v;
    n->next = *pp;
    *pp = n;
    return 0;
}

Again the double pointer collapses the head case and the middle case into one path. Position 0 leaves pp pointing at the caller’s head, which is exactly right.

O(n) because of the walk to find the position. This is the operation people mistakenly think linked lists are fast at. The insertion itself is O(1), but getting there is O(n), so unless you already hold the node pointer you have paid the same cost as an array shift. Saying that clearly is a strong differentiator, and it leads directly into Q116.

---

Q101. How do you delete a node from a linked list?

Case 1, singly linked, you have the predecessor.

void delete_after(node_t *prev) {
    node_t *victim = prev->next;
    if (!victim) return;
    prev->next = victim->next;
    free(victim);
}

Case 2, singly linked, you have only the node, and it is not the tail.

void delete_node_no_prev(node_t *n) {
    node_t *next = n->next;
    if (!next) return;                 /* cannot do this for the tail */
    n->data = next->data;              /* copy the successor's data into this node */
    n->next = next->next;              /* then unlink the successor */
    free(next);
}

O(1), and it is a classic interview question. Say the caveats without being asked: * It fails for the last node, because there is no successor to steal. * It invalidates any other pointer that was aimed at the successor, since that node is now freed while the node you were asked to delete still exists at the same address.

Case 3, the general singly linked delete by value, with the double pointer.

void delete_value(node_t **head, int v) {
    node_t **pp = head;
    while (*pp) {
        node_t *entry = *pp;
        if (entry->data == v) {
            *pp = entry->next;         /* identical code for head, middle, and tail */
            free(entry);
            return;
        }
        pp = &entry->next;
    }
}

No if (node == *head) branch anywhere. Write this version in the interview.

Case 4, doubly linked. Q95, O(1) with two assignments, or with a sentinel, two assignments and zero branches.

---

Q102. How do you reverse a linked list iteratively?

Say this out loud Three pointers. Walk forward, and at each node redirect its next to point backward. Save the next node before you overwrite the link, or you lose the rest of the list. O(n) time, O(1) space.

node_t *reverse(node_t *head) {
    node_t *prev = NULL, *cur = head;
    while (cur != NULL) {
        node_t *next = cur->next;      /* 1. SAVE, before destroying the link */
        cur->next = prev;              /* 2. REVERSE this node's pointer */
        prev = cur;                    /* 3. advance prev */
        cur = next;                    /* 4. advance cur */
    }
    return prev;                       /* prev is the new head */
}

Full trace on [1, 2, 3]

initial:   prev=NULL  cur=[1]   list: 1 -> 2 -> 3 -> NULL

iteration 1:
  next = [2]
  [1].next = NULL         NULL <- 1     2 -> 3 -> NULL
  prev = [1], cur = [2]

iteration 2:
  next = [3]
  [2].next = [1]          NULL <- 1 <- 2     3 -> NULL
  prev = [2], cur = [3]

iteration 3:
  next = NULL
  [3].next = [2]          NULL <- 1 <- 2 <- 3
  prev = [3], cur = NULL

loop ends, return prev = [3]

result: 3 -> 2 -> 1 -> NULL

Why return prev and not return cur. When the loop ends, cur is NULL, having walked off the end. prev is the last node visited, which is the original tail and therefore the new head. Getting this wrong returns NULL and is the single most common error on this question.

This is the most frequently asked linked list question in existence. You should be able to write it correctly without pausing.

---

Q103. How do you reverse a linked list recursively?

node_t *reverse_rec(node_t *head) {
    if (head == NULL || head->next == NULL) return head;   /* base: empty or single */

    node_t *new_head = reverse_rec(head->next);   /* reverse everything after me */
    head->next->next = head;                      /* my successor now points back at me */
    head->next = NULL;                            /* and I become the new tail */
    return new_head;                              /* propagate the head unchanged */
}

Understanding the key line. After the recursive call returns, everything from head->next onward is already reversed, and head->next is now the tail of that reversed portion. So head->next->next = head appends head to it.

Trace on [1, 2, 3]:

reverse_rec(1) calls reverse_rec(2) calls reverse_rec(3)
  reverse_rec(3) returns 3            (base case)

back in reverse_rec(2):  list is currently 1 -> 2 -> 3, with 3 as the reversed tail
  head=2, head->next=3
  3->next = 2      giving   3 -> 2, and 2 -> 3 still exists (a cycle for one instant)
  2->next = NULL   giving   3 -> 2 -> NULL
  return 3

back in reverse_rec(1):
  head=1, head->next=2
  2->next = 1      giving   3 -> 2 -> 1
  1->next = NULL
  return 3

O(n) time, O(n) stack. It is a good exercise in trusting the recursive call, and it is not something to ship, for exactly the reasons in Q90.

---

Q104. How do you find the middle node in a single pass?

Say this out loud Two pointers. Slow advances one node per step, fast advances two. When fast reaches the end, slow is at the middle. One pass, O(1) space.

node_t *find_middle(node_t *head) {
    node_t *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

Trace, odd length [1,2,3,4,5]

Returns 3, the exact middle. Correct.

Trace, even length [1,2,3,4]

Returns 3, the second of the two middles.

To get the first middle instead, change the condition:

while (fast->next != NULL && fast->next->next != NULL) { ... }   /* returns 2 for [1,2,3,4] */

Ask which one they want before writing. Both are correct answers to different questions, and merge sort on a linked list specifically needs the first middle so that the split makes progress on a two element list. Getting that wrong causes infinite recursion, which is a genuinely good follow up question.

Why it matters: this two speed pointer idea is the foundation of Q105, Q106, and Q112. It is one technique answering four questions.

---

Q105. How do you detect a loop in a linked list?

Say this out loud Floyd’s cycle detection. Slow moves one, fast moves two. If there is a cycle they eventually meet, because inside the cycle fast gains one position on slow every step. If there is no cycle, fast reaches NULL. O(n) time, O(1) space.

bool has_cycle(node_t *head) {
    node_t *slow = head, *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Why they must meet, which is the real question being asked

Once both pointers are inside the cycle, consider the gap from slow to fast measured forward around the cycle. Each step, slow advances 1 and fast advances 2, so the gap decreases by exactly 1 every iteration. A quantity that decreases by 1 each step and lives in the finite range 0 to cycle length must reach 0. When it is 0 they are on the same node. They cannot jump past each other, because the gap changes by exactly 1 and cannot skip 0.

That argument, stated in two sentences, is what distinguishes understanding from memorisation.

Why not a hash set. It also works, in O(n) time, but it needs O(n) memory. On a device with 8 KB of RAM, detecting a cycle in a 5000 node list with a hash set is impossible and with Floyd’s is free. Say this explicitly for an embedded role.

---

Q106. How do you find the start and length of a linked list loop?

Finding the entry point

node_t *find_cycle_start(node_t *head) {
    node_t *slow = head, *fast = head;

    while (fast && fast->next) {                 /* phase 1: find the meeting point */
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;                         /* phase 2: reset one to the head */
            while (slow != fast) {               /* now both move at ONE step */
                slow = slow->next;
                fast = fast->next;
            }
            return slow;                         /* they meet exactly at the entry */
        }
    }
    return NULL;
}

The proof, which is worth being able to give

Let: * L be the distance from the head to the cycle entry * C be the cycle length * k be the distance from the entry to the meeting point, measured forward

When they meet, slow has travelled L + k and fast has travelled L + k + nC for some whole number of extra laps n. Fast travelled exactly twice as far:

2(L + k) = L + k + nC
L + k = nC
L = nC - k

nC - k is the distance from the meeting point forward around the cycle back to the entry, plus n-1 extra full laps. So walking L steps from the head and walking L steps from the meeting point both land on the entry. That is why the second phase works and why both pointers move at the same speed in it.

Finding the cycle length

int cycle_length(node_t *meeting_point) {
    int len = 1;
    node_t *p = meeting_point->next;
    while (p != meeting_point) { p = p->next; len++; }
    return len;
}

Hold one pointer still and walk the other around until it comes back.

Why it matters in firmware

A corrupted next pointer that creates a cycle turns every list traversal into an infinite loop, which presents as a watchdog reset with no useful information. A debug build that runs cycle detection when a list operation is suspiciously slow, or a bounded traversal that gives up after MAX_NODES iterations, converts a hang into a diagnosable error. The bounded traversal is the cheaper defence and worth mentioning:

for (node_t *p = head; p && count < MAX_NODES; p = p->next, count++) { ... }
if (count >= MAX_NODES) log_error("list corruption suspected");

---

Q107. How do you remove duplicates from a sorted linked list?

From a sorted list, O(n) time, O(1) space

void remove_dups_sorted(node_t *head) {
    node_t *cur = head;
    while (cur != NULL && cur->next != NULL) {
        if (cur->data == cur->next->data) {
            node_t *dup = cur->next;
            cur->next = dup->next;
            free(dup);                 /* do NOT advance cur, there may be more dups */
        } else {
            cur = cur->next;
        }
    }
}

Not advancing cur after a deletion is the detail. [1,1,1,2] requires two consecutive deletions at the same position.

From an unsorted list

The nested version, for completeness:

void remove_dups_unsorted(node_t *head) {
    for (node_t *cur = head; cur; cur = cur->next) {
        node_t *runner = cur;
        while (runner->next) {
            if (runner->next->data == cur->data) {
                node_t *dup = runner->next;
                runner->next = dup->next;
                free(dup);
            } else {
                runner = runner->next;
            }
        }
    }
}

---

Q108. How do you insert into a sorted linked list?

void sorted_insert(node_t **head, node_t *n) {
    node_t **pp = head;
    while (*pp != NULL && (*pp)->data < n->data) {
        pp = &(*pp)->next;
    }
    n->next = *pp;
    *pp = n;
}

Eight lines, and it handles insert into an empty list, insert before the head, insert in the middle, and insert at the tail with no branches at all. Compare that with the version that tracks a prev pointer and needs an if (prev == NULL) at the end. This is the strongest single demonstration of why the double pointer technique is worth learning.

Why it matters in firmware

This is exactly how an RTOS delayed task list works. Tasks are kept sorted by wake time, so the scheduler only ever needs to examine the head to know when the next timer expires. Insertion is O(n) but happens rarely, while the check happens on every tick and is O(1). That asymmetry is the design rationale, and stating it is a good answer to “why not a heap”.

---

Q109. How do you merge two sorted linked lists?

node_t *merge_sorted(node_t *a, node_t *b) {
    node_t dummy;                      /* a stack allocated dummy head */
    node_t *tail = &dummy;
    dummy.next = NULL;

    while (a && b) {
        if (a->data <= b->data) { tail->next = a; a = a->next; }
        else                    { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = (a != NULL) ? a : b;  /* attach whatever remains, in one line */

    return dummy.next;
}

Two techniques in eight lines, both worth calling out:

1. The dummy head. Without it you need a special case for the very first append, because tail does not exist yet. With it, tail always points somewhere valid and the loop body is uniform. The dummy lives on the stack and costs nothing.
2. Attaching the remainder in O(1). Unlike arrays, you do not copy the leftover elements. You point at them. That is the one genuine advantage a linked list has in a merge.

O(m + n) time, O(1) extra space, and it is stable because <= makes ties resolve in favour of list a.

Why it matters: this is the merge step of merge sort, and merge sort is the correct sort for linked lists (Q116 and the sorting section), precisely because it never needs random access and never needs to move data.

---

Q110. How do you concatenate two linked lists?

/* O(n) without a tail pointer */
node_t *concat(node_t *a, node_t *b) {
    if (a == NULL) return b;
    node_t *p = a;
    while (p->next) p = p->next;
    p->next = b;
    return a;
}

/* O(1) with a list struct that tracks the tail */
void list_concat(list_t *a, list_t *b) {
    if (b->head == NULL) return;
    if (a->tail) a->tail->next = b->head;
    else         a->head = b->head;
    a->tail = b->tail;
    a->len += b->len;
    b->head = b->tail = NULL;          /* clear b, so ownership is unambiguous */
    b->len  = 0;
}

Clearing b is not cosmetic. If both lists still claim the same nodes, a later free of either one leaves the other holding dangling pointers, which is the shallow copy problem from the first file appearing in a new form.

The circular list version is O(1) with no tail pointer at all, because from any node’s next you can reach the head in one step if you hold the tail. That is why circular lists are often kept by tail pointer.

---

Q111. How do you find where two linked lists intersect?

The lists merge at some node and share a common tail from there on, forming a Y shape:

list A: 1 -> 2 -> 3 \
                     -> 7 -> 8 -> NULL
list B:      4 -> 5 /

Say this out loud Compute both lengths, advance the pointer into the longer list by the difference so both have the same number of nodes remaining, then walk them together until the node pointers are equal. O(m + n) time, O(1) space. Compare pointers, not values.

static int list_len(node_t *h) { int n = 0; for (; h; h = h->next) n++; return n; }

node_t *find_intersection(node_t *a, node_t *b) {
    int la = list_len(a), lb = list_len(b);

    while (la > lb) { a = a->next; la--; }    /* align the starting positions */
    while (lb > la) { b = b->next; lb--; }

    while (a != b) { a = a->next; b = b->next; }   /* walk in lockstep */
    return a;                                       /* NULL if no intersection */
}

Trace with A of length 5 and B of length 4: advance a by 1, so both have 4 nodes left. Now if they intersect, they must reach the junction on the same step, because from the junction onward the remaining lengths are identical by construction.

The elegant alternative worth mentioning

node_t *p = a, *q = b;
while (p != q) {
    p = (p == NULL) ? b : p->next;    /* when you run out, switch to the other list */
    q = (q == NULL) ? a : q->next;
}
return p;

Both pointers traverse lenA + lenB nodes in total, so they arrive at the junction simultaneously without ever computing a length. If there is no intersection, both reach NULL at the same time and the loop exits with p == q == NULL. Two lines, no length calculation. Interviewers like this one.

Compare pointers, not values. Two nodes can hold the same data without being the same node. The question is about structural sharing, so a == b is the correct test and a->data == b->data is a wrong answer.

---

Q112. How do you delete the nth node from the end in one pass?

Say this out loud Two pointers separated by n nodes. Advance the lead pointer n steps first, then advance both together until the lead reaches the end. The trailing pointer is then n from the end. One pass, O(1) space, and a dummy head removes the special case where the node to delete is the first one.

node_t *remove_nth_from_end(node_t *head, int n) {
    node_t dummy;
    dummy.next = head;

    node_t *lead = &dummy, *trail = &dummy;

    for (int i = 0; i <= n; i++) {         /* note <= : gives trail the PREDECESSOR */
        if (lead == NULL) return head;     /* n is larger than the list */
        lead = lead->next;
    }

    while (lead != NULL) {                 /* advance both until lead falls off the end */
        lead  = lead->next;
        trail = trail->next;
    }

    node_t *victim = trail->next;
    trail->next = victim->next;
    free(victim);

    return dummy.next;                     /* may differ from head, if head was removed */
}

Why i <= n and not i < n. You need trail to end at the node before the one you are deleting, since a singly linked list can only unlink through the predecessor. One extra step of the lead pointer creates that offset.

Why the dummy head matters here specifically. If n equals the list length, the node to delete is the head itself, and there is no real predecessor. The dummy provides one, so the same three lines of unlink code handle it, and dummy.next carries the possibly changed head back to the caller.

Trace, remove the 2nd from the end of [1,2,3,4,5]

after the first loop (n=2, so 3 steps from dummy): lead is at 3
walk together:
   lead=4, trail=1
   lead=5, trail=2
   lead=NULL, trail=3
victim = trail->next = 4, unlink it
result: 1 -> 2 -> 3 -> 5

---

Q113. How do you reverse a linked list in groups of k?

node_t *reverse_k_group(node_t *head, int k) {
    /* check that at least k nodes remain, otherwise leave this group alone */
    node_t *check = head;
    for (int i = 0; i < k; i++) {
        if (check == NULL) return head;    /* fewer than k left: leave as is */
        check = check->next;
    }

    /* reverse exactly k nodes, standard three pointer loop with a counter */
    node_t *prev = NULL, *cur = head;
    for (int i = 0; i < k; i++) {
        node_t *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    /* head is now the TAIL of this reversed group. Link it to the processed rest. */
    head->next = reverse_k_group(cur, k);

    return prev;                           /* prev is the new head of this group */
}

Trace on [1,2,3,4,5] with k = 2:

group 1: reverse [1,2]        -> 2 -> 1 -> (rest)
group 2: reverse [3,4]        -> 4 -> 3 -> (rest)
group 3: only [5] remains, fewer than k, left alone
result:  2 -> 1 -> 4 -> 3 -> 5

The requirement they leave out on purpose. What happens to a final group shorter than k? Two valid answers: leave it in original order, which is what the code above does, or reverse it anyway. Ask before writing. Candidates who ask score higher than candidates who guess correctly, because the question is testing requirement gathering as much as pointer manipulation.

The recursion here is depth n/k, which is unbounded in the input, so for firmware you would convert it to a loop that tracks the previous group’s tail. Mention that.

---

Q114. How do you deep copy a linked list with random pointers?

Each node has a next and an additional random pointer that can point at any node in the list, or NULL. Produce a deep copy.

typedef struct rnode {
    int           data;
    struct rnode *next;
    struct rnode *random;
} rnode_t;

The hash map approach, O(n) space. Map each original node to its copy in one pass, then use the map to set the random pointers in a second pass. Easy and usually not what they are looking for.

The interleaving approach, O(1) extra space. This is the answer.

Pass 1: weave a copy in after each original.

before:  A -> B -> C
after:   A -> A' -> B -> B' -> C -> C'

for (rnode_t *p = head; p; p = p->next->next) {
    rnode_t *copy = malloc(sizeof *copy);
    copy->data = p->data;
    copy->next = p->next;
    p->next = copy;
}

Pass 2: set the random pointers. Now the copy of any node X is simply X->next. So if A->random points at C, then A'->random must point at C', which is C->next, which is A->random->next.

for (rnode_t *p = head; p; p = p->next->next) {
    p->next->random = (p->random != NULL) ? p->random->next : NULL;
}

That single line is the whole trick. Interleaving turned “find the copy of this node” from a map lookup into a pointer dereference.

Pass 3: unweave the two lists.

rnode_t *new_head = head->next;
for (rnode_t *p = head; p; p = p->next) {
    rnode_t *copy = p->next;
    p->next = copy->next;                      /* restore the original list */
    copy->next = (p->next) ? p->next->next : NULL;  /* link the copies together */
}
return new_head;

Three passes, O(n) time, O(1) extra space beyond the copies themselves, and the original list is restored exactly. The p->random != NULL guard in pass 2 is the detail most people miss.

---

Q115. Why choose a linked list over an array?

Say this out loud When insertions and deletions at arbitrary positions dominate and you already hold the node pointer, when the total size is unpredictable, when a contiguous block cannot be allocated due to fragmentation, or when an element must belong to several lists at once through intrusive links. Otherwise the array usually wins, including in cases where the theory says otherwise.

The honest comparison

The case against, which you should make yourself

The theoretical O(1) insertion is real but almost always unreachable, because getting to the position is O(n). The overhead is 100 to 300 percent for small elements. And on any cached core, traversal is a dependent load chain that defeats prefetching, so the constant factor is often 10x worse than an array (Q118).

The result is that std::vector beats std::list for nearly every real workload, including workloads with frequent middle insertion, until the element count gets large. Being able to say this, and then explain the specific embedded cases where the list still wins, is the mark of someone who has measured rather than memorised.

---

Q116. Array versus linked list: how do the complexities compare?

The row that actually matters is “delete a known node”. That single O(1) is the entire justification for the doubly linked list in an RTOS: when a task blocks, you already hold its control block, and removing it from the ready queue must complete in bounded time with interrupts disabled.

The trap in this table. Every O(1) in the linked list columns assumes you already hold the node pointer. If you must search for it first, add O(n) and the advantage disappears. That is why the intrusive design of Q97 matters so much: it is what makes “you already hold the pointer” true in practice.

---

Q117. How much memory overhead does a linked list really cost?

Concrete numbers on a 32 bit target, storing 1000 uint32_t values:

The allocator header is the part people forget. A typical malloc stores the block size and flags in 8 bytes immediately before the returned pointer, and rounds every allocation up to an 8 byte boundary. So malloc(12) consumes 24 bytes of heap.

The consequence to state. On a part with 32 KB of RAM, the array fits four times over and the malloc backed doubly linked version does not fit at all. That is not a micro optimisation argument, it is a “does the product exist” argument.

This is also why intrusive lists win twice: no separate node allocation means no allocator header and no fragmentation, and the link fields are part of an object you were going to allocate regardless.

---

Q118. Why is a linked list slower than an array on real hardware?

Say this out loud An array walk is sequential, so one cache line fetch serves several elements and the hardware prefetcher predicts the pattern perfectly. A linked list walk is a dependent load chain: the address of the next node cannot be computed until the current node has arrived from memory, so there is no prefetching and no memory level parallelism. On a cached processor this is routinely a ten times difference with an identical instruction count.

The mechanism, spelled out

Array:

load a[0]  -> cache miss, fetches a 32 byte line containing a[0] through a[7]
load a[1]  -> HIT
...
load a[7]  -> HIT
load a[8]  -> miss, but the prefetcher already saw the pattern and issued it early

One miss per 8 elements, and even that miss is hidden by the prefetcher.

Linked list:

load node0        -> miss, wait ~100 cycles for RAM
read node0->next  -> now, finally, we know the next address
load node1        -> miss, wait ~100 cycles

The CPU cannot start the second load until the first completes, because the first load produces the address for the second. Every step pays the full memory latency in series. Nodes scattered by an allocator across the heap make it worse, since each one lands on a different line.

Where this argument does not apply, and saying so is important

On a Cortex M0, M3, or M4 there is no data cache and RAM access is single cycle from tightly coupled memory. The dependent load chain costs nothing extra, so the pointer chasing penalty largely disappears and the theoretical complexity is the real complexity. On a Cortex M7, an A series application processor, or a Linux target, the penalty is fully in effect.

Knowing which of those two worlds your part lives in, and adjusting your answer accordingly, is exactly the judgement an interviewer for a senior firmware role is testing.

---

Q119. Where are circular linked lists used in firmware?

• Round robin scheduling. Advance with current = current->next, unconditionally, forever. No end of list branch anywhere.
• Buffer pools. A fixed set of DMA buffers cycled continuously as one fills and another drains.
• Repeating menus and playlists. Wrapping is free.
• The free list in some allocators. A next fit allocator resumes searching from where it stopped last time, which a circular list expresses naturally.
• Multiplayer or multi channel turn taking. Any “whose turn is it next” logic.

The common thread is that there is no meaningful first or last element, only a current position. Whenever the concept of “the end” does not exist in the problem, a circular structure removes a branch from every operation.

---

Q120. Where does an RTOS use linked lists internally?

Where they appear in FreeRTOS, Zephyr, ThreadX, and VxWorks:

The three properties that make lists the correct choice here, and this is the complete answer to why not an array or a heap:

1. No allocation. The list node is a member of the task control block, which already exists. Enqueueing a task cannot fail and cannot fragment memory.
2. Bounded, tiny time. Insert and remove are a fixed count of pointer writes, executed with interrupts disabled. An array would need a shift, which is O(n) inside a critical section, which directly increases worst case interrupt latency.
3. Multiple membership. A task can be in a priority ready queue and simultaneously in a global list of all tasks, using two separate link members in the same struct. No copy, no cross reference table.

The FreeRTOS structure specifically

typedef struct xLIST_ITEM {
    TickType_t           xItemValue;     /* the sort key: priority or wake tick */
    struct xLIST_ITEM   *pxNext;
    struct xLIST_ITEM   *pxPrevious;
    void                *pvOwner;        /* points back at the TCB */
    void                *pvContainer;    /* which list am I currently in */
} ListItem_t;

Note pvOwner, which is FreeRTOS’s alternative to container_of: rather than computing the offset, it stores the back pointer explicitly. That costs 4 bytes per item and buys simplicity and portability. And pvContainer lets uxListRemove work without being told which list the item is in, which is what makes unblocking a task a single call.

Being able to discuss both approaches, offset arithmetic versus an explicit back pointer, and their tradeoff, is a strong answer.

---

Q121. How do you implement a free list and pool allocator?

Say this out loud Carve a static array of fixed size blocks at initialisation and thread them into a free list by storing the next pointer inside each free block’s own payload, which costs zero extra memory. Allocation pops the head, deallocation pushes it. Both are O(1) and deterministic, and fragmentation is impossible because every block is identical and interchangeable.

#define POOL_N      32
#define BLOCK_SIZE  64

typedef struct block {
    struct block *next;                 /* only valid while the block is FREE */
} block_t;

static uint8_t  pool[POOL_N][BLOCK_SIZE] __attribute__((aligned(8)));
static block_t *free_head;

void pool_init(void) {
    free_head = NULL;
    for (int i = 0; i < POOL_N; i++) {
        block_t *b = (block_t *)pool[i];
        b->next = free_head;            /* the link lives INSIDE the free block */
        free_head = b;
    }
}

void *pool_alloc(void) {
    uint32_t primask = __get_PRIMASK();
    __disable_irq();

    block_t *b = free_head;
    if (b != NULL) free_head = b->next;

    __set_PRIMASK(primask);
    return b;                           /* NULL when exhausted, caller must check */
}

void pool_free(void *p) {
    if (p == NULL) return;
    uint32_t primask = __get_PRIMASK();
    __disable_irq();

    block_t *b = (block_t *)p;
    b->next = free_head;
    free_head = b;

    __set_PRIMASK(primask);
}

The zero overhead trick. While a block is free, nobody is using its contents, so the next pointer is stored in the first 4 bytes of the payload itself. When the block is handed out, that space becomes the caller’s data. The free list therefore costs exactly nothing beyond the single free_head pointer. This is the detail that makes the answer impressive, so say it explicitly.

Why it solves every heap problem from the first file

The interrupt safety detail. Saving and restoring PRIMASK rather than blindly calling __enable_irq() at the end is what makes this nestable. If the caller already had interrupts disabled, blindly enabling them at the end would silently break their critical section. Interviewers who work on RTOS internals watch for this specific thing.

Internal fragmentation, the cost you accept. A 10 byte request still consumes a 64 byte block. That waste is the price of determinism, and it is bounded and calculable, which is exactly what external fragmentation is not.

Real world equivalents: FreeRTOS heap_4 with fixed sizes, Zephyr’s k_mem_slab, the Linux slab allocator, and lwIP’s pbuf pools.

---

Q122. Can you build a lock free linked list on a microcontroller?

Say this out loud A single producer single consumer queue can be made lock free with careful memory ordering and no atomic read modify write at all. A general lock free list needs compare and swap on the link pointers plus a solution to the ABA problem, because a node can be freed and a new node allocated at the same address between your read and your CAS. The honest answer is that I would not hand roll this unless profiling proved the lock was the bottleneck.

The ABA problem, concretely

Thread 1 reads head, sees node A, and prepares to CAS head from A to A->next which is B.
Thread 1 is preempted.

Thread 2 pops A, pops B, then pushes A back. The list is now A -> C.

Thread 1 resumes. Its CAS compares head against A. It matches, because A is back at the head.
The CAS succeeds and sets head to B.
But B was removed and possibly freed. The list is now corrupt.

The comparison succeeded even though the state changed underneath, because the pointer value returned to its original. That is ABA, and it is why a CAS on a raw pointer is not sufficient.

The standard solutions

The SPSC ring buffer, which is what you should actually offer

For the overwhelmingly common firmware case of one ISR producing and one task consuming, a ring buffer with separate head and tail indices needs no CAS and no lock at all:

typedef struct {
    uint8_t  buf[SIZE];              /* SIZE must be a power of two */
    volatile uint32_t head;          /* written ONLY by the producer */
    volatile uint32_t tail;          /* written ONLY by the consumer */
} ring_t;

bool ring_put(ring_t *r, uint8_t v) {            /* called from the ISR */
    uint32_t h = r->head;
    uint32_t next = (h + 1) & (SIZE - 1);
    if (next == r->tail) return false;           /* full */
    r->buf[h] = v;
    __DMB();                                     /* data written BEFORE the index moves */
    r->head = next;
    return true;
}

bool ring_get(ring_t *r, uint8_t *out) {         /* called from the task */
    uint32_t t = r->tail;
    if (t == r->head) return false;              /* empty */
    *out = r->buf[t];
    __DMB();
    r->tail = (t + 1) & (SIZE - 1);
    return true;
}

It is safe because each index has exactly one writer, and each side only ever reads the other’s index. The __DMB() ensures the data write is visible before the index update that advertises it, which volatile alone does not guarantee (Q15 in the first file).

Offering this instead of a lock free list, and explaining that it covers the real use case with far less risk, is a much stronger answer than reciting hazard pointers.

---

Q123. What are the real embedded uses of linked lists?

• Deferred work queues. An ISR does the minimum, enqueues a work item, and returns. A task drains the queue at thread priority. This is the standard way to keep interrupt latency bounded.
• DMA descriptor chains. Each descriptor holds a source, destination, length, and the address of the next descriptor. The DMA controller walks the list in hardware with no CPU involvement, which is how scatter gather transfers work.
• Network buffer chains. One packet may span several fixed size buffers, chained together, so a 1500 byte frame does not need a contiguous 1500 byte allocation. lwIP’s pbuf and the kernel’s sk_buff both do this.
• Timer and timeout lists. Sorted by expiry, so the tick handler checks only the head.
• Callback and event registration. Modules register handlers at init and the dispatcher walks the list on each event.
• Filesystem block chains. FAT is literally a linked list of cluster numbers, which is why seeking in a FAT file is O(n) in the cluster index.
• Free lists in every pool allocator. Q121.
• Message queues between tasks. Though in practice these are usually ring buffers, for the cache and allocation reasons in Q118 and Q121.

The pattern worth naming: linked lists appear in firmware wherever the elements already exist as allocated objects and the operation you need is O(1) splice or unsplice. They do not appear where you need to iterate a large homogeneous dataset, which is where arrays and ring buffers win.

---

Quick revision sheet, questions 74 to 123

---

---

All seven parts of the guide

• Part 1: C Fundamentals, Pointers and Memory — Q1 to Q35
• Part 2: Arrays and Strings — Q36 to Q73
• Part 3: Recursion and Linked Lists — Q74 to Q123 (you are here)
• Part 4: Stack and Queue — Q124 to Q153
• Part 5: Trees and Binary Search Trees — Q154 to Q188
• Part 6: Heap and Sorting — Q189 to Q218
• Part 7: Hashing and Complexity — Q219 to Q248

Start here: The Embedded Firmware DSA Interview Guide, all 248 questions indexed in one place. Architecture round: Firmware Architecture Interview Questions: 100 Q&A.

---

Work with us

Kalapi Infotech builds firmware for connected embedded products — architecture and BSP work, RTOS and bare-metal development, secure boot and OTA infrastructure. If you are hiring for these roles, or building a product that needs them, we would be glad to talk.

Get in touch with our firmware team →