You are Here
Embedded DSA Interview Questions: Arrays and Strings (Q36–Q73)
DSA Embedded System Interview

Embedded DSA Interview Questions: Arrays and Strings (Q36–Q73)

32 min read

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

Array and string interview questions look like the easy round, and they are where most candidates quietly lose points: on bounds, on the null terminator, and on what sizeof does once an array has decayed to a pointer. Thirty-eight questions, answered with the firmware consequences spelled out.

Array and string interview questions in this part

Questions 36 to 73, explained fully. Same layout as the previous file.

Section 3: Arrays

Q36. Static vs dynamic array?

Say this out loud A static array has its size fixed at compile time and lives in .bss, .data, or on the stack. A dynamic array has its size chosen at runtime and lives on the heap, so it can be resized by allocating a bigger block and copying. There is a third case, the variable length array, which is stack allocated with a runtime size, and it is banned in most firmware coding standards.

The full explanation

Three ways to get an array in C, and they behave completely differently.

One, static or global array.

uint8_t buffer[1024];              /* file scope, lives in .bss, 1 KB RAM, 0 flash */
static uint8_t rx[256];            /* same, but private to this file */

Exists for the whole program. Size is baked into the binary. Cannot fail at runtime. This is what firmware uses for almost everything.

Two, automatic array.

void f(void) {
    uint8_t temp[64];              /* on the stack, gone when f returns */
}

Cheap to create, one SP subtraction, but it consumes stack you may not have. A 512 byte local array inside a FreeRTOS task with a 1 KB stack is already dangerous.

Three, dynamic array.

uint8_t *p = malloc(n);            /* size decided at runtime, on the heap */
free(p);

Flexible, resizable, and carries every heap problem from the previous file: non deterministic timing, fragmentation, and the possibility of returning NULL.

Four, the one to avoid, the variable length array.

void f(int n) {
    uint8_t temp[n];               /* C99 VLA, size from a runtime value */
}

This looks like a free lunch. It is not. The stack has no capacity check. If n comes from a packet length field and an attacker sends 100000, you walk off the end of the stack and corrupt whatever is below it. MISRA C bans it, the Linux kernel removed every instance of it, and you should treat it as forbidden.

Comparison

Static or global Automatic Dynamic
Size known compile time compile time runtime
Lives in .bss or .data stack heap
Lifetime whole program the enclosing block until you free it
Allocation cost zero, exists at boot one SP subtraction search the free list
Can fail no no, it silently overflows yes, returns NULL
Resizable no no yes, by realloc and copy
Fragments memory no no yes

Why it matters in firmware

The static array is the default answer, and being able to say why is the point. A statically sized array proves at link time that the memory exists. The linker map file tells you exactly how much RAM the whole image needs, and if it does not fit, the build fails on your desk instead of the product failing in the field. That guarantee is worth far more than the flexibility you give up.

Mistakes people make

Saying “I would use malloc” for an embedded question without qualifying it. The expected answer is a fixed sized static buffer, or a pool of fixed sized blocks, with dynamic allocation only during initialization if at all.

Q37. Array representation in memory?

Say this out loud A contiguous block of identically sized elements. Element i is at base + i * sizeof(element). There is no length stored anywhere and no bounds checking, which is why the length must always be carried alongside the pointer.

The full explanation

uint32_t arr[5] = {10, 20, 30, 40, 50};    /* suppose base is 0x2000_0000 */
address        value     index
0x2000_0000  |  10  |     arr[0]
0x2000_0004  |  20  |     arr[1]
0x2000_0008  |  30  |     arr[2]
0x2000_000C  |  40  |     arr[3]
0x2000_0010  |  50  |     arr[4]
0x2000_0014  |  ??  |     arr[5]  <-- out of bounds, no error, just other memory

Three consequences follow directly from this picture, and they explain almost everything about arrays.

  1. Indexing is O(1). The address is one multiply and one add, both single cycle. It does not matter whether you want element 0 or element 9999.
  2. There is no length. The array itself stores only the data. sizeof(arr) works only where the compiler can still see the declaration. The moment you pass it to a function it decays to a pointer and the size information is gone.
  3. There is no bounds check. arr[5] compiles fine and reads whatever is next in memory. arr[-1] also compiles. This is the single largest source of memory corruption in C.

The decay rule, demonstrated

void f(uint32_t a[5]) {
    printf("%zu\n", sizeof(a));      /* 4, the size of a pointer */
}

int main(void) {
    uint32_t arr[5];
    printf("%zu\n", sizeof(arr));    /* 20, the real array size */
    f(arr);
}

So the number of elements is sizeof(arr) / sizeof(arr[0]), and that expression is only valid in the scope where the array was declared. The safe macro, which fails to compile if you accidentally hand it a pointer, is worth memorising:

#define ARRAY_SIZE(a) (sizeof(a) / sizeof((a)[0]))

Why it matters in firmware

Contiguity is why arrays are so much faster than linked lists on any core with a cache: one cache line fetch brings in the next several elements for free, and the prefetcher can see the pattern. It is also why an array can be handed directly to a DMA engine, which needs a base address and a length and cannot follow pointers.

Q38. Row major formula?

Say this out loud For a two dimensional array A[m][n] of element size w, in row major order the address of element (i, j) is base + (i * n + j) * w. C, C++, Python, and Java are all row major.

The full explanation

A two dimensional array is a fiction. Memory is one dimensional, so the compiler must flatten it. Row major means row 0 is laid out completely, then row 1, then row 2.

Worked example

int A[3][4];       /* 3 rows, 4 columns, w = 4 bytes, base = 0x2000_0000 */

Layout in memory:

index:   A[0][0] A[0][1] A[0][2] A[0][3] A[1][0] A[1][1] ... A[2][3]
offset:     0       4       8      12      16      20    ...   44

Address of A[2][1]:

base + (i * n + j) * w
= 0x20000000 + (2 * 4 + 1) * 4
= 0x20000000 + 9 * 4
= 0x20000000 + 36
= 0x20000024

Verify by counting: rows 0 and 1 take 8 elements, then A[2][0] is element 8, A[2][1] is element 9. Correct.

With non zero lower bounds

Some languages let you declare A[1..3][1..4]. The general formula subtracts the lower bounds first:

addr(i, j) = base + ((i - l1) * n + (j - l2)) * w

where n is the number of columns, l1 is the first row index and l2 is the first column index. C always has l1 = l2 = 0, which collapses it to the simple form.

Three dimensions

addr(i, j, k) = base + ((i * n2 + j) * n3 + k) * w

for A[n1][n2][n3]. The pattern generalises: each index multiplies by the product of all the dimensions to its right.

Why it matters in firmware

Cache and locality. Compare these two loops over int A[1000][1000]:

/* fast: consecutive addresses */
for (i = 0; i < 1000; i++)
    for (j = 0; j < 1000; j++)
        sum += A[i][j];

/* slow: strides 4000 bytes each step */
for (j = 0; j < 1000; j++)
    for (i = 0; i < 1000; i++)
        sum += A[i][j];

The first walks memory in order, so each 32 byte cache line fetch serves 8 elements. The second touches one element per cache line and evicts the line before coming back to it. On an application processor the difference is routinely five to ten times, with identical instruction counts. This is a favourite interview question because the two loops look equivalent and are not.

Mistakes people make

Writing A[i][j] where they meant A[j][i] in image processing code. It still runs, produces a transposed or garbled result, and the slowdown is often what tips you off first.

Q39. Column major formula?

Say this out loud Column major stores column 0 completely, then column 1, and so on. The address of (i, j) is base + (j * m + i) * w where m is the number of rows. Fortran, MATLAB, R, and most BLAS libraries use column major.

The full explanation

Same array, different flattening.

int A[3][4];   /* 3 rows, 4 cols */

Row major layout:

A[0][0] A[0][1] A[0][2] A[0][3] | A[1][0] ... | A[2][0] ...

Column major layout:

A[0][0] A[1][0] A[2][0] | A[0][1] A[1][1] A[2][1] | A[0][2] ...

Address of A[2][1] in column major:

base + (j * m + i) * w
= base + (1 * 3 + 2) * 4
= base + 5 * 4
= base + 20

Count to check: column 0 holds 3 elements at offsets 0, 1, 2. Then A[0][1] is element 3, A[1][1] is 4, A[2][1] is 5. Correct.

Why anyone would do this

Historical, and mathematical. Fortran chose it, and the entire numerical linear algebra ecosystem, LAPACK and BLAS, followed. Matrix algorithms are often expressed column by column, so column major makes those loops sequential.

Why it matters in firmware

When you call a DSP or math library that was ported from Fortran, or when you exchange a matrix with MATLAB generated code, the ordering convention is the interface. Getting it wrong gives you a transposed matrix, which for a symmetric matrix silently works and for anything else silently does not. CMSIS-DSP uses row major, so if you feed it MATLAB exported data you must transpose first.

Q40. Time complexity of insertion in an array?

