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

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

Hash table interview questions for embedded roles carry a twist the general version does not: average O(1) is worth very little when the requirement is a bounded worst case. Thirty questions on hashing and complexity analysis, closing out the 248 question bank.

---

Hash table interview questions for embedded roles

• Q219. What is a hash table and what do you trade away for O(1)?
• Q220. What makes a good hash function?
• Q221. What is a hash collision and why is it unavoidable?
• Q222. How does separate chaining resolve collisions?
• Q223. How does linear probing work and what is clustering?
• Q224. How does quadratic probing reduce clustering?
• Q225. How does double hashing work?
• Q226. What is load factor and what should you keep it below?
• Q227. Why is rehashing dangerous in firmware?
• Q228. What are the average and worst case costs of a hash table?
• Q229. When should you use a lookup table instead of a hash table?
• Q230. Why do hash tables behave badly in cache?
• Q231. What is perfect hashing and when can you use it?
• Q232. What is a Bloom filter and what does it guarantee?
• Q233. How do you build an LRU cache with O(1) operations?
• Q234. What does Big O actually mean?
• Q235. What does Big Omega mean?
• Q236. What does Big Theta mean?
• Q237. How do you work out the time complexity of a function?
• Q238. How do you work out space complexity?
• Q239. How is amortized complexity different from average case?
• Q240. How do you find the complexity of a recursive algorithm?
• Q241. What is best case complexity and why is it rarely useful?
• Q242. Why is worst case the only complexity that matters with a deadline?
• Q243. What does average case complexity assume?
• Q244. What are P, NP, and NP-complete?
• Q245. What are the recurring tradeoffs in system design?
• Q246. In what order should you optimize?
• Q247. How do you decide between memory and speed?
• Q248. How do you reason about complexity out loud in an interview?

---

Questions 219 to 248, explained fully. This completes the 248 question bank.

---

Section 13: Hashing

---

Q219. What is a hash table and what do you trade away for O(1)?

Say this out loud A structure that maps a key to an array index by computing a function of the key, giving O(1) average lookup, insert, and delete. The tradeoffs are that two keys can map to the same index, which is a collision that must be resolved, and that it provides no ordering, so range queries and sorted iteration are impossible.

The full explanation

The idea is to skip searching entirely. Instead of comparing your key against stored keys, you compute where it must be.

key "temperature"  ->  hash function  ->  0x4F2A18B3  ->  % 16  ->  index 3

#define TABLE_SIZE 16

typedef struct {
    const char *key;
    int         value;
    bool        occupied;
} entry_t;

static entry_t table[TABLE_SIZE];

Why it is O(1). Computing the hash depends only on the key length, not on how many items are stored. Indexing the array is one instruction. So the cost does not grow with n, which is a fundamentally different shape from a tree’s O(log n) or a list’s O(n).

The three properties you trade away

1. No ordering. You cannot iterate in sorted order, ask for the minimum, or perform a range query without scanning everything.
2. Worst case is O(n). If every key collides, the structure degenerates into a list.
3. Memory is over-provisioned by design. You need more slots than items, typically 1.3 to 2 times, or performance collapses.

When to use which structure, which is the question this usually leads to:

That last row matters for firmware. A hash table’s average O(1) is excellent, but its worst case is O(n), so it is a poor fit anywhere a hard deadline applies.

---

Q220. What makes a good hash function?

Say this out loud A function mapping an arbitrary key to an integer in the table’s index range. A good one distributes keys uniformly, is fast to compute, and is deterministic. For strings, FNV-1a and djb2 are the standard simple choices. For firmware, the CRC peripheral on the chip is often the fastest good hash available.

The three requirements

1. Deterministic. The same key always gives the same value. This rules out anything involving a pointer address or a timestamp.
2. Uniform. Keys should spread evenly across the range. Clustering causes collisions, which destroys the O(1).
3. Fast. The hash is computed on every operation, so a slow hash negates the benefit of avoiding a search.

Note that cryptographic strength is not required for a hash table, and cryptographic hashes such as SHA-256 are far too slow for one.

FNV-1a, the one to memorise

uint32_t fnv1a(const char *s) {
    uint32_t h = 2166136261u;                 /* FNV offset basis */
    while (*s) {
        h ^= (uint8_t)*s++;                   /* XOR first */
        h *= 16777619u;                       /* then multiply by the FNV prime */
    }
    return h;
}

Five lines, excellent distribution, and one multiply per byte. The XOR-then-multiply order is what makes it FNV-1a rather than FNV-1, and 1a has measurably better avalanche behaviour.

djb2, equally common

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

(h << 5) + h is h * 33, written as a shift and an add because 33 is not a power of two and old compilers did not strength-reduce it. Modern compilers do, so write whichever is clearer.

For integer keys

uint32_t hash_int(uint32_t x) {                  /* the Murmur3 finalizer */
    x ^= x >> 16;
    x *= 0x85ebca6bu;
    x ^= x >> 13;
    x *= 0xc2b2ae35u;
    x ^= x >> 16;
    return x;
}

Using the integer directly as an index is a common mistake. If your keys are addresses, they are all multiples of 4 or 8, so the low bits are always zero and you use only a quarter of the table. The mixing above spreads the entropy across all 32 bits.

Mapping to the table index

index = h & (TABLE_SIZE - 1);      /* power of two size: one AND instruction */
index = h % TABLE_SIZE;            /* prime size: a division */

Power of two with a mask is faster, especially on Cortex M0 which has no hardware divider, but it uses only the low bits of the hash, so the hash must have good low-bit entropy. A prime modulus is more forgiving of a weak hash. With FNV-1a or the Murmur finalizer, a power of two is fine.

