Quick Overview

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

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.

Matrix Multiplication

Return A times B, optionally modulo MOD.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

Input: ([[1,2],[3,4]], [[5,6],[7,8]], None)

Expected Output: [[19, 22], [43, 50]]

Explanation: Basic matrix multiplication.

Input: ([[2]], [[5]], 7)

Expected Output: [[3]]

Explanation: Modulo is applied if provided.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.

Exponentiation By Squaring

Return x^k, optionally modulo MOD.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

Input: (2,10,None)

Expected Output: 1024

Explanation: 2^10.

Input: (2,10,1000)

Expected Output: 24

Explanation: Modulo exponentiation.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.

Fast Fibonacci With Matrix Power

Return F(n), optionally modulo MOD, using 2x2 matrix exponentiation.

Constraints

  • Inputs are Python literals matching the function signature.
  • Return a deterministic exact-match value.

Examples

Input: (10,None)

Expected Output: 55

Explanation: F(10)=55.

Input: (100,1000)

Expected Output: 75

Explanation: Modulo Fibonacci.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.

Loading coding console...