Say this out loud O(1) at the end if capacity remains, O(n) anywhere else because every element after the insertion point must shift up by one. Inserting at the front is the worst case, a full n element shift.

The full explanation

There is no such thing as making room in the middle of a contiguous block. You physically move the data.

Worked example, insert 99 at index 2

start:   [10][20][30][40][50][  ]     n = 5, capacity 6

shift from the END backwards, or you overwrite unread data:
         [10][20][30][40][  ][50]     move index 4 to 5
         [10][20][30][  ][40][50]     move index 3 to 4
         [10][20][  ][30][40][50]     move index 2 to 3

write:   [10][20][99][30][40][50]     n = 6
int insert_at(int *a, int *n, int cap, int pos, int val) {
    if (*n >= cap || pos < 0 || pos > *n) return -1;
    for (int i = *n; i > pos; i--) {
        a[i] = a[i - 1];              /* backwards, always backwards */
    }
    a[pos] = val;
    (*n)++;
    return 0;
}

The direction is the detail that matters. Copying forward would overwrite a[3] before you had read it.

Complexity by position

Insert at Elements moved Complexity
end 0 O(1)
middle n/2 on average O(n)
front n O(n)

Why it matters in firmware

memmove does this shift far faster than a byte loop, because it moves words at a time and the library version is hand tuned in assembly. If you find yourself writing a shift loop, use memmove instead:

memmove(&a[pos + 1], &a[pos], (size_t)(*n - pos) * sizeof(a[0]));
a[pos] = val;

Note it must be memmove and not memcpy, since source and destination overlap. That is exactly the distinction from Q34 in the previous file.

Q41. Time complexity of deletion?

Say this out loud O(1) at the end, O(n) anywhere else for the shift down. If the order of elements does not matter, swap the last element into the hole and decrement the count, which is O(1).

The full explanation

Ordered deletion, delete index 1

start:   [10][20][30][40][50]     n = 5
         [10][30][30][40][50]     move 2 to 1
         [10][30][40][40][50]     move 3 to 2
         [10][30][40][50][50]     move 4 to 3
result:  [10][30][40][50][ - ]    n = 4

Forward direction this time, because you are closing a gap rather than opening one.

void delete_at(int *a, int *n, int pos) {
    for (int i = pos; i < *n - 1; i++) {
        a[i] = a[i + 1];
    }
    (*n)--;
}

Unordered deletion, the O(1) trick

start:   [10][20][30][40][50]     n = 5, delete index 1
         [10][50][30][40][50]     copy last into the hole
result:  [10][50][30][40][ - ]    n = 4
void delete_unordered(int *a, int *n, int pos) {
    a[pos] = a[*n - 1];
    (*n)--;
}

Why it matters in firmware

This swap and shrink is exactly how you manage an array of active objects: connected BLE peers, registered callbacks, open sockets, active timers. Order carries no meaning, so removal is constant time and there is no shifting cost inside a critical section. Whenever an interviewer asks how you would manage a table of active connections, this is the answer.

The one caution is that any index you handed out earlier becomes stale, because an element moved. So iterate carefully:

for (int i = 0; i < n; ) {
    if (should_remove(&a[i])) {
        a[i] = a[--n];            /* do NOT increment i, a new element is now here */
    } else {
        i++;
    }
}

Q42. Binary search?

Say this out loud Repeatedly halve a sorted range by comparing the middle element to the key. O(log n) time, O(1) space iteratively. Compute the midpoint as lo + (hi - lo) / 2 to avoid overflow, and decide up front whether you want any match, the first match, or the insertion point, because the three loops differ.

The full explanation

Every comparison eliminates half the remaining candidates. Starting from n, after k steps you have n / 2^k left, and you are done when that reaches 1, so k = log2(n). For a million elements that is 20 comparisons. For four billion it is 32. That is the whole appeal.

Worked trace, searching for 40 in [10, 20, 30, 40, 50, 60, 70]

Step lo hi mid a[mid] Action
1 0 6 3 40 equal, found at index 3

Now search for 60:

Step lo hi mid a[mid] Action
1 0 6 3 40 40 < 60, go right, lo = 4
2 4 6 5 60 equal, found at index 5

Now search for 45, which is absent:

Step lo hi mid a[mid] Action
1 0 6 3 40 40 < 45, lo = 4
2 4 6 5 60 60 > 45, hi = 4
3 4 4 4 50 50 > 45, hi = 3
4 lo=4 > hi=3 loop ends, not found

The plain version

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

The overflow detail interviewers wait for

(lo + hi) / 2 overflows when lo + hi exceeds INT_MAX. On a 32 bit machine with arrays over a billion elements that is real, and it was a genuine bug in the JDK’s binary search for nine years. lo + (hi - lo) / 2 is mathematically identical and cannot overflow because hi - lo is at most the array size. Say this in the interview even if the arrays are small. It signals that you have read about the problem rather than memorised the loop.

The half open version, which handles first match and insertion point

/* returns the index of the first element >= key, which is the insertion point */
int lower_bound(const int *a, int n, int key) {
    int lo = 0, hi = n;              /* note hi = n, and the range is [lo, hi) */
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < key) lo = mid + 1;
        else              hi = mid;
    }
    return lo;                       /* 0..n, n means key is larger than everything */
}

This one version answers three questions at once: * is the key present: lo < n && a[lo] == key * index of the first occurrence in a array with duplicates: lo * where to insert to keep the array sorted: lo

Learn this version. It is shorter, it has no -1 and +1 asymmetry to get wrong, and it is what std::lower_bound does.

Why it matters in firmware

Lookup tables are everywhere: calibration curves, gamma tables, command dispatch by opcode, timezone rules. A sorted const table in flash plus a binary search gives O(log n) lookup at zero RAM cost. For a 256 entry command table that is 8 comparisons instead of 128 on average for a linear scan.

That said, for very small tables the linear scan often wins in practice, because it is branch predictable and cache friendly while binary search jumps around. The crossover is typically somewhere between 8 and 64 elements depending on the core. Mentioning that you would measure rather than assume is a strong answer.

Mistakes people make

  • Infinite loops from lo = mid instead of lo = mid + 1. If mid equals lo and you do not advance, you never terminate.
  • Forgetting that the array must be sorted by the same comparison you are searching with.
  • Using it on a linked list, where getting to the middle is already O(n) and the whole benefit evaporates.

Q43. Why does binary search require a sorted array?

Say this out loud Because the algorithm throws away half the data based on a single comparison. That is only valid if the comparison at the midpoint tells you something true about every element in the discarded half. Sortedness is exactly that guarantee.

The full explanation

Say a[mid] < key. In a sorted array, that one fact implies a[0] through a[mid] are all less than the key, so none of them can be the answer, so discarding them loses nothing. In an unsorted array it implies nothing at all about any other element, so discarding them may throw away the answer.

Worked counterexample

unsorted: [50, 10, 40, 30, 20]     search for 10
mid = 2, a[2] = 40, 40 > 10, so "go left" to [50, 10]

That happens to work here by luck. Now search for 20:

mid = 2, a[2] = 40, 40 > 20, so go left to [50, 10]

20 is in the right half, which you just discarded. The answer is reported as not found even though it is present.

The cost tradeoff worth mentioning

Sorting costs O(n log n). Binary search saves you O(n) per lookup, reducing it to O(log n). So sorting only pays off if you search many times. One search of an unsorted array is O(n) linear scan, which beats sorting then searching. The breakeven is roughly log n searches.

In firmware this almost always resolves in favour of sorting at build time. A const table in flash is sorted by the developer or by a code generator, costs nothing at runtime, and every lookup is logarithmic forever.

Q44. Reverse an array?

Say this out loud Two indices, one at each end, swap and walk inward until they meet. n/2 swaps, O(n) time, O(1) space.

The full explanation

void reverse(int *a, int n) {
    int i = 0, j = n - 1;
    while (i < j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
        i++; j--;
    }
}

Worked trace on [10, 20, 30, 40, 50]

i j Array after the swap
0 4 [50, 20, 30, 40, 10]
1 3 [50, 40, 30, 20, 10]
2 2 i < j is false, stop

The middle element of an odd length array never moves, which is correct.

Why i < j and not i != j

For an even length array the indices cross without ever being equal. With n = 4: (0,3), (1,2), then (2,1). They never meet at the same value, so i != j loops forever and swaps the array back to where it started and onwards. Always use i < j.

Why it matters in firmware

Endianness conversion is exactly this operation on 4 bytes, and the correct answer there is the CPU instruction rather than a loop:

uint32_t swapped = __builtin_bswap32(value);      /* becomes REV on ARM, one cycle */

Reversal is also the building block for rotation, which is the next question.

Q45. Rotate an array?

Say this out loud The reversal algorithm. To rotate left by k: reverse the first k elements, reverse the remaining n minus k, then reverse the whole array. O(n) time, O(1) space, and every pass is sequential so it is cache friendly.

The full explanation

Worked example, rotate [1, 2, 3, 4, 5, 6, 7] left by 3