The firmware trick worth volunteering: many MCUs have a hardware CRC32 peripheral. Feeding your key through it gives a well distributed 32 bit value at roughly one cycle per word with zero code size. CRC is not a cryptographic hash, but for table indexing it is excellent and it is free.

---

Q221. What is a hash collision and why is it unavoidable?

Say this out loud Two distinct keys hashing to the same index. Collisions are unavoidable, because the key space is far larger than the table, so every hash table design is really a collision resolution design.

Why unavoidable. The pigeonhole principle. If you have a 16 slot table and 17 possible keys, at least two must share a slot. In practice the key space is effectively infinite while the table is small, so collisions are certain.

The birthday paradox is the number that surprises people. With a table of 365 slots, you only need 23 randomly chosen keys before there is a better than even chance of a collision. Generally, collisions become likely at around the square root of the table size. So a 1024 slot table sees its first collision at roughly 32 entries, not at 512. This is why “my table is big so collisions are rare” is wrong reasoning.

The two families of resolution

Q222 through Q225 cover them.

---

Q222. How does separate chaining resolve collisions?

Say this out loud Each table slot holds the head of a linked list of all entries that hashed there. Insert prepends to the list, and lookup hashes then walks the short list. It is simple, tolerates a load factor above 1, and deletion is trivial, at the cost of a pointer per entry and poor cache behaviour.

typedef struct hnode {
    char         *key;
    int           value;
    struct hnode *next;
} hnode_t;

static hnode_t *table[TABLE_SIZE];

int *ht_find(const char *key) {
    uint32_t i = fnv1a(key) & (TABLE_SIZE - 1);
    for (hnode_t *n = table[i]; n != NULL; n = n->next) {
        if (strcmp(n->key, key) == 0) return &n->value;
    }
    return NULL;
}

bool ht_insert(const char *key, int value) {
    uint32_t i = fnv1a(key) & (TABLE_SIZE - 1);
    for (hnode_t *n = table[i]; n; n = n->next) {
        if (strcmp(n->key, key) == 0) { n->value = value; return true; }  /* update */
    }
    hnode_t *n = pool_alloc();                  /* pool, not malloc, in firmware */
    if (!n) return false;
    n->key = key; n->value = value;
    n->next = table[i];                         /* prepend, O(1) */
    table[i] = n;
    return true;
}

table
  [0] -> NULL
  [1] -> ("temp", 25) -> ("mode", 3) -> NULL      two keys collided here
  [2] -> ("id", 7) -> NULL
  [3] -> NULL

The always-compare-the-key rule. Matching hashes does not mean matching keys. You must compare the actual key, which is why strcmp appears in the loop. Skipping it gives you silent wrong answers on collision, and it is a bug that passes every small test.

Firmware note. Every insert allocates. Use a fixed pool (Q121) so allocation is O(1), bounded, and cannot fragment. Better still, use open addressing and avoid allocation entirely.

---

Q223. How does linear probing work and what is clustering?

Say this out loud Open addressing where a collision is resolved by checking the next slot, then the next, wrapping around. All data lives in one array with no pointers, which is excellent for cache and for firmware, but it suffers from primary clustering and deletion requires tombstones.

typedef enum { EMPTY, OCCUPIED, DELETED } slot_state_t;

typedef struct {
    uint32_t     key;
    int          value;
    slot_state_t state;
} slot_t;

static slot_t table[TABLE_SIZE];

int *lp_find(uint32_t key) {
    uint32_t i = hash_int(key) & (TABLE_SIZE - 1);
    for (uint32_t n = 0; n < TABLE_SIZE; n++) {
        uint32_t j = (i + n) & (TABLE_SIZE - 1);
        if (table[j].state == EMPTY) return NULL;         /* a true gap ends the search */
        if (table[j].state == OCCUPIED && table[j].key == key) return &table[j].value;
        /* DELETED: keep going */
    }
    return NULL;
}

Trace. Table of 8, inserting keys that hash to 3, 3, 4, 3:

insert A (hash 3): slot 3 empty  -> [.,.,.,A,.,.,.,.]
insert B (hash 3): slot 3 taken, try 4, empty -> [.,.,.,A,B,.,.,.]
insert C (hash 4): slot 4 taken, try 5, empty -> [.,.,.,A,B,C,.,.]
insert D (hash 3): 3,4,5 taken, try 6         -> [.,.,.,A,B,C,D,.]

Notice C had no collision of its own, yet it was displaced because B had already taken its slot. That knock-on effect is primary clustering: occupied runs grow and merge, and every key hashing anywhere into a run must traverse the whole run. A cluster of length L makes the average probe count grow roughly as L/2.

The tombstone problem, which is the real content of this question

You cannot simply mark a deleted slot EMPTY. Doing so would break the search for any key that probed past it.

[.,.,.,A,B,C,.,.]        A, B, C where B and C probed past A
delete A, mark EMPTY:
[.,.,.,.,B,C,.,.]
now search for C: hash is 4... but if C hashed to 3 originally,
the search stops at the EMPTY slot 3 and reports not found, even though C is present.

So deletion writes a DELETED marker, a tombstone. Search treats it as “keep probing” and insert treats it as “you may reuse this slot”.

The cost of tombstones. They accumulate. A table with many insert-delete cycles fills with tombstones, and searches slow down even though the table holds few live entries. The fix is to count tombstones and rehash the table when they exceed a threshold. If your workload deletes frequently, chaining is often the better choice, and saying that is the mature answer.

