Allowed R6 · Within policy
{
"slug": "fast-fibonacci",
"title": "Fast Fibonacci",
"difficulty": "medium",
"tags": [
"coding",
"algorithms-theory",
"technical",
"intern"
],
"is_free": true,
"locked": false,
"frequency": 0.25,
"last_reported_at": "2024-01-02T22:12:54.540004Z",
"url": "https://www.mokabla.com/en/c/google/fast-fibonacci",
"agent": {
"page": "https://www.mokabla.com/agent/en/c/google/fast-fibonacci",
"question": "https://www.mokabla.com/agent/_call/get_question?company=google&question=fast-fibonacci"
},
"company": {
"slug": "google",
"name_en": "Google"
},
"body_md": "## What they ask\nThe second of the two internship interviews, this time with an engineer in a US office. It starts small and escalates:\n\n> Write a function that returns the n-th Fibonacci number.\n\nThen: make it faster. Then: faster than linear. The expected end point is `O(log n)` using matrix exponentiation or the equivalent fast-doubling identities, and a short discussion of what happens when the numbers get big (modular arithmetic or arbitrary precision).\n\n### Examples\n- `n = 10` returns `55`.\n- `n = 90` returns `2880067194370816120`, which already needs 64-bit integers.\n- With modulus `10^9 + 7`, `n = 10^18` must still answer instantly.\n\n### Constraints\n- `0 <= n <= 10^18` in the final version, with a modulus.\n- Define `F(0) = 0`, `F(1) = 1`.\n\n## What they look for\n- Progression you drive yourself: naive recursion, then memoisation or iteration, then the logarithmic method, each with its complexity.\n- Knowing why `[[1,1],[1,0]]^n` gives Fibonacci numbers, and writing a clean binary exponentiation loop.\n- Overflow awareness: in Python it is free, in JavaScript you need `BigInt` or a modulus.\n- Tests: `n = 0`, `n = 1`, `n = 2`, a large `n` against a known value.\n\nThis is a question where the interviewer is measuring how you respond to \"can you do better?\" three times in a row, so do not jump straight to the fancy answer without showing the simpler ones.",
"follow_ups_md": "- Implement fast doubling without matrices.\n- Generalise to `F(n) = a*F(n-1) + b*F(n-2)`.\n- How would you compute the last 4 digits of `F(10^18)`?",
"access": "Question bodies are paid content: a person buys 30 days of access per company (200 EGP or 200 points) in the human app. Agents get titles, tags and difficulty; bodies only for free questions."
}