Target result: [4, 5, 6, 7, 1, 2, 3]

start:                  [1, 2, 3, 4, 5, 6, 7]
reverse first k = 3:    [3, 2, 1, 4, 5, 6, 7]
reverse the rest:       [3, 2, 1, 7, 6, 5, 4]
reverse the whole:      [4, 5, 6, 7, 1, 2, 3]     correct

Why it works

Think of the array as two blocks, A of length k and B of length n minus k. You start with AB and you want BA. Reversing each block gives A’ B’. Reversing the whole of that gives (A'B')' which is B'' A'' which is BA, since reversing twice returns the original. That is the entire proof and it is worth being able to state it.

static void rev(int *a, int i, int j) {
    while (i < j) { int t = a[i]; a[i++] = a[j]; a[j--] = t; }
}

void rotate_left(int *a, int n, int k) {
    if (n <= 1) return;
    k %= n;                     /* handle k > n and k == n */
    if (k == 0) return;
    rev(a, 0, k - 1);
    rev(a, k, n - 1);
    rev(a, 0, n - 1);
}

Rotating right by k is the same as rotating left by n - k.

The alternatives, and why reversal wins

Method Time Space Notes
Rotate by one, k times O(n * k) O(1) Simple, unacceptably slow for large k
Temp buffer O(n) O(k) Needs extra memory, which firmware may not have
Juggling by gcd cycles O(n) O(1) Fewer writes, but jumps around memory and thrashes cache
Reversal O(n) O(1) 3 sequential passes, roughly 1.5n swaps, best real world choice

The juggling algorithm looks better on paper because it touches each element once instead of three times. In practice reversal usually wins on hardware, because three sequential passes are prefetched perfectly while gcd cycles stride unpredictably. Being able to say that is a strong differentiator.

Why it matters in firmware

This is what a circular buffer does implicitly, without moving anything. A ring buffer rotates the view by moving read and write indices instead of moving data, which is O(1) instead of O(n). If an interviewer asks you to rotate a buffer in an embedded context, the best answer is often “I would not move the data at all, I would use a ring buffer”.

Q46. Find the missing number?

Say this out loud For the numbers 1 to n with exactly one missing, either subtract the array sum from n(n+1)/2, or XOR everything together with 1 to n. XOR is the better answer because it cannot overflow.

The full explanation

Method one, the sum.

The sum of 1 to n is n * (n + 1) / 2. Subtract what you actually have and the difference is the missing value.

int missing_sum(const int *a, int n) {     /* array holds n-1 of the numbers 1..n */
    long expected = (long)n * (n + 1) / 2;
    long actual = 0;
    for (int i = 0; i < n - 1; i++) actual += a[i];
    return (int)(expected - actual);
}

Trace with n = 5, array [1, 2, 4, 5]: expected is 15, actual is 12, missing is 3.

The weakness is overflow. With n = 100000 and 32 bit ints, n(n+1)/2 is about 5 billion, which does not fit in a signed 32 bit int. The fix is a wider accumulator or the next method.

Method two, XOR. This is the one to give.

XOR has two properties that make it perfect here: * x ^ x = 0, a value cancels itself * x ^ 0 = x, and XOR is commutative and associative, so order does not matter

So if you XOR every number from 1 to n together with every number actually present, every present number appears exactly twice and cancels, leaving only the one that appeared once.

int missing_xor(const int *a, int n) {
    int x = 0;
    for (int i = 1; i <= n; i++) x ^= i;        /* all expected values */
    for (int i = 0; i < n - 1; i++) x ^= a[i];  /* all present values */
    return x;
}

Trace with n = 4, array [1, 2, 4]:

1 ^ 2 ^ 3 ^ 4  = 4
4 ^ (1 ^ 2 ^ 4) = 4 ^ 7 = 3     correct

No overflow is possible, because XOR never produces a value wider than its inputs. Same O(n) time, same O(1) space, and it works for any integer width.

Variants you should expect as follow ups

  • Two numbers missing. XOR everything to get a ^ b. Find any set bit in that result, which is a bit where a and b differ. Partition all values by that bit and XOR each group separately, which isolates a and b.
  • One duplicate instead of one missing. Identical XOR approach, the duplicate is the value left over.
  • Range is 0 to n rather than 1 to n. Include 0 in the loop, which changes nothing since x ^ 0 = x.

Why it matters in firmware

XOR is one instruction, works on any width, cannot overflow, and needs no division. Sequence number gap detection in a protocol, checksum validation, and parity are all the same idea. And the wider point is worth saying: understanding XOR’s cancellation property lets you solve a whole family of problems in constant space, which matters far more when the space you have is 8 KB than when it is 8 GB.

Q47. Duplicate detection?

Say this out loud It depends on the constraints, and the constraints are the interesting part. Sorting gives O(n log n) time with O(1) extra space. A hash set gives O(n) time with O(n) space. If the values are bounded and small, a bitmap gives O(n) time in fixed tiny space, and that is the embedded answer. If the values are exactly 1 to n and you may modify the array, index marking gives O(n) time and O(1) space.

The full explanation

Approach 1, brute force. Compare every pair. O(n squared) time, O(1) space. Mention it only to dismiss it, though note that for n under about 20 it is genuinely the fastest option because there is no setup cost.

Approach 2, sort then scan.

qsort(a, n, sizeof(int), cmp);
for (int i = 1; i < n; i++)
    if (a[i] == a[i-1]) return a[i];

O(n log n) time, O(1) extra space if the sort is in place. Destroys the original order, which may or may not be acceptable.

Approach 3, hash set. O(n) time, O(n) space. The standard answer on a desktop and usually the wrong answer on a microcontroller with 8 KB of RAM.

Approach 4, the bitmap. This is the embedded answer.

If values fall in a known small range, allocate one bit per possible value.

#define MAX_VAL 1024
static uint32_t seen[MAX_VAL / 32];        /* 1024 bits = 128 bytes total */

int find_duplicate(const uint16_t *a, int n) {
    memset(seen, 0, sizeof seen);
    for (int i = 0; i < n; i++) {
        uint16_t v = a[i];
        uint32_t word = v >> 5;            /* v / 32 */
        uint32_t bit  = v & 31u;           /* v % 32 */
        if (seen[word] & (1u << bit)) return v;    /* already seen */
        seen[word] |= (1u << bit);
    }
    return -1;
}

128 bytes handles 1024 distinct values, in O(n) time, with no allocation and no hashing. Note v >> 5 and v & 31 rather than divide and modulo, which matters on a core with no hardware divider such as Cortex M0.

Approach 5, index marking. Only when the values are exactly 1 to n and the array is modifiable.

int find_dup_marking(int *a, int n) {
    for (int i = 0; i < n; i++) {
        int idx = abs(a[i]) - 1;
        if (a[idx] < 0) return abs(a[i]);   /* already visited this slot */
        a[idx] = -a[idx];                   /* mark it by flipping the sign */
    }
    return -1;
}

O(n) time, O(1) space, but it destroys the input by using the sign bit as a marker. Restoring it is a second pass of abs.

How to answer this in an interview

Do not name one method. Ask the constraints first: what is the value range, is the array modifiable, is extra memory available, does order matter. Then give the method that fits. That conversation is the actual signal being measured.

Q48. Pair sum, find two elements adding to a target?

Say this out loud If the array is sorted, two pointers from both ends in O(n) time and O(1) space. If unsorted, a hash set of complements in O(n) time and O(n) space, or sort first if memory is scarce and O(n log n) is acceptable.

The full explanation

Sorted, two pointers.

int pair_sum_sorted(const int *a, int n, int target, int *i_out, int *j_out) {
    int i = 0, j = n - 1;
    while (i < j) {
        int s = a[i] + a[j];
        if      (s == target) { *i_out = i; *j_out = j; return 1; }
        else if (s <  target) i++;          /* need a bigger sum, move the low end up */
        else                  j--;          /* need a smaller sum, move the high end down */
    }
    return 0;
}

Worked trace on [2, 7, 11, 15, 20], target 22

i j a[i] a[j] sum Action
0 4 2 20 22 found, indices 0 and 4

Target 26:

i j a[i] a[j] sum Action
0 4 2 20 22 too small, i = 1
1 4 7 20 27 too large, j = 3
2 3 11 15 26 found

Why the two pointer move is correct

This is the part interviewers push on. If the sum is too small, a[i] paired with the largest available element is still too small, so a[i] cannot participate in any solution and can be discarded permanently. Symmetrically if the sum is too large, a[j] paired with the smallest element is still too large, so a[j] is out. Each step eliminates exactly one candidate, so the loop runs at most n times.

Unsorted, hash set of complements.

/* for each element, ask whether target - element has already been seen */
for (int i = 0; i < n; i++) {
    if (set_contains(seen, target - a[i])) return 1;
    set_insert(seen, a[i]);
}

One pass, O(n), at the cost of a hash table.

Firmware variant. If the values are small and bounded, replace the hash set with the bitmap from Q47. 128 bytes of static memory, one pass, no allocation. That is the version to write on the whiteboard for an embedded role.