Why linear probing is still the default in high performance code. Probing sequential slots means each probe usually hits the same cache line. On a modern CPU, examining 8 consecutive entries can cost less than following one pointer to another cache line. Clustering is a real cost, but cache locality often more than pays for it.

---

Q224. How does quadratic probing reduce clustering?

Say this out loud Instead of stepping by 1, step by increasing squares: i + 1, i + 4, i + 9, and so on. This spreads probes out so collided keys do not follow identical paths, eliminating primary clustering, though secondary clustering remains because keys with the same initial hash still share the whole probe sequence.

uint32_t j = (i + n * n) & (TABLE_SIZE - 1);      /* n = 0, 1, 2, 3, ... */

Comparison of the probe sequences from index 3

The quadratic sequence leaves the neighbourhood quickly, so a run of occupied slots does not force every later key through the whole run.

The critical caveat. Quadratic probing does not necessarily visit every slot. With a table size that is a power of two, (i + n*n) mod size only reaches half the table, so an insert can fail while slots remain free. Two standard fixes:

• Use (i + (n*n + n)/2) mod size with a power-of-two size, which is guaranteed to cover the whole table.
• Use a prime table size and keep the load factor below 0.5, which guarantees a free slot is found.

Being able to state that limitation is the point of the question, because it is the non-obvious failure mode.

Secondary clustering. Two keys with the same initial hash follow the identical probe sequence forever, so they still collide repeatedly. It is a milder problem than primary clustering, and double hashing removes it.

---

Q225. How does double hashing work?

Say this out loud Use a second hash function to determine the step size, so keys with the same initial index still follow different probe sequences. This eliminates both primary and secondary clustering, at the cost of computing a second hash and losing cache locality.

uint32_t j = (h1 + n * h2) & (TABLE_SIZE - 1);

The requirement on h2. It must never be zero, or the probe never moves and you loop forever. And it must be coprime with the table size, or the sequence only visits a fraction of the slots.

/* power of two table: force h2 odd, since odd is always coprime with 2^k */
uint32_t h2 = (hash2(key) | 1u);

/* prime table size R < TABLE_SIZE: this form is never zero */
uint32_t h2 = R - (hash2(key) % R);

Forcing the step odd is the standard trick for a power-of-two table and it is worth knowing, because odd numbers share no factor with a power of two, so the step sequence walks the entire table.

The three schemes side by side

The verdict to give. Double hashing has the best theoretical distribution, but linear probing usually wins in practice on real hardware because of cache behaviour. Choose linear probing unless measurement shows clustering is actually hurting you. That is a measurement-over-theory answer and it reads well.

---

Q226. What is load factor and what should you keep it below?

Say this out loud Load factor is the number of entries divided by the number of slots. It is the single number controlling hash table performance. For open addressing, keep it below about 0.7, because probe counts rise sharply beyond that. For chaining, values above 1 are workable since the average chain length is simply the load factor.

α = n / m        n = entries, m = slots

The probe count as a function of load factor, open addressing with linear probing

Successful search averages 0.5 * (1 + 1/(1-α)), unsuccessful averages 0.5 * (1 + 1/(1-α)²).

The unsuccessful search column is the alarming one. Going from 70 percent to 90 percent full multiplies the failed-lookup cost by eight. This is not a gentle degradation, it is a cliff, and it is why 0.7 is the standard threshold.

For chaining, the average chain length is exactly α, so the average search is 1 + α/2. At α of 2 that is only 2 probes. Chaining degrades linearly rather than falling off a cliff, which is its main advantage.

In practice

Firmware angle. With a fixed table you cannot grow, so you must size for the worst case load. If you expect at most 100 entries and want α below 0.7, allocate at least 143 slots, rounded up to 256 for the power-of-two masking. That over-provisioning is the memory price of O(1), and being able to compute it on the spot is a good concrete answer.

---

Q227. Why is rehashing dangerous in firmware?

Say this out loud When the load factor crosses the threshold, allocate a larger table, typically double, and reinsert every entry, because the index depends on the table size so the old positions are meaningless. It is O(n) but happens rarely enough that the amortized cost per insert stays O(1).

static bool rehash(hashtable_t *ht) {
    size_t old_cap = ht->cap;
    slot_t *old = ht->slots;

    ht->cap  = old_cap * 2;
    ht->slots = calloc(ht->cap, sizeof(slot_t));
    if (!ht->slots) { ht->slots = old; ht->cap = old_cap; return false; }
    ht->count = 0;

    for (size_t i = 0; i < old_cap; i++) {
        if (old[i].state == OCCUPIED) ht_insert(ht, old[i].key, old[i].value);
    }
    free(old);
    return true;
}

Why you cannot just copy. The index is hash & (cap - 1). Doubling the capacity adds a bit to the mask, so roughly half the entries move to a new position. Copying the array would leave every lookup searching in the wrong place.

The amortized argument. Inserting n items triggers rehashes at sizes 16, 32, 64, and so on. The total reinsertion work is 16 + 32 + 64 + ... + n, which is less than 2n. So n inserts cost O(n) total, meaning O(1) each on average. This is exactly the dynamic array doubling argument from Q55, and pointing out that it is the same argument is worth doing.

The problem for real time systems, and this is the firmware answer. One unlucky insert takes O(n) while every other takes O(1). If that insert happens inside a control loop with a 1 ms deadline and the table holds 10000 entries, you miss the deadline. Average O(1) is meaningless when the requirement is on the worst case.

The mitigations:

