DescriptionQ088
Q088FWDesignQualcommASIC interview problem
Return a checked 32-bit Fibonacci number
TechniquesFWDesignFirmware
DifficultyEasy
TopicFirmware
LanguageC
Requirements4 checkpoints
01
Problem
Firmware needs the zero-based Fibonacci value F(n) in unsigned 32-bit arithmetic. Write the bounded iterative function.
Starting declarationC
bool fib_u32(uint8_t n, uint32_t *out);Example input and output
Use this case to check your interpretationInput
Case 1: fib_u32(0,&out)
Case 2: fib_u32(10,&out)
Case 3: With out initially 123, fib_u32(48,&out)Output
Case 1: Returns true and stores 0.
Case 2: Returns true and stores 55.
Case 3: Returns false and leaves out=123.Explanation
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.
02
Requirements (4)
- Require out to be nonnull and n to be in 0..47; otherwise return false and do not write through out.
- Define F(0)=0, F(1)=1, and F(n)=F(n-1)+F(n-2).
- Use an iterative O(n)-time, O(1)-space implementation without recursion or a lookup table.
- Return true and store the exact value for every valid n; F(47)=2971215073 is the largest Fibonacci value that fits uint32_t.