# Implement nth Fibonacci number ## Problem Write a function that returns the **n-th Fibonacci number**. The Fibonacci sequence is defined as: - \(F(0)=0\) - \(F(1)=1\) - \(F(n)=F(n-1)+F(n-2)\) for \(n \ge 2\) ### Requirements - Input: integer `n` (assume `n >= 0`). - Output: integer `F(n)`. - Discuss time/space complexity and how you would handle large `n`. ### Follow-ups (if asked) - Avoid recursion stack overflow. - Optimize for time (e.g., better than \(O(n)\)) or for very large values. ### Constraints & Assumptions - Preserve the scope, facts, inputs, and requested outputs from the prompt above. - If the prompt leaves a detail unspecified, state a reasonable assumption before relying on it. - Keep the answer interview-ready: concise enough to present, but concrete enough to implement or evaluate. ### Clarifying Questions to Ask - Clarify input sizes, value ranges, mutability, return format, and tie-breaking. - State the target time and space complexity before coding. - Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes. ### What a Strong Answer Covers - A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it. - A correctness argument that explains why the algorithm covers all required cases. - Time and space complexity, plus at least one alternative approach when relevant. - Focused tests for normal cases, edge cases, and failure modes. ### Follow-up Questions - How would the approach change if the input were streaming or too large for memory? - What invariants would you assert in production code? - Which tests would catch off-by-one, duplicate, or tie-breaking bugs?