• Preallocate for the worst case and never rehash. This is the standard firmware answer.
• Incremental rehashing. Keep both tables and migrate a few entries per operation, which is what Redis does. Every operation stays bounded, at the cost of complexity and checking two tables during migration.
• Do not use a hash table where a hard deadline applies.

---

Q228. What are the average and worst case costs of a hash table?

The iteration row is a real trap. Iterating a hash table costs O(m), the number of slots, because you scan every slot including empty ones. A table with 1024 slots holding 10 entries costs 1024 steps to iterate. If your workload iterates frequently and looks up rarely, a hash table is the wrong structure.

Where the worst case comes from. All keys hashing to one slot degenerates to a linear scan. In an adversarial setting this is a real attack: an attacker who knows your hash function sends keys that all collide, turning your O(1) service into O(n) and denying service. This was a widely exploited vulnerability in web frameworks around 2011, and the fix is a randomised per-process hash seed, which is why Python’s string hashing is randomised by default.

The three-way comparison to state

---

Q229. When should you use a lookup table instead of a hash table?

Say this out loud On a constrained target, the best hash table is often no hash table. If the keys are known at build time, a sorted const array in flash with binary search, or a perfect hash generated offline, gives deterministic timing, zero RAM, and no collision handling code.

Option 1: direct index, when the key range is small

static const uint16_t sine_lut[256] = { /* generated offline */ };
uint16_t s = sine_lut[angle & 0xFF];        /* O(1), one instruction, no hashing */

If the key is already a small integer, the array is the hash table, with a perfect hash function of identity. Always check whether this applies before reaching for anything cleverer.

Option 2: sorted const table plus binary search

typedef struct { uint16_t cmd_id; void (*handler)(const uint8_t *, size_t); } cmd_t;

static const cmd_t commands[] = {         /* MUST stay sorted by cmd_id */
    { 0x0001, cmd_ping     },
    { 0x0010, cmd_read     },
    { 0x0020, cmd_write    },
    { 0x00FF, cmd_reset    },
};

const cmd_t *find_cmd(uint16_t id) {
    int lo = 0, hi = (int)(sizeof commands / sizeof commands[0]) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if      (commands[mid].cmd_id < id) lo = mid + 1;
        else if (commands[mid].cmd_id > id) hi = mid - 1;
        else return &commands[mid];
    }
    return NULL;
}

Zero RAM, entirely in flash, deterministic log2(n) comparisons, and immune to corruption by a wild pointer since flash is not writable. For 256 commands that is 8 comparisons, which is fast enough for any command dispatcher.

Add a build-time guard so a maintainer cannot break the sort order:

static_assert(commands[0].cmd_id < commands[1].cmd_id, "command table must be sorted");

Option 3: perfect hash, generated offline. Q231.

When a runtime hash table is genuinely right in firmware. Dynamic keys not known at build time: a table of connected BLE peers by address, a DNS cache, an ARP table, or a session map. Then use open addressing with a fixed statically allocated table, size it for the worst case, and never rehash.

---

Q230. Why do hash tables behave badly in cache?

Say this out loud A hash lookup is one random memory access by design, which is the worst possible pattern for a cache and for a prefetcher. Open addressing with linear probing is much friendlier than chaining because the probes are sequential and often land in the same cache line.

The mechanism

A hash function’s job is to destroy any relationship between the key and the index. That is exactly what defeats a prefetcher, which works by detecting patterns. So a hash lookup on a cached processor is typically one cache miss, roughly 100 to 300 cycles on an application processor, while the hash computation itself is perhaps 10 cycles. The memory access dominates completely.

Chaining versus open addressing on a cached core

With 16 byte entries and a 64 byte cache line, linear probing examines four entries per miss. Chaining pays a miss per collision. This is why modern high performance hash tables, including Google’s Swiss tables and Rust’s hashbrown, all use open addressing.

Storing hashes to avoid key comparison

typedef struct {
    uint32_t hash;       /* cached, so most mismatches are rejected by comparing ints */
    char    *key;
    int      value;
} entry_t;

Comparing the stored hash first means you only dereference and strcmp the key when the hashes match, which turns most probe steps into an integer compare with no extra cache miss.

The Cortex M caveat. On an M0, M3, or M4 there is no data cache and RAM is single cycle, so the entire cache argument disappears and only the instruction counts matter. On an M7 with its caches, or an A series part, it dominates. Knowing which world your part is in, and saying so, is the differentiating answer.

---

Q231. What is perfect hashing and when can you use it?

Say this out loud A hash function with no collisions at all for a known fixed key set. Because it is collision free, lookup is a single probe with a guaranteed O(1) worst case, not just average. It requires the keys to be known in advance, which makes it ideal for firmware command tables, keyword sets, and protocol identifiers.

Minimal perfect hashing additionally maps n keys onto exactly n slots with no gaps, so there is zero wasted memory.

How you actually get one: generate it offline. gperf is the standard tool and it ships with GCC.

$ cat commands.gperf
%{
#include <string.h>
%}
struct command { const char *name; int id; };
%%
ping,    1
reset,   2
status,  3
version, 4
%%

$ gperf -t commands.gperf > commands.c

The generated code is typically a small const lookup table plus a hash built from one or two character positions and the string length, and a single strcmp to confirm. Everything is const, so it lives in flash. Lookup is a handful of instructions with no probing loop and no worst case.

Why this is the right answer for embedded command dispatch

The limitation to state. The key set must be fixed at build time. Adding a command means regenerating. For a firmware command table, protocol opcode set, or AT command list, that is exactly the situation, so the limitation costs nothing.

Bringing up gperf unprompted is one of the higher value things you can do in an embedded interview, because it shows you solve the problem at build time rather than at runtime.

