Skip to question
asic.fyi

Hardware interview practice

Return a checked 32-bit Fibonacci number

EasyFirmwareC

Firmware needs the zero-based Fibonacci value F(n) in unsigned 32-bit arithmetic. Write the bounded iterative function.

Starting point

Question code

bool fib_u32(uint8_t n, uint32_t *out);
Reviewed example

Work through one case

Input
Case 1: fib_u32(0,&out)
Case 2: fib_u32(10,&out)
Case 3: With out initially 123, fib_u32(48,&out)
Expected output
Case 1: Returns true and stores 0.
Case 2: Returns true and stores 55.
Case 3: Returns false and leaves out=123.

The shown result follows by applying this rule: Handle n=0 directly or initialize two accumulators to 0 and 1 and iterate to n. The cases also demonstrate this requirement: Return true and store the exact value for every valid n; F(47)=2971215073 is the largest Fibonacci value that fits uint32_t.

What to cover

Requirements

  1. Require out to be nonnull and n to be in 0..47; otherwise return false and do not write through out.
  2. Define F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2).
  3. Use an iterative O(n)-time, O(1)-space implementation without recursion or a lookup table.
  4. Return true and store the exact value for every valid n; F(47)=2971215073 is the largest Fibonacci value that fits uint32_t.