Q49. Merge two sorted arrays?

Say this out loud Walk both with separate indices, always taking the smaller head, then copy whatever remains from the array that is not exhausted. O(m + n) time. If merging into the larger array in place, fill from the back so you never overwrite an element you have not read yet.

The full explanation

void merge(const int *a, int m, const int *b, int n, int *out) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        out[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
    }
    while (i < m) out[k++] = a[i++];      /* drain whichever is left */
    while (j < n) out[k++] = b[j++];
}

<= rather than < is what makes the merge stable, meaning equal elements keep their original relative order with the first array winning ties. That matters when merge sort is built on top of this, which is exactly why merge sort is stable and quick sort is not.

Worked trace, a = [1, 3, 5], b = [2, 3, 8]

i j a[i] b[j] Taken out
0 0 1 2 a, 1 [1]
1 0 3 2 b, 2 [1,2]
1 1 3 3 a, 3 (tie goes left) [1,2,3]
2 1 5 3 b, 3 [1,2,3,3]
2 2 5 8 a, 5 [1,2,3,3,5]
3 2 done 8 drain b [1,2,3,3,5,8]

The in place variant, which is the actual interview question

Array a has capacity m + n with the first m slots filled. Merge b into it.

void merge_in_place(int *a, int m, const int *b, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && a[i] > b[j]) a[k--] = a[i--];
        else                       a[k--] = b[j--];
    }
}

Filling from the back is the trick. The tail of a is empty, so writing there destroys nothing. Going forward would overwrite a[0] with b[0] before you had read a[0].

Note that only j >= 0 is needed as the loop condition. If i runs out first, the remaining elements of b get copied. If j runs out first, the remaining elements of a are already in their correct final positions, so there is nothing to do.

Why it matters in firmware

This is the merge step of merge sort, and merge sort is the sort you choose for linked lists and for external data too large to fit in RAM, both of which come up in embedded work. It is also how you combine two sorted sensor sample streams by timestamp.

Q50. Union of two sorted arrays?

Say this out loud The same merge walk, but skip duplicates: within each array and between the two. O(m + n) time.

int set_union(const int *a, int m, const int *b, int n, int *out) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if      (a[i] < b[j]) out[k++] = a[i++];
        else if (b[j] < a[i]) out[k++] = b[j++];
        else { out[k++] = a[i]; i++; j++; }     /* equal, emit once, advance both */
    }
    while (i < m) out[k++] = a[i++];
    while (j < n) out[k++] = b[j++];
    return k;                                   /* number of elements written */
}

Trace a = [1, 3, 5, 7], b = [3, 4, 5], giving [1, 3, 4, 5, 7].

If the inputs may contain internal duplicates, add a check against the last written value before each emit.

For unsorted inputs, either sort first for O(n log n) or use a hash set for O(n) time and O(n) space.

Q51. Intersection of two sorted arrays?

Say this out loud Same walk, but only emit when both sides are equal, and advance the smaller side otherwise. O(m + n). If one array is far smaller than the other, binary search each of its elements in the larger one for O(m log n) instead.

int intersect(const int *a, int m, const int *b, int n, int *out) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if      (a[i] < b[j]) i++;
        else if (b[j] < a[i]) j++;
        else { out[k++] = a[i]; i++; j++; }
    }
    return k;
}

The size asymmetry point, which is the good answer

If m is 10 and n is 1000000, the merge walk still costs a million steps because it must scan all of b. Binary searching each of the 10 elements costs 10 * log2(1000000) which is about 200 operations. So:

  • similar sizes, use the merge walk, O(m + n)
  • very different sizes, binary search the small one into the large one, O(m log n)

Knowing when to switch is what separates a memorised answer from an understood one.

Q52. Difference of two sorted arrays?

Say this out loud Same walk again. Emit elements of A that have no match in B. Advance both on equality without emitting.

int difference(const int *a, int m, const int *b, int n, int *out) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if      (a[i] < b[j]) out[k++] = a[i++];   /* in A, not yet seen in B */
        else if (b[j] < a[i]) j++;                 /* in B only, ignore */
        else { i++; j++; }                         /* in both, exclude */
    }
    while (i < m) out[k++] = a[i++];               /* rest of A has no match */
    return k;
}

Notice that questions 49 through 52 are one algorithm with four different emit rules. Say that out loud in the interview. Recognising the shared structure is worth more than reciting four separate functions.

Operation On a[i] < b[j] On a[i] > b[j] On equal
Merge emit a emit b emit both
Union emit a emit b emit one
Intersection skip a skip b emit one
Difference (A minus B) emit a skip b skip both

Q53. Find max and min in one pass?

Say this out loud The naive loop costs 2n comparisons. Processing elements in pairs costs 3n/2, which is the theoretical minimum. Compare the two elements of the pair against each other first, then the smaller against the running minimum and the larger against the running maximum.

The full explanation

Naive: 2 comparisons per element, so 2n total.

for (int i = 1; i < n; i++) {
    if (a[i] > max) max = a[i];
    if (a[i] < min) min = a[i];
}

Pairwise: 3 comparisons per 2 elements, so 1.5n total.

void min_max(const int *a, int n, int *mn, int *mx) {
    int i;
    if (n == 0) return;

    if (n & 1) {                       /* odd count: seed with the first element */
        *mn = *mx = a[0];
        i = 1;
    } else {                           /* even: seed with the first pair, 1 comparison */
        if (a[0] < a[1]) { *mn = a[0]; *mx = a[1]; }
        else             { *mn = a[1]; *mx = a[0]; }
        i = 2;
    }

    while (i < n - 1) {
        int lo, hi;
        if (a[i] < a[i+1]) { lo = a[i]; hi = a[i+1]; }   /* comparison 1 */
        else               { lo = a[i+1]; hi = a[i]; }
        if (lo < *mn) *mn = lo;                          /* comparison 2 */
        if (hi > *mx) *mx = hi;                          /* comparison 3 */
        i += 2;
    }
    if (i < n) {                       /* leftover element */
        if (a[i] < *mn) *mn = a[i];
        if (a[i] > *mx) *mx = a[i];
    }
}

Why it works. The smaller of a pair cannot possibly be the maximum, and the larger cannot be the minimum. So the first comparison eliminates half the work of the other two. Three comparisons handle two elements instead of four.

Honesty about the real world, which is worth saying

The saving is 25 percent of comparisons but the code is longer and has more branches. On a modern core with branch prediction, the naive version may actually be faster because both if statements are usually not taken and predict perfectly, while the pairwise version has an unpredictable branch. On a small in order core with no predictor, the pairwise version genuinely wins. Saying that you know the theoretical answer and would still measure is the strongest response.

Q54. Check whether an array is sorted?

Say this out loud One pass, compare each element to its predecessor, return false on the first violation. O(n) worst case, O(1) best case if it fails early, O(1) space.

bool is_sorted_asc(const int *a, int n) {
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) return false;
    }
    return true;
}

Points worth making:

  • An empty array and a single element array are both sorted. Handle them by construction: the loop starts at 1 and simply does not run.
  • < versus <= decides whether duplicates are allowed. a[i] < a[i-1] fails only on a strict decrease, so equal neighbours pass, which is non decreasing order. If you need strictly increasing, use a[i] <= a[i-1] as the failure test.
  • The recursive version exists but there is no reason to use it, since it is O(n) stack for an O(1) space problem.

Why it matters in firmware. A cheap precondition check at an API boundary. If a function requires a sorted lookup table, assert(is_sorted(table, n)) in a debug build catches a maintainer who adds an entry in the wrong place, and compiles away entirely in release.

Q55. How do you increase the size of a dynamic array?

Say this out loud Allocate a bigger block, copy the contents, free the old one. Grow by a multiplicative factor rather than a constant, typically 1.5 or 2 times, which makes appending amortized O(1). Always assign realloc’s result to a temporary, because if it fails it returns NULL and you would otherwise have overwritten your only pointer to the old block and leaked it.

The full explanation

typedef struct {
    int   *data;
    size_t len;      /* elements in use */
    size_t cap;      /* elements allocated */
} vec_t;

int vec_push(vec_t *v, int value) {
    if (v->len == v->cap) {
        size_t newcap = (v->cap == 0) ? 4 : v->cap * 2;
        int *tmp = realloc(v->data, newcap * sizeof(int));   /* temporary, always */
        if (tmp == NULL) return -1;                          /* old block still valid */
        v->data = tmp;
        v->cap  = newcap;
    }
    v->data[v->len++] = value;
    return 0;
}

Why doubling, with the arithmetic

Suppose you append n elements.

  • Grow by a constant, say 1 each time. You reallocate and copy on every single append. Copies total 1 + 2 + 3 + ... + n which is n(n+1)/2, so O(n squared) total work. Appending 10000 elements costs 50 million copies.
  • Grow by doubling. You reallocate at sizes 4, 8, 16, 32 and so on. Copies total 4 + 8 + 16 + ... + n which is less than 2n, so O(n) total work, meaning O(1) per append when averaged. Appending 10000 elements costs about 20000 copies.

