Katkat
Back

Implement matrix multiplication and fast exponentiation

WeRideSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates competency in matrix multiplication, modular arithmetic, and exponentiation algorithms as applied to large-scale numeric computations such as sequence generation.

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