---

Q232. What is a Bloom filter and what does it guarantee?

Say this out loud A probabilistic set membership structure using a bit array and k independent hash functions. It answers “definitely not present” or “probably present”. False positives are possible, false negatives are not. It uses dramatically less memory than storing the keys, which is why it is used as a cheap pre-filter in front of an expensive lookup.

How it works

#define BLOOM_BITS 1024
static uint32_t bloom[BLOOM_BITS / 32];

void bloom_add(const char *key) {
    uint32_t h1 = fnv1a(key), h2 = djb2(key);
    for (int i = 0; i < K; i++) {
        uint32_t b = (h1 + i * h2) % BLOOM_BITS;      /* k hashes from two, cheaply */
        bloom[b >> 5] |= (1u << (b & 31));
    }
}

bool bloom_maybe_contains(const char *key) {
    uint32_t h1 = fnv1a(key), h2 = djb2(key);
    for (int i = 0; i < K; i++) {
        uint32_t b = (h1 + i * h2) % BLOOM_BITS;
        if (!(bloom[b >> 5] & (1u << (b & 31)))) return false;   /* DEFINITELY absent */
    }
    return true;                                                  /* probably present */
}

Why there are no false negatives. Adding a key sets specific bits and bits are never cleared. So if a key was added, all of its bits are set, and the query cannot fail. If any bit is clear, the key was definitely never added.

Why there are false positives. A key that was never added may find all its bits set, because other keys happened to set each of them.

The math worth quoting. With m bits, n inserted items, and k hash functions, the optimal k is (m/n) * ln 2, about 0.693 * m/n, and the false positive rate is about 0.6185^(m/n).

Ten bits per item gives under 1 percent false positives. Storing the actual 16 byte keys would cost 128 bits per item. That thirteenfold saving is the entire appeal.

No deletion. Clearing bits would break other keys that share them. If deletion is required, use a counting Bloom filter with a small counter per position instead of a bit, at 4 times the memory.

Firmware and systems uses

• A pre-filter in front of a slow flash or network lookup: if the Bloom filter says no, skip the expensive query entirely.
• Duplicate packet detection with bounded memory.
• Cache admission, deciding whether an item has been seen before and is worth caching.
• Databases such as Cassandra and LevelDB use them to avoid reading disk blocks that cannot contain the key.

The one line summary: it trades a small, tunable error rate for a large, guaranteed memory saving, and it is only usable where a false positive is merely expensive rather than incorrect.

---

Q233. How do you build an LRU cache with O(1) operations?

The LRU cache, which is the interview question this leads to

Say this out loud A hash map for O(1) lookup, plus a doubly linked list maintaining recency order. The map stores key to node pointer, the list keeps the most recently used at the head. Every access moves that node to the head. When capacity is exceeded, evict the tail. All operations are O(1).

typedef struct lru_node {
    int              key, value;
    struct lru_node *prev, *next;
} lru_node_t;

typedef struct {
    lru_node_t  *map[TABLE_SIZE];      /* hash of key -> node */
    lru_node_t   head, tail;           /* sentinels, so no NULL checks (Q97) */
    int          count, capacity;
} lru_t;

static void detach(lru_node_t *n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
}

static void push_front(lru_t *c, lru_node_t *n) {
    n->next = c->head.next;
    n->prev = &c->head;
    c->head.next->prev = n;
    c->head.next = n;
}

bool lru_get(lru_t *c, int key, int *out) {
    lru_node_t *n = map_find(c, key);
    if (!n) return false;
    detach(n);
    push_front(c, n);                  /* touched, so it becomes most recent */
    *out = n->value;
    return true;
}

void lru_put(lru_t *c, int key, int value) {
    lru_node_t *n = map_find(c, key);
    if (n) { n->value = value; detach(n); push_front(c, n); return; }

    if (c->count == c->capacity) {
        lru_node_t *victim = c->tail.prev;      /* least recently used */
        detach(victim);
        map_remove(c, victim->key);
        pool_free(victim);
        c->count--;
    }
    n = pool_alloc();
    n->key = key; n->value = value;
    push_front(c, n);
    map_insert(c, key, n);
    c->count++;
}

Why both structures are needed, which is the whole answer. The hash map gives O(1) key lookup but knows nothing about recency. The list maintains recency order but searching it is O(n). Combining them, the map finds the node instantly and the node’s prev and next pointers let you reposition it in O(1) without any search. Neither structure alone achieves O(1) for both operations.

The sentinel head and tail remove every empty, first, and last special case from detach and push_front, which is exactly the technique from Q97. In an interview, using sentinels here makes the code noticeably shorter and cleaner and interviewers notice.

Firmware relevance. Flash translation layer page caches, filesystem block caches, DNS caches, and BLE bonding tables all use exactly this. Use a fixed pool for the nodes so there is no allocation, and size the table for capacity divided by 0.7.

---

Section 14: Complexity

---

Q234. What does Big O actually mean?

Say this out loud Big O is an upper bound on growth rate. Saying an algorithm is O(f(n)) means that beyond some input size, its cost is at most a constant multiple of f(n). It describes how the cost scales, deliberately discarding constants and lower order terms.

The formal definition, worth being able to state:

f(n) = O(g(n)) if there exist positive constants c and n0 such that f(n) <= c * g(n) for all n >= n0.

The n0 is why constants and small inputs do not matter: the claim is only about large n.

Simplification rules

The growth table you should have memorised

The row that matters: at a million elements, O(log n) is 20 operations and O(n²) is a trillion. That is the difference between instant and never.