That averaged cost is what “amortized O(1)” means. Individual appends are occasionally expensive, O(n), but the expensive ones are rare enough that the average is constant. Being able to explain amortized analysis with this exact example is a common interview requirement.

Why 1.5 rather than 2 in some libraries

With a growth factor of 2, the sum of all previously freed blocks is always smaller than the next requested block, so freed memory can never be reused for the next growth and the allocator must keep extending into fresh territory. With a factor below the golden ratio, roughly 1.618, the freed blocks eventually coalesce into something large enough to reuse. This is why Microsoft’s implementation of std::vector uses 1.5 while libstdc++ uses 2. It is a memory fragmentation argument, not a speed one, and it is a good detail to mention for an embedded role because fragmentation is the thing you actually fear.

The realloc trap

p = realloc(p, newsize);      /* WRONG: if it fails, p becomes NULL and the old block leaks */

Also remember that realloc may move the block. Any other pointer or index into the old buffer is invalid afterwards. This is the same rule as std::vector iterator invalidation.

Why it matters in firmware

The honest answer is that you usually do not do this. The firmware pattern is a fixed capacity array with a length counter, sized at build time for the worst case, and an explicit error return when full:

typedef struct {
    int    data[MAX_ITEMS];
    size_t len;
} fixed_vec_t;

int fv_push(fixed_vec_t *v, int value) {
    if (v->len >= MAX_ITEMS) return -ENOSPC;   /* fail predictably, never grow */
    v->data[v->len++] = value;
    return 0;
}

This cannot fragment, cannot fail unpredictably, and its worst case memory is visible in the linker map. Explaining the doubling strategy and then saying you would not use it here is the complete answer.

Section 4: Strings

Q56. How do you reverse a string in place safely?

Say this out loud Same two pointer swap as an array, but stop before the terminator, and never do it on a string literal because literals live in read only memory.

void str_reverse(char *s) {
    size_t n = strlen(s);
    size_t i = 0, j = (n == 0) ? 0 : n - 1;
    while (i < j) {
        char t = s[i]; s[i++] = s[j]; s[j--] = t;
    }
}

The literal trap, which is asked deliberately

char *s = "hello";     /* pointer to a string literal in .rodata, in FLASH */
str_reverse(s);        /* attempts to write to flash: bus fault or silently ignored */

char s2[] = "hello";   /* an ARRAY, initialized by copying the literal into RAM */
str_reverse(s2);       /* fine */

The difference between those two declarations catches a surprising number of experienced candidates. char *s = "hello" gives you 4 bytes of pointer in RAM pointing at 6 bytes in flash. char s2[] = "hello" gives you 6 bytes in RAM, plus 6 bytes in flash holding the initial values, plus a copy at startup. Compile with -Wwrite-strings and the first form becomes a warning.

The n == 0 guard matters because n - 1 on a size_t of value 0 wraps around to a huge number rather than going negative.

Q57. How do you reverse the words in a sentence in O(1) space?

Say this out loud Reverse the entire string, then reverse each word individually. O(n) time, O(1) space.

Worked example

input:            "the quick brown fox"
reverse all:      "xof nworb kciuq eht"
reverse each word:"fox brown quick the"
static void rev_range(char *s, size_t i, size_t j) {
    while (i < j) { char t = s[i]; s[i++] = s[j]; s[j--] = t; }
}

void reverse_words(char *s) {
    size_t n = strlen(s);
    if (n == 0) return;
    rev_range(s, 0, n - 1);                 /* pass 1: reverse everything */

    size_t start = 0;
    for (size_t i = 0; i <= n; i++) {       /* pass 2: reverse each word */
        if (i == n || s[i] == ' ') {
            if (i > start) rev_range(s, start, i - 1);
            start = i + 1;
        }
    }
}

The i <= n bound is deliberate. It lets the final word be handled by the same code path as every other word, using the terminator position as a virtual separator, instead of needing a special case after the loop.

The follow up. How do you also collapse multiple spaces? Add the read and write index compaction from Q64 as a third pass, or merge it into pass 2.

Q58. Palindrome check?

Say this out loud Two pointers walking inward. Before writing anything, ask whether case, punctuation, and spaces count, because that changes the loop.

The simple version

bool is_palindrome(const char *s) {
    size_t n = strlen(s);
    if (n == 0) return true;
    size_t i = 0, j = n - 1;
    while (i < j) {
        if (s[i++] != s[j--]) return false;
    }
    return true;
}

The version they usually want, ignoring case and non alphanumerics

bool is_palindrome_relaxed(const char *s) {
    size_t i = 0, j = strlen(s);
    if (j == 0) return true;
    j--;
    while (i < j) {
        while (i < j && !isalnum((unsigned char)s[i])) i++;
        while (i < j && !isalnum((unsigned char)s[j])) j--;
        if (tolower((unsigned char)s[i]) != tolower((unsigned char)s[j])) return false;
        i++; j--;
    }
    return true;
}

"A man, a plan, a canal: Panama" passes.

The (unsigned char) cast on every ctype function argument is a real requirement, not pedantry. isalnum and friends are defined for values representable as unsigned char plus EOF. On ARM, plain char is unsigned by default so it happens to work, but on x86 it is signed, and passing a negative value is undefined behaviour that historically caused out of bounds table reads. Mentioning this signals real C experience.

The related question: asking whether the two inner while loops can run past each other. They cannot, because both are bounded by i < j.

Q59. String comparison?

Say this out loud Compare byte by byte until either a mismatch or a terminator. Return the sign of the difference between the first differing bytes, so the result gives ordering rather than just equality. The comparison must be done on unsigned char.

Full implementation and discussion in Q70.

The point to understand here is that strcmp returns an ordering, which is why it can drive a sort:

if (strcmp(a, b) == 0)  /* equal */
if (strcmp(a, b) <  0)  /* a comes before b */
if (strcmp(a, b) >  0)  /* a comes after b */

And the most common bug in all of C:

if (name == "reset")        /* WRONG: compares two pointers, almost always false */
if (strcmp(name, "reset") == 0)   /* right */

The first version compiles without warning. It compares the address of your buffer against the address of a literal in flash. It is false essentially always, and it is a bug that ships.

Q60. Anagram check?

Say this out loud Count character frequencies in one pass over each string and compare the counts. O(n) time with a fixed 256 entry table. Sorting both strings and comparing is O(n log n) and is the weaker answer.

bool is_anagram(const char *a, const char *b) {
    int count[256] = {0};

    const unsigned char *p = (const unsigned char *)a;
    while (*p) count[*p++]++;              /* increment for the first string */

    p = (const unsigned char *)b;
    while (*p) {
        if (--count[*p++] < 0) return false;   /* decrement, negative means b has extra */
    }

    for (int i = 0; i < 256; i++)
        if (count[i] != 0) return false;   /* leftover means a had extra */

    return true;
}

The single table trick. Notice there is only one count array, not two. Increment on the first string, decrement on the second. If the strings are anagrams every count returns to zero. The early exit on a negative count catches the case where b contains a character a never had, without waiting for the final scan.

Optimisation: compare lengths first. If they differ, they cannot be anagrams, and that is O(1) after two strlen calls.

Follow ups to expect * Case insensitive: lowercase each character on the way into the table. * Unicode: a 256 entry table no longer works, so you need a hash map keyed by code point, and you must decide whether canonically equivalent sequences count as equal, which is a genuinely hard problem. * Memory constrained: for lowercase ASCII only, use int count[26] which is 104 bytes, or int8_t count[26] at 26 bytes if strings are short.

Q61. Find duplicate characters?

Say this out loud A 256 entry count table, one pass. If you only need presence rather than counts, a 256 bit bitmap in 32 bytes.

/* print every character occurring more than once */
void print_duplicates(const char *s) {
    int count[256] = {0};
    for (const unsigned char *p = (const unsigned char *)s; *p; p++)
        count[*p]++;
    for (int i = 0; i < 256; i++)
        if (count[i] > 1) printf("%c appears %d times\n", i, count[i]);
}

The bitmap version, 32 bytes instead of 1024

bool has_duplicate(const char *s) {
    uint32_t seen[8] = {0};                 /* 8 words * 32 bits = 256 bits */
    for (const unsigned char *p = (const unsigned char *)s; *p; p++) {
        uint32_t w = *p >> 5, b = *p & 31u;
        if (seen[w] & (1u << b)) return true;
        seen[w] |= (1u << b);
    }
    return false;
}

For lowercase letters only this collapses further, to a single uint32_t where bit 0 is ‘a’ and bit 25 is ‘z’. That version uses 4 bytes and no loop over the table at the end, and it is a genuinely elegant answer to give:

bool has_dup_lower(const char *s) {
    uint32_t mask = 0;
    for (; *s; s++) {
        uint32_t bit = 1u << (*s - 'a');
        if (mask & bit) return true;
        mask |= bit;
    }
    return false;
}

