Implement matrix multiplication and fast exponentiation
Company: WeRide
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 1)
- `A` `n × m`
- `B` `m × p`
`C = A × B``n × p`
-
-
- `MOD` `MOD`
## 2) Exponentiation by Squaring
`x` `k` `MOD`
- `x^k`
- `x^k mod MOD`
- `O(log k)`
- `k = 0``x = 0`
## 3)
`n (n ≥ 0)` `n` `F(n)`
- `F(0)=0, F(1)=1`
- `F(n)=F(n-1)+F(n-2)`
- `2×2` `O(log n)`
- `MOD`
### /
- `multiply(A, B) -> C`
- `pow(x, k, MOD=None) -> value`
- `fib(n, MOD=None) -> value`
###
- `n` `10^9` DP
-
Quick Answer: This question evaluates competency in matrix multiplication, modular arithmetic, and exponentiation algorithms as applied to large-scale numeric computations such as sequence generation.