The common complexity classes

---

Q235. What does Big Omega mean?

Say this out loud Big Omega is a lower bound. f(n) = Ω(g(n)) means the cost is at least a constant multiple of g(n) for large n. Where Big O says “no worse than”, Omega says “no better than”.

Formally, there exist positive c and n0 such that f(n) >= c * g(n) for all n >= n0.

Where it is genuinely used

• Lower bounds on problems, not algorithms. Any comparison based sort is Ω(n log n) in the worst case. That is a statement about the problem: no comparison sort can ever beat it, so there is no point searching for one. The proof is the decision tree argument from Q213.
• Any algorithm that must examine its whole input is Ω(n). Finding the maximum of an unsorted array cannot be done in fewer than n minus 1 comparisons.

The common misuse. People say “insertion sort is Ω(n) because the best case is linear”. That conflates best case with lower bound. Best and worst case are about which input you get. Big O and Omega are about which bound you are stating. You can give a lower bound on the worst case, an upper bound on the best case, or any other combination. Keeping the two axes separate is the point of the question, and it is covered further in Q241 to Q243.

---

Q236. What does Big Theta mean?

Say this out loud Theta is a tight bound, meaning both O and Omega hold with the same function. f(n) = Θ(g(n)) says the growth rate is exactly g(n) up to constant factors.

Examples

Why everyone says O when they mean Θ. In casual use, “binary search is O(log n)” is understood as a tight statement. Technically, binary search is also O(n) and O(n²), since those are valid upper bounds. Nobody objects, but an interviewer asking specifically about Theta wants to see that you know the difference.

The one line summary: O is at most, Ω is at least, Θ is exactly. Use Θ when the upper and lower bounds match, and stick with O when they do not, as with quick sort.

---

Q237. How do you work out the time complexity of a function?

Say this out loud How the number of basic operations grows with input size. You count the operations that dominate, ignore constants, and identify the loop structure, because the loop structure is almost always the answer.

How to analyse code quickly

for (int i = 0; i < n; i++)          /* n iterations */
    for (int j = 0; j < n; j++)      /* n iterations each */
        sum += a[i][j];              /* O(1) work */
/* total: O(n²) */

for (int i = 1; i < n; i *= 2)       /* i doubles: log n iterations */
    do_work();
/* total: O(log n) */

for (int i = 0; i < n; i++)          /* n */
    for (int j = i; j < n; j++)      /* n-i, so the average is n/2 */
        do_work();
/* total: n + (n-1) + ... + 1 = n(n+1)/2 = O(n²) */

That last one catches people: the inner loop shrinks, but the sum is still quadratic. Halving the constant does not change the class.

while (n > 0) n /= 2;                /* O(log n) */
for (int i = 0; i < n; i++)          /* O(n) */
    for (int j = 1; j < n; j *= 2)   /* O(log n) each */
        do_work();
/* total: O(n log n) */

The rules

1. Sequential blocks add, and the larger wins.
2. Nested loops multiply.
3. A loop variable that is multiplied or divided gives log n iterations, not n.
4. A recursive call means a recurrence, so use the master theorem from Q87.
5. Drop constants and lower order terms only at the end.

What “basic operation” means. For a sort it is comparisons and swaps, for a search it is comparisons, for a matrix routine it is multiplies. Choose the operation that dominates and count that. In firmware, if the operation is a flash write costing milliseconds, count flash writes and ignore everything else, which is exactly the reasoning behind selection sort in Q200.

---

Q238. How do you work out space complexity?

Say this out loud How much memory the algorithm needs as a function of input size, usually counting only the auxiliary space beyond the input itself. For recursive algorithms the stack counts, and on an embedded target it is often the binding constraint rather than time.

What to count

Examples

The BFS versus DFS point is the one to volunteer. People assume BFS and DFS have similar costs. DFS needs O(h) space, which for a balanced tree is O(log n). BFS needs O(w), which for the widest level is about n/2. On a memory constrained target, that is the difference between 20 stack frames and 500 queue entries, and it is often what decides the choice.

Why space is often the binding constraint in firmware. A Cortex M4 part might have 128 KB of RAM and run at 168 MHz. An O(n²) time algorithm on 100 elements is 10000 operations, about 60 microseconds, which is fine. An O(n) space algorithm on 50000 elements needs 200 KB, which simply does not exist. Time you can often afford, memory you cannot conjure.

---

Q239. How is amortized complexity different from average case?

Say this out loud The average cost per operation over a sequence of operations, where an occasional expensive operation is paid for by many cheap ones. It is not the same as average case: amortized is a guarantee over any sequence, while average case depends on a probability distribution over inputs.

The canonical example, dynamic array append

Doubling on overflow means most appends are O(1) and the rare resize is O(n).

appends 1 to 4:    cheap                    capacity 4
append 5:          copy 4, capacity 8       expensive
appends 6 to 8:    cheap
append 9:          copy 8, capacity 16      expensive

Total copying for n appends: 4 + 8 + 16 + ... + n, which is less than 2n. So n appends cost O(n) in total, giving O(1) amortized per append.

The accounting method, which is the intuitive explanation. Charge 3 units for every append. One unit pays for the actual write. The other two are saved in the element’s “account”. When a resize happens, every element in the second half of the array has 2 saved units, which is exactly enough to pay for copying itself and one element from the first half. The savings always cover the cost, so the average charge of 3 units is O(1).

Where else it appears

The firmware caveat, which is the important half of this answer. Amortized O(1) does not mean bounded. One particular append takes O(n). If that append lands inside a 1 ms control loop with 10000 elements, you miss the deadline. Real time systems care about the worst case single operation, not the average over a sequence.