Q62. Count vowels?

int count_vowels(const char *s) {
    int n = 0;
    for (; *s; s++) {
        switch (tolower((unsigned char)*s)) {
            case 'a': case 'e': case 'i': case 'o': case 'u': n++; break;
            default: break;
        }
    }
    return n;
}

The table driven alternative, which is branchless and faster in a tight loop:

static const uint8_t is_vowel[256] = {
    ['a']=1, ['e']=1, ['i']=1, ['o']=1, ['u']=1,
    ['A']=1, ['E']=1, ['I']=1, ['O']=1, ['U']=1,
};

int count_vowels_tbl(const char *s) {
    int n = 0;
    for (const unsigned char *p = (const unsigned char *)s; *p; p++) n += is_vowel[*p];
    return n;
}

Two things worth pointing out about that table. It uses C99 designated initializers, so every unlisted entry is zero and it is const, meaning the whole 256 byte table sits in flash and costs no RAM. And n += is_vowel[*p] has no branch at all, which is the real speedup on a pipelined core.

The interviewer is not testing whether you can count vowels. They are looking for whether you handle case, whether you use unsigned char, and whether you know the branchless table trick.

Q63. Count words?

Say this out loud A two state machine. Track whether you are currently inside a word, and increment the counter on each transition from outside to inside. Counting spaces is wrong because it breaks on leading spaces, trailing spaces, and repeated spaces.

int count_words(const char *s) {
    int count = 0;
    bool in_word = false;

    for (; *s; s++) {
        if (isspace((unsigned char)*s)) {
            in_word = false;
        } else if (!in_word) {
            in_word = true;
            count++;                  /* only on the transition into a word */
        }
    }
    return count;
}

Why the naive approach fails

Input Count spaces + 1 State machine Correct
"hello world" 2 2 2
" hello world" 4 2 2
"hello world" 3 2 2
"hello world " 4 2 2
"" 1 0 0

The state machine is right in all five cases and the counting approach is right in one.

Why it matters in firmware

This is the smallest possible example of the pattern you use for every serial protocol parser: current state, an input character, a transition, and an action on the transition. Say that connection out loud. Parsing an AT command stream or a NMEA sentence arriving one byte at a time from a UART interrupt is the same structure with more states.

Q64. Remove spaces?

Say this out loud Two index compaction, done in place. A read index scans every character, a write index only advances when a character is kept. O(n) time, O(1) space, no second buffer.

void remove_spaces(char *s) {
    size_t r = 0, w = 0;
    while (s[r]) {
        if (!isspace((unsigned char)s[r])) {
            s[w++] = s[r];
        }
        r++;
    }
    s[w] = '\0';                   /* terminate at the new, shorter length */
}

Worked trace on "a b c"

r s[r] Keep w before Buffer state
0 ‘a’ yes 0 a b c
1 ’ ’ no 1 a b c
2 ‘b’ yes 1 ab b c becomes ab_c in progress
3 ’ ’ no 2
4 ‘c’ yes 2 abc c
end 3 write \0 at index 3, giving "abc"

The write index never overtakes the read index, which is why writing in place is always safe here. w is less than or equal to r at every step by construction.

Why this pattern matters

The same three lines solve an entire family of problems:

  • remove all occurrences of a character
  • remove duplicates from a sorted array
  • filter an array of structs by a predicate
  • collapse runs of repeated separators
  • strip control characters from a received serial buffer

Recognising a question as “this is the read and write index pattern” is far more useful than memorising each variant. In C++ this exact pattern is std::remove_if, which is why that function returns a new end iterator rather than shrinking the container.

Q65. String validation?

Say this out loud Define what valid means precisely, then write a single pass state machine. Validating a number, for example, needs states for optional sign, integer digits, optional decimal point and fraction, and optional exponent, and it must reject a string containing no digits at all.

Worked example, validating a decimal number

bool is_valid_number(const char *s) {
    bool seen_digit = false, seen_dot = false, seen_exp = false;

    if (*s == '+' || *s == '-') s++;              /* optional leading sign */

    while (*s) {
        if (isdigit((unsigned char)*s)) {
            seen_digit = true;
        } else if (*s == '.') {
            if (seen_dot || seen_exp) return false;   /* second dot, or dot after e */
            seen_dot = true;
        } else if (*s == 'e' || *s == 'E') {
            if (seen_exp || !seen_digit) return false; /* second e, or e with no mantissa */
            seen_exp = true;
            seen_digit = false;                        /* exponent needs its OWN digits */
            if (s[1] == '+' || s[1] == '-') s++;       /* optional exponent sign */
        } else {
            return false;                              /* any other character */
        }
        s++;
    }
    return seen_digit;                                 /* must end having seen a digit */
}

Test cases that separate a working implementation from a broken one:

Input Valid Why
"123" yes
"-1.5e-3" yes sign, dot, exponent with its own sign
"." no no digits at all
"1e" no exponent with no digits after it
"1.2.3" no second dot
"e5" no exponent with no mantissa
"+" no sign only
"" no empty

The seen_digit = false reset after the exponent is the line most candidates miss, and it is the one that makes "1e" fail correctly.

Why it matters in firmware

A validation function is your defence at the boundary between the outside world and your system. Every byte from a UART, a CAN bus, a radio, or a config file is untrusted. The general rule to state: validate at the boundary, once, and then let the internal code assume validity rather than re checking everywhere.

Q66. String tokenization?

Say this out loud strtok modifies the input buffer by writing terminators into it, and it keeps its position in a static variable, so it is neither reentrant nor thread safe and cannot be used on a string literal. Use strtok_r with a caller supplied save pointer, or write a non destructive tokenizer that returns offsets and lengths.

The full explanation

char input[] = "GET,/status,HTTP1.1";     /* must be a modifiable array */
char *tok = strtok(input, ",");
while (tok != NULL) {
    printf("[%s]\n", tok);
    tok = strtok(NULL, ",");              /* NULL means "continue where you left off" */
}

What strtok actually does to your buffer:

before:  G E T , / s t a t u s , H T T P 1 . 1 \0
after:   G E T \0 / s t a t u s \0 H T T P 1 . 1 \0

It replaces each delimiter with a terminator and returns a pointer into the original buffer. So it does no allocation, which is why it exists, but it destroys the input.

The three problems

  1. It modifies the input. So you cannot tokenize a const char*, and you cannot tokenize the same buffer twice.
  2. It uses a hidden static. So two tokenizations cannot be interleaved. If a function calls strtok and then calls another function that also uses strtok, the outer loop’s position is silently destroyed.
  3. It is not thread safe or ISR safe. Two tasks calling it concurrently corrupt each other’s state. Some libc implementations use thread local storage, which fixes threads but not interrupts and is not guaranteed.

The reentrant version

char *save = NULL;
char *tok = strtok_r(input, ",", &save);
while (tok) {
    process(tok);
    tok = strtok_r(NULL, ",", &save);
}

The state now lives in the caller’s variable, so nesting and threading both work.

The firmware version, non destructive

typedef struct { const char *p; size_t len; } token_t;

int tokenize(const char *s, char delim, token_t *out, int max) {
    int n = 0;
    while (*s && n < max) {
        while (*s == delim) s++;                 /* skip leading delimiters */
        if (!*s) break;
        out[n].p = s;
        while (*s && *s != delim) s++;
        out[n].len = (size_t)(s - out[n].p);
        n++;
    }
    return n;
}

This never writes to the input, so it works on a const buffer in flash, works on a DMA receive buffer that another layer still needs intact, and is fully reentrant. Offering this unprompted is a strong answer for an embedded role.

Q67. How do you implement strstr, and when is KMP worth it?

Say this out loud The naive version tries every starting position and compares forward, O(n times m). KMP achieves O(n plus m) by precomputing, for each prefix of the pattern, the length of the longest proper prefix that is also a suffix, which tells you how far you can safely skip after a mismatch instead of restarting.

The naive version

const char *my_strstr(const char *hay, const char *needle) {
    if (*needle == '\0') return hay;

    for (const char *h = hay; *h; h++) {
        const char *a = h, *b = needle;
        while (*a && *b && *a == *b) { a++; b++; }
        if (*b == '\0') return h;            /* consumed the whole needle: match */
    }
    return NULL;
}

Worst case is a pattern like "aaaab" in a haystack of "aaaaaaaaab", where every start position matches almost to the end before failing, giving O(n times m).

KMP, explained properly

The insight: when the naive algorithm fails partway through a match, it throws away everything it just learned and restarts one character later. But it already knows what those characters were, because they matched the pattern. That knowledge tells you how far you can jump.

The LPS array. For each position i in the pattern, lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of it. Proper means it cannot be the whole thing.

Building it for "ABABCABAB":

i Character Prefix ending here Longest prefix that is also a suffix lps[i]
0 A A none 0
1 B AB none 0
2 A ABA A 1
3 B ABAB AB 2
4 C ABABC none 0
5 A ABABCA A 1
6 B ABABCAB AB 2
7 A ABABCABA ABA 3
8 B ABABCABAB ABAB 4

