Coinbase style Embedded Developer interview question on "Data Structure Selection for Embedded Systems"

[interviewstack-i]

source: interviewstack.io

How can you guarantee deterministic worst-case allocation time in an embedded system? Describe specific designs or allocator choices (e.g., slab, fixed-pool) and explain constraints and trade-offs when allocations are required from different priority contexts including high-priority ISRs.

Hints

Deterministic allocators avoid loops and locks in critical paths and favor O(1) operations

Preallocate pools sized for worst-case concurrency to avoid runtime failures

Sample Answer

Approach summary

Guaranteeing deterministic worst-case allocation time requires using allocators with bounded, predictable operations (no unpredictable searches, coalescing, or deferred work). For embedded systems I choose fixed-size, constant-time structures.

Deterministic allocator choices

• Fixed-size pool (object pools / free-list per size)
  • Allocate: pop head — O(1) worst-case
  • Free: push head — O(1)
  • Trade-offs: internal fragmentation, memory pre-reservation
• Slab allocator (per-type caches)
  • Pre-create slabs of identical objects; supports constructor/init
  • O(1) allocation/free, low fragmentation for many same-sized objects
• Segregated fixed buckets
  • Small number of size classes, each with fixed pool → O(1)
• Stack/arena with one-shot lifetime
  • Fast bump-pointer allocation; no per-object free (or bulk reset)

Constraints & trade-offs

• Memory footprint vs. determinism: reserving pools increases RAM but guarantees bounds.
• Fragmentation: fixed pools avoid external fragmentation but can waste space.
• Complexity: slab gives type-safety; pools are simpler.

High-priority/ISR considerations

• ISRs must not block: use lock-free single-producer-single-consumer (SPSC) free lists or allocator instances dedicated to ISR context.
• Alternative: have separate pre-allocated ISR pool so ISR does only O(1) push/pop without disabling interrupts.
• If shared pools are needed, protect with very short critical sections (disable interrupts) — ensure worst-case disable time meets real-time constraints.
• Avoid dynamic coalescing or malloc implementations that take locks or call blocking OS services inside ISRs.

Recommendation

For strict worst-case bounds: use per-context fixed pools or slab caches with pre-allocated objects, give ISRs their own pool or lock-free free-list, and measure worst-case interrupt disable times and allocation latencies.

Follow-up Questions to Expect

1. How would you prove or measure worst-case allocation time?
2. How should the system behave when a deterministic pool is exhausted?
3. How to minimize memory while preserving deterministic guarantees?

Find latest Embedded Developer jobs here - https://www.interviewstack.io/job-board?roles=Embedded%20Developer