That is why firmware preallocates. A fixed size array with an error return has a genuinely constant worst case, and that is worth more than an amortized guarantee. Saying this connects the theory back to the design decisions in Q55 and Q227, and it is the point interviewers are probing for on an embedded role.

---

Q240. How do you find the complexity of a recursive algorithm?

Say this out loud Write the recurrence relating the cost at size n to the cost at smaller sizes, then solve it by substitution, by drawing the recursion tree, or with the master theorem when the form fits.

The master theorem, for T(n) = a * T(n/b) + f(n), comparing f(n) with n^(log_b a):

Applied

The master theorem only applies when the subproblem is a constant fraction of the input. Recurrences with n-1 need substitution, which is why Hanoi and worst case quick sort are handled separately.

The recursion tree method is faster under pressure. For merge sort: level 0 does n work, level 1 does n/2 in each of 2 nodes so n total, level 2 does n again. Every level does n, and there are log n levels, so n log n. Reproducing that reasoning is more reliable than recalling which master case applies.

Do not forget the space. Depth times frame size, from Q88. Naive Fibonacci makes exponentially many calls but has only O(n) stack depth, because branches execute one at a time.

---

Q241. What is best case complexity and why is it rarely useful?

Say this out loud The complexity on the most favourable input. It is generally the least useful of the three, because you cannot design around getting lucky. The exception is when the favourable input is what you actually expect, which happens more often than people assume.

When it matters in practice. Sensor readings, timestamps, and log entries are usually nearly sorted, so insertion sort’s best case is close to the real case. Choosing an adaptive algorithm because you know your data’s shape is a legitimate engineering decision, and saying “I would pick insertion sort because my input is nearly sorted” is a much better answer than reciting worst case tables.

---

Q242. Why is worst case the only complexity that matters with a deadline?

Say this out loud The complexity on the least favourable input. This is the number that matters for any system with a deadline, and it is the default meaning when someone states a complexity without qualification.

Why it is the default for firmware. Certification standards and real time analysis are stated in terms of worst case execution time, WCET. An algorithm that is fast on average and occasionally slow is unusable if the occasional case can miss a deadline. That is the reasoning behind choosing heap sort over quick sort in Q214, and behind preallocating rather than rehashing in Q227.

Worst case is also a security property. Sorted input to a naive quick sort, or colliding keys to a hash table, are inputs an attacker can supply deliberately. Any service that processes untrusted input must be analysed on the worst case, not the average.

---

Q243. What does average case complexity assume?

Say this out loud The expected complexity over some probability distribution of inputs. The distribution is doing a lot of work in that sentence, and it is usually an assumption of uniform randomness that real data does not satisfy.

Why the assumption usually fails. Real data is not uniformly random. Log entries arrive sorted. IDs increment. String keys cluster by prefix. So the average case computed under uniformity can be optimistic for real workloads, which is exactly the BST degeneration problem in Q183.

Average case versus amortized, the distinction they may ask for

A dynamic array’s amortized O(1) holds for every sequence of n appends, with no probability involved. Quick sort’s average O(n log n) can be violated by an adversary who picks the input. That difference is real and it is a favourite follow up.

---

Q244. What are P, NP, and NP-complete?

Say this out loud P is the set of problems solvable in polynomial time. NP is the set whose solutions can be verified in polynomial time. NP-complete problems are the hardest in NP, in the sense that a polynomial algorithm for any one of them would give one for all of them. Whether P equals NP is unresolved, and the working assumption is that it does not.

The key intuition. Verifying is easier than finding. Given a proposed route through 50 cities, checking whether it is under a given length is trivial. Finding the shortest is not. NP is the class where that gap exists.

Well known NP-complete problems

Why it matters in engineering rather than theory. Recognising that a problem is NP-complete tells you to stop looking for an exact efficient algorithm and switch strategy:

• Approximation. Accept a solution within a provable factor of optimal. First-fit-decreasing bin packing is within 11/9 of optimal and runs in O(n log n).
• Heuristics. Greedy, simulated annealing, or genetic algorithms with no guarantee but good practical results.
• Exact but exponential on small inputs. If n is 20, 2^20 is a million and brute force is fine.
• Constrain the problem. Many NP-complete problems become polynomial on restricted inputs, such as trees instead of general graphs.

Where it appears in embedded work. Task placement on multiple cores, memory layout and bin packing, PCB routing, register allocation in compilers, which is graph colouring, and optimal scheduling. In each case the production solution is a heuristic, and knowing why is the useful part.

---

Q245. What are the recurring tradeoffs in system design?

The recurring axes in system design, with the firmware position on each.

The sentence that generalises them. There is no best algorithm, only the best algorithm for a stated set of constraints, so the first thing to do is establish the constraints. In an interview, asking about input size, memory budget, and whether a deadline exists before proposing an algorithm is what a senior engineer does, and it is often the thing actually being assessed.

---

Q246. In what order should you optimize?

Say this out loud Measure first, then improve the algorithm, then the data layout, then the code, in that order. An algorithmic improvement changes the growth rate and typically wins by orders of magnitude, while micro-optimisation adjusts the constant factor.

The order of leverage

Measure first, always. Intuition about where time goes is wrong most of the time. On a target the tools are a cycle counter such as DWT CYCCNT on Cortex M, a GPIO toggled around the region of interest and watched on a scope, or SWO trace with a profiler. Optimising an unmeasured hotspot is how a week disappears with nothing to show.