Now suppose you matched 8 characters and then failed. lps[7] = 3 says the last 3 characters you matched are also the first 3 characters of the pattern. So instead of restarting, you keep those 3 as already matched and continue comparing from pattern position 3. The haystack index never moves backward, which is what gives O(n).

static void build_lps(const char *p, int m, int *lps) {
    int len = 0;
    lps[0] = 0;
    for (int i = 1; i < m; ) {
        if (p[i] == p[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];        /* fall back, do NOT advance i */
        } else {
            lps[i++] = 0;
        }
    }
}

int kmp_search(const char *text, const char *pat) {
    int n = (int)strlen(text), m = (int)strlen(pat);
    if (m == 0) return 0;
    int lps[m];                        /* in real firmware: a fixed max size buffer */
    build_lps(pat, m, lps);

    for (int i = 0, j = 0; i < n; ) {
        if (text[i] == pat[j]) {
            i++; j++;
            if (j == m) return i - m;  /* full match, return the start index */
        } else if (j != 0) {
            j = lps[j - 1];            /* skip ahead using what we already know */
        } else {
            i++;
        }
    }
    return -1;
}

When to use which

KMP costs O(m) extra memory for the LPS table plus the time to build it. For short patterns, which is nearly every real case, the naive version wins because the setup cost dominates and the naive loop is cache friendly and branch predictable. glibc’s strstr actually uses a hybrid: naive for short needles, and a two way algorithm for long ones.

For an embedded interview the right answer is: naive by default, and I would only reach for KMP if profiling showed the search was hot and the pattern was long, and I would need to bound the LPS table size at compile time because a VLA is not acceptable.

Q68. How do you implement strcpy from scratch?

char *my_strcpy(char *dst, const char *src) {
    char *d = dst;
    while ((*d++ = *src++) != '\0') { }
    return dst;                    /* return the original dst, for chaining */
}

Decoding the condensed loop, because interviewers ask you to explain it:

*d++ = *src++ does four things in one expression. Copy the character src points at into where d points, then increment both pointers. The whole assignment expression evaluates to the value that was assigned. So the loop condition tests the copied character, and stops after copying the terminator, meaning the terminator does get copied. That last point is the correctness detail.

Written out, it is exactly equivalent to:

char *my_strcpy_clear(char *dst, const char *src) {
    size_t i = 0;
    while (src[i] != '\0') { dst[i] = src[i]; i++; }
    dst[i] = '\0';                 /* the terminator, explicitly */
    return dst;
}

Say this immediately after writing it. This function has no bounds checking whatsoever. If the source is longer than the destination buffer, it writes past the end and corrupts whatever is next. It is one of the most exploited functions in the history of C.

The alternatives and their traps

strncpy(dst, src, n);

This does NOT simply add bounds checking. Two surprises: 1. If the source is n characters or longer, the destination is not null terminated. Every subsequent strlen or printf runs off the end. 2. If the source is shorter than n, strncpy pads the entire remainder of the destination with zeros. Copying a 3 character string into a 1024 byte buffer writes 1024 bytes, not 4.

It was designed in 1979 for fixed width filename fields in a filesystem, not for general string copying, and it is almost never what you want.

The safe options:

snprintf(dst, sizeof dst, "%s", src);          /* always terminates, portable */
strlcpy(dst, src, sizeof dst);                 /* always terminates, BSD and now POSIX */

Saying “I would write strcpy like this in an interview, but I would ship snprintf or strlcpy” is exactly the right answer, and it demonstrates security awareness without being asked.

Q69. How do you implement strlen from scratch?

size_t my_strlen(const char *s) {
    const char *p = s;
    while (*p) ++p;
    return (size_t)(p - s);
}

O(n), which is unavoidable because the length is not stored anywhere and must be discovered by scanning.

How the real one works, and why the answer is impressive

The library version processes a whole word at a time. The problem is detecting whether any byte within a 4 byte word is zero, without examining the bytes individually. The classic bit trick:

#define HAS_ZERO(w) (((w) - 0x01010101u) & ~(w) & 0x80808080u)

Why this works, byte by byte: * w - 0x01010101 subtracts 1 from each byte. A byte of 0x00 becomes 0xFF and sets its high bit. A byte of 0x01 becomes 0x00. * ~w has its high bit set only where the original byte had its high bit clear, which is true for all ASCII. * ANDing with 0x80808080 isolates just the high bit of each byte.

The result is non zero if and only if some byte was zero, with false positives eliminated by the ~w term. So the loop tests 4 bytes per iteration instead of 1.

The real implementation must also align the pointer first, by scanning byte by byte until the address is a multiple of 4, because otherwise the word load itself could fault or cross into an unmapped page. Alignment from the previous file, applied.

Mentioning this in an interview shows you have actually read a libc implementation rather than only used it.

Q70. How do you implement strcmp from scratch?

int my_strcmp(const char *a, const char *b) {
    while (*a && (*a == *b)) { ++a; ++b; }
    return (int)(unsigned char)*a - (int)(unsigned char)*b;
}

Tracing the loop exit. It exits either when *a is the terminator or when the two characters differ. In both cases, subtracting the current pair of characters gives the right answer: * If both are at their terminators, 0 - 0 is 0, meaning equal. * If a ended and b did not, 0 - something is negative, meaning a sorts first, which is correct since a prefix sorts before the longer string. * If they differ, the sign of the difference gives the ordering.

The unsigned char cast, which is the point of the question.

Plain char has implementation defined signedness. ARM GCC treats it as unsigned, x86 GCC treats it as signed. So comparing the byte 0x80: * as signed: it is -128, so it compares as less than ‘A’ which is 65 * as unsigned: it is 128, so it compares as greater than ‘A’

The C standard requires strcmp to compare as unsigned char, so the cast is not optional if you want the same behaviour everywhere. This is exactly the kind of portability detail that a senior firmware interview probes, because it is the difference between code that works on your dev board and code that works on the customer’s part.

Related: memcmp is the same idea but with an explicit length and no terminator, so it does not stop early on a zero byte. Never use memcmp to compare a secret such as a key or a password, because it returns as soon as it finds a difference, and the timing of that return leaks how many bytes matched. Use a constant time comparison that XORs every byte and accumulates.

Q71. Why do C strings end with ‘\0’?

Say this out loud Because a C string is only a pointer, with no length field anywhere, so the terminator is the only way any function can know where the data ends. It is a design tradeoff: it costs one byte per string and makes length O(n), but it means a string can be passed around as a single pointer with no accompanying structure.

The full explanation

Two ways to represent a string:

Null terminated (C) Length prefixed (Pascal, Rust, C++ std::string)
Representation pointer only pointer plus length
strlen O(n), must scan O(1), stored
Can contain a zero byte no yes
Substring without copying only a suffix any range
Overhead per string 1 byte 4 or 8 bytes
Passing cost 1 pointer 2 words or a struct
Bounds safety none inherent

Ken Thompson and Dennis Ritchie chose the terminator on a machine with 8 KB of memory, where one byte per string mattered and a pointer fitting in one register mattered more. It was a reasonable decision in 1972 and it is the source of an enormous share of security vulnerabilities since.

The consequences you should be able to list

  1. Every length query is a scan. for (i = 0; i < strlen(s); i++) is O(n squared), because strlen runs on every iteration. Hoist it out.
  2. You cannot store binary data. A zero byte in the middle truncates the string. Binary buffers need an explicit length, which is why every embedded API takes (const uint8_t *data, size_t len).
  3. One missing terminator turns every string function into an out of bounds read. strlen on an unterminated buffer walks until it happens to find a zero somewhere in unrelated memory.
  4. Every buffer needs one extra byte. char name[8] holds only 7 characters plus the terminator, and off by one here is the single most common C bug.

Why it matters in firmware

For anything from hardware, use explicit lengths, not terminators. A UART receive buffer, a CAN frame, a radio packet: all of these are byte arrays with a length, and treating them as C strings invites a scan off the end of the buffer if the terminator you expected never arrives. When you must convert a received buffer to a string, terminate it explicitly and check the length first:

if (len >= sizeof buf) return -EMSGSIZE;
memcpy(buf, rx, len);
buf[len] = '\0';                    /* now, and only now, it is a C string */

Q72. UTF-8 vs ASCII?

Say this out loud ASCII is 7 bit, one byte per character, 128 values. UTF-8 is a variable length encoding of Unicode using one to four bytes, designed so that all ASCII text is already valid UTF-8. Continuation bytes always begin with the bits 10, so you can find a character boundary from any position in the stream, and no ASCII byte value ever appears inside a multibyte sequence.

The encoding, laid out

Code point range Bytes Bit pattern
U+0000 to U+007F 1 0xxxxxxx
U+0080 to U+07FF 2 110xxxxx 10xxxxxx
U+0800 to U+FFFF 3 1110xxxx 10xxxxxx 10xxxxxx
U+10000 to U+10FFFF 4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

The leading byte tells you the length by how many high bits are set before the first zero. Every following byte starts with 10 and nothing else does.

Worked example, the euro sign U+20AC

code point:   0x20AC = 0010 0000 1010 1100    (16 bits, so 3 byte form)
template:     1110xxxx 10xxxxxx 10xxxxxx      (4 + 6 + 6 = 16 bits of payload)
fill:         1110 0010  10 000010  10 101100
bytes:        0xE2 0x82 0xAC

The self synchronising property, which is why the design is admired

Drop into the middle of a UTF-8 stream at a random byte. If it starts with 10 it is a continuation, so step backward until you find one that does not. At most 3 steps. You are now at a character boundary. No other variable length encoding of the era could do this, and it is the reason a corrupted byte in a transmission costs you one character rather than desynchronising everything that follows.

What still works and what breaks

Works unchanged on UTF-8: * strlen, but it returns the byte count, not the character count * strcmp, and it even gives correct code point ordering, which is a deliberate property of the encoding * strstr, because a valid UTF-8 sequence can never appear as a partial match inside another one * strcpy, memcpy, and anything byte oriented

Breaks: * indexing, since s[5] is the sixth byte, not the sixth character * truncation, since cutting at an arbitrary byte can split a character in half and produce invalid output * reversing, since reversing bytes destroys multibyte sequences * toupper and tolower, since case mapping outside ASCII is language dependent, and in Turkish the uppercase of i is not I * display width, since some characters occupy two columns and combining marks occupy zero

Why it matters in firmware

Device names, SSIDs, BLE advertising names, and file paths are UTF-8 in every modern system. If your display driver truncates a name at 16 bytes without checking for a boundary, you emit an invalid sequence and the display shows a replacement glyph or garbage. The correct truncation walks backward from the cut point until it finds a byte that is not a continuation:

size_t utf8_safe_truncate(const char *s, size_t max) {
    if (strlen(s) <= max) return strlen(s);
    size_t cut = max;
    while (cut > 0 && ((unsigned char)s[cut] & 0xC0) == 0x80) cut--;  /* back off continuations */
    return cut;
}

(b & 0xC0) == 0x80 is the test for a continuation byte, and it is worth memorising because it is the only bit manipulation you need for almost all practical UTF-8 handling.

Q73. Common string bugs in interviews and in production?

A checklist. Every one of these has shipped in real firmware.

1. Forgetting the terminator in the allocation.

char *copy = malloc(strlen(s));        /* one byte short, always */
strcpy(copy, s);                       /* writes one byte past the end */

Needs strlen(s) + 1.

2. sizeof on a parameter.

void f(char *buf) {
    memset(buf, 0, sizeof(buf));       /* 4 bytes, not the buffer size */
}

The array decayed to a pointer at the call. Pass the size explicitly.

3. strncpy leaving the buffer unterminated.

char dst[8];
strncpy(dst, "0123456789", sizeof dst);   /* 8 chars, no terminator */
printf("%s", dst);                        /* reads off the end */

4. strcat in a loop.

for (i = 0; i < n; i++) strcat(out, parts[i]);

Each strcat scans the whole existing string to find its end, so building an n character string costs O(n squared). Track the write position yourself, or use snprintf with an advancing offset.

5. Writing to a string literal.

char *s = "hello";
s[0] = 'H';                            /* undefined, flash write on an MCU */

6. memcpy on overlapping regions.

memcpy(buf + 1, buf, len);             /* undefined, use memmove */

7. Comparing with ==.

if (cmd == "reset")                    /* compares pointers, silently false */

8. Off by one on the buffer size.

char name[8];
strcpy(name, "12345678");              /* 8 chars plus terminator = 9 bytes into 8 */

9. Calling strlen inside the loop condition.

for (size_t i = 0; i < strlen(s); i++)  /* O(n squared) */

10. Passing a plain char to a ctype function.

if (isalpha(s[i]))                     /* undefined for negative values on signed char */
if (isalpha((unsigned char)s[i]))      /* correct */

11. Treating a received binary buffer as a string. No terminator will arrive, so strlen scans until it finds an unrelated zero byte somewhere in RAM.

12. sprintf with no bound. Use snprintf and check the return value, which is the length that would have been written, so a value greater than or equal to the buffer size means it was truncated.

Appendix: memcpy and memmove from scratch

These come up constantly and the overlap logic is the part people get wrong.

memcpy: no overlap allowed.

void *my_memcpy(void *dst, const void *src, size_t n) {
    unsigned char       *d = dst;
    const unsigned char *s = src;
    while (n--) *d++ = *s++;
    return dst;
}

The standard declares both pointers restrict, which is the promise from the previous file that they do not overlap. That promise is what lets a real implementation copy words at a time, in whatever order is fastest, or even backwards.

memmove: overlap handled.

void *my_memmove(void *dst, const void *src, size_t n) {
    unsigned char       *d = dst;
    const unsigned char *s = src;

    if (d == s || n == 0) return dst;

    if (d < s) {
        while (n--) *d++ = *s++;              /* forward is safe */
    } else {
        d += n; s += n;
        while (n--) *--d = *--s;              /* backward is required */
    }
    return dst;
}

Why the direction depends on which pointer is higher, drawn out

Case one, destination is below the source. memmove(buf, buf + 2, 5) on [A B C D E F G]:

copying forward:
  step 1: buf[0] = buf[2] = C   ->  [C B C D E F G]
  step 2: buf[1] = buf[3] = D   ->  [C D C D E F G]
  step 3: buf[2] = buf[4] = E   ->  [C D E D E F G]

Each source byte is read before the write that would have destroyed it. Forward is safe.

Case two, destination is above the source. memmove(buf + 2, buf, 5) on [A B C D E F G]:

copying forward would go wrong:
  step 1: buf[2] = buf[0] = A   ->  [A B A D E F G]
  step 2: buf[3] = buf[1] = B   ->  [A B A B E F G]
  step 3: buf[4] = buf[2] = A   ->  wrong, buf[2] was overwritten in step 1

Copying backward from the end reads each byte before anything overwrites it:

  step 1: buf[6] = buf[4] = E   ->  [A B C D E F E]
  step 2: buf[5] = buf[3] = D   ->  [A B C D E D E]
  step 3: buf[4] = buf[2] = C   ->  [A B C D C D E]
  ...

The rule in one sentence: if the destination is above the source and they overlap, copy backward, otherwise copy forward.

Roughly half of candidates get memcpy right and memmove wrong, which is exactly why it is a favourite screening question.

Quick revision sheet, questions 36 to 73

Concept The one sentence to remember
Array in memory Contiguous, base + i * size, no length stored, no bounds check
Array decay sizeof gives the pointer size the moment it is a parameter
Row major base + (i * n + j) * w, and iterate with the last index innermost for cache
Insert or delete in the middle O(n) for the shift, use memmove not a loop
Unordered delete Swap the last element into the hole, O(1)
Binary search midpoint lo + (hi - lo) / 2, never (lo + hi) / 2
lower_bound One loop that answers present, first occurrence, and insertion point
Rotate Reverse k, reverse the rest, reverse everything
Missing number XOR, because it cannot overflow
Duplicate detection Ask the value range first, then a bitmap if it is bounded
Merge family One walk, four emit rules: merge, union, intersection, difference
Dynamic growth Double it, which makes append amortized O(1)
Read and write index The in place filter pattern behind half of all string questions
Word counting A two state machine, never a space count
strcpy No bounds check, ship snprintf or strlcpy
strncpy May not terminate, and pads the whole buffer
strcmp Cast to unsigned char, because plain char signedness varies
strtok Destroys the input and uses a hidden static, use strtok_r
KMP LPS table tells you how far to skip, O(n + m), rarely worth it for short needles
'\0' The only reason any function knows where a string ends
UTF-8 Continuation bytes are 10xxxxxx, test with (b & 0xC0) == 0x80
memmove Destination above source and overlapping means copy backward

All seven parts of the guide

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 →

Share
Facebook Twitter Pinterest Linkedin

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

You May Also Like

Production firmware architecture diagram for an industrial IoT controller showing application, services, middleware, RTOS, HAL and driver layers
Embedded Firmware Architecture Embedded System

How to Design a Production-Grade Firmware Architecture

25 min read
Layered embedded firmware architecture diagram showing application, services, middleware, RTOS, HAL/BSP, drivers and hardware layers
Embedded Firmware Architecture Embedded System

Embedded Firmware Architecture Fundamentals: How Engineers Actually Decide

19 min read
Hashing and complexity analysis interview questions for embedded firmware engineers, questions 219 to 248
DSA Embedded System Interview

Embedded DSA Interview Questions: Hashing and Complexity (Q219–Q248)

49 min read
Firmware architecture interview questions cover: system architecture, RTOS vs bare-metal, OTA and rollback, secure boot
Embedded System Interview

Firmware Architecture Interview Questions: 100 Q&A for Senior and Staff Engineers

26 min read