/* the cheapest reliable timing on Cortex M3 and above */
CoreDebug->DEMCR |= CoreDebug_DEMCR_TRCENA_Msk;
DWT->CYCCNT = 0;
DWT->CTRL  |= DWT_CTRL_CYCCNTENA_Msk;

uint32_t start = DWT->CYCCNT;
function_under_test();
uint32_t cycles = DWT->CYCCNT - start;

Embedded specific optimisations worth naming

• Replace division and modulo with shifts and masks, since Cortex M0 and M0+ have no divider.
• Use fixed point instead of floating point on parts without an FPU, where a soft float multiply can be a hundred cycles.
• Move constant tables to flash with const, freeing RAM and removing the startup copy.
• Compute at build time with constexpr or a code generator, so it costs zero cycles.
• Order struct members widest to narrowest to remove padding (Q5).
• Use __attribute__((section(".ramfunc"))) to place a hot function in RAM when executing from slow external flash.
• Choose -Os over -O2 when flash is the constraint, and measure both, since -Os is sometimes faster too because of better instruction cache behaviour.

The rule to state. Optimise the algorithm before the code, measure before and after every change, and stop when the requirement is met rather than when the code stops being improvable.

---

Q247. How do you decide between memory and speed?

Say this out loud The classic trade: precompute and store, or compute on demand. On a microcontroller the answer is usually to precompute into flash, because flash is plentiful and cycles are scarce, and because the table is deterministic while a computation may not be.

Worked example, a sine table

/* option A: compute at runtime */
float s = sinf(angle);              /* 100+ cycles with soft float, and pulls in libm */

/* option B: precomputed table in flash */
static const int16_t sine_lut[256] = { 0, 804, 1608, ... };
int16_t s = sine_lut[angle & 0xFF];  /* 2 cycles, 512 bytes of flash, 0 bytes of RAM */

512 bytes of flash buys a fiftyfold speedup and removes the floating point library entirely. On a part with 256 KB of flash that is a trivially good trade, and it is exactly how every DDS, motor control, and audio synthesis routine works.

The general pattern

When the trade runs the other way. If flash is the binding constraint, which happens on small parts, compute instead of storing. A CRC computed bit by bit needs no table at all, at roughly eight times the cycles. A nibble-wise CRC uses a 16 entry table, giving a middle point. Being able to name all three points on that curve is a good concrete answer.

Do not forget the third resource. Flash, RAM, and cycles are three separate budgets. A const table costs flash and no RAM. A computed value costs cycles and no memory. A cached value costs RAM. Knowing which of the three is scarce on your specific part is the actual engineering question, and stating that is the strongest way to answer this.

---

Q248. How do you reason about complexity out loud in an interview?

Worked examples of the reasoning you will be asked to perform out loud.

Example 1

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        work();

O(n·m). If m is a constant, that is O(n). Do not write O(n²) unless m actually equals n, since collapsing two distinct variables is a common error.

Example 2

for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++)
        work();

(n-1) + (n-2) + ... + 1 = n(n-1)/2, so O(n²). The shrinking inner loop halves the constant and does not change the class.

Example 3

for (int i = 1; i <= n; i *= 2)
    for (int j = 0; j < i; j++)
        work();

The inner loop runs 1, 2, 4, 8, up to n times. The sum is 1 + 2 + 4 + ... + n = 2n - 1, so O(n), not O(n log n). This one catches most candidates, because the log n outer loop suggests a log factor that the geometric sum absorbs.

Example 4

void f(int n) {
    if (n <= 1) return;
    f(n / 2);
    f(n / 2);
    for (int i = 0; i < n; i++) work();
}

T(n) = 2T(n/2) + O(n), which is merge sort’s recurrence, so O(n log n).

Example 5

for (int i = 0; i < n; i++)
    binary_search(a, n, key);

O(n log n). Recognising a known routine’s complexity and multiplying is the intended shortcut.

Example 6

while (n > 1) n = n / 2;         /* O(log n) */
while (n > 1) n = n - 1;         /* O(n) */
while (n > 1) n = sqrt(n);       /* O(log log n) */

The third one is worth knowing. Each step halves the number of bits, so it terminates in about log log n steps, which for a 32 bit value is 5.

Example 7, the one they ask for verbally “You have a million sorted records in flash and need to look up by ID. What is the complexity, and would you use a hash table?”

The answer they want: binary search over the sorted const array is O(log n), so 20 comparisons, entirely in flash with zero RAM and a deterministic bound. A hash table would give O(1) average but needs RAM for the table, has an O(n) worst case, and buys you 20 comparisons of saving that a flash read time dominates anyway. So binary search, and the reasoning is that the constant factor and the memory budget matter more than the asymptotic class at this size.

Example 8, where Big O misleads “Which is faster, an O(n) linear scan of 50 elements or an O(log n) binary search of 50 elements?”

Often the linear scan. Fifty sequential comparisons are branch predictable and cache friendly, while binary search jumps around and mispredicts nearly every branch. The asymptotic ordering only asserts something about large n, and 50 is not large. Saying “I would measure, and I would expect the linear scan to win at this size” is the answer.

The four things to say in any complexity discussion

1. State which case you mean, best, average, or worst.
2. State both time and space, since space often decides it on a target.
3. Name the constant factor when it matters, particularly cache behaviour.
4. Note where the asymptotic answer and the practical answer diverge, which is essentially always at small n.

---

Quick revision sheet, questions 219 to 248

---

Index of parts

All 248 questions are now answered at full depth, across seven parts.

The five themes running through all of it are listed at the top of this document, under How to use this guide.

---

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
• 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 (you are here)

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 →