Quick Overview

Multiply two integer matrices with compatible dimensions and return their product. This coding warm-up tests careful indexing over rows, columns and the shared inner dimension, correct output dimensions for non-square inputs, and clean handling of single-row and single-column matrices.

Multiply Two Integer Matrices of Compatible Dimensions

Company: eBay

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given two integer matrices `a` and `b`, return their matrix product. ### Function Signature ```python def multiply_matrices(a: list[list[int]], b: list[list[int]]) -> list[list[int]]: ``` ### Rules - `a` has `m` rows and `n` columns, and `b` has `n` rows and `p` columns. Every row of a matrix has the same length. - The number of columns of `a` always equals the number of rows of `b`, so the product is always defined. - Return the product `c` as a list of `m` rows, each a list of `p` integers, where `c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + ... + a[i][n-1] * b[n-1][j]`. ### Constraints - `1 <= m, n, p <= 100` - `-1000 <= a[i][j] <= 1000` and `-1000 <= b[i][j] <= 1000` - Every entry of the result has absolute value at most `100 * 1000 * 1000 = 10^8`, so it fits in a 32-bit signed integer. ### Examples **Example 1** ```text Input: a = [[1, 2], [3, 4]], b = [[5, 6], [7, 8]] Output: [[19, 22], [43, 50]] ``` For example, `c[0][0] = 1 * 5 + 2 * 7 = 19` and `c[1][1] = 3 * 6 + 4 * 8 = 50`. **Example 2** ```text Input: a = [[1, 0, -2]], b = [[3], [4], [5]] Output: [[-7]] ``` A 1 × 3 matrix times a 3 × 1 matrix gives a 1 × 1 matrix: `1 * 3 + 0 * 4 + (-2) * 5 = -7`. **Example 3** ```text Input: a = [[2], [-1]], b = [[1, 0, 3]] Output: [[2, 0, 6], [-1, 0, -3]] ``` A 2 × 1 matrix times a 1 × 3 matrix gives a 2 × 3 matrix.

Overview: Multiply two integer matrices with compatible dimensions and return their product. This coding warm-up tests careful indexing over rows, columns and the shared inner dimension, correct output dimensions for non-square inputs, and clean handling of single-row and single-column matrices.

Read the full eBay Machine Learning Engineer interview experience this question came from

Given two integer matrices `a` and `b`, return their matrix product. `a` has `m` rows and `n` columns, and `b` has `n` rows and `p` columns. Every row of a matrix has the same length. The number of columns of `a` always equals the number of rows of `b`, so the product is always defined. Return the product `c` as a list of `m` rows, each a list of `p` integers, where `c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + ... + a[i][n-1] * b[n-1][j]` for every `0 <= i < m` and `0 <= j < p`. Row `i` of the returned list holds `c[i][0], c[i][1], ..., c[i][p-1]` in that order. Every entry of the result has absolute value at most `100 * 1000 * 1000 = 10^8`, so no value exceeds `2^31 - 1` and a 32-bit signed integer (`int` in Java and C++) is sufficient. ### Example 1 ```text Input: a = [[1, 2], [3, 4]], b = [[5, 6], [7, 8]] Output: [[19, 22], [43, 50]] ``` For example, `c[0][0] = 1 * 5 + 2 * 7 = 19` and `c[1][1] = 3 * 6 + 4 * 8 = 50`. ### Example 2 ```text Input: a = [[2], [-1]], b = [[1, 0, 3]] Output: [[2, 0, 6], [-1, 0, -3]] ``` A 2 x 1 matrix times a 1 x 3 matrix gives a 2 x 3 matrix; for example, `c[1][2] = (-1) * 3 = -3`. ### Constraints - `1 <= m, n, p <= 100` - `-1000 <= a[i][j] <= 1000` and `-1000 <= b[i][j] <= 1000` - Every row of a matrix has the same length, and the number of columns of `a` equals the number of rows of `b`. - Every entry of the result has absolute value at most `100 * 1000 * 1000 = 10^8`, so it fits in a 32-bit signed integer.

Constraints

  • 1 <= m, n, p <= 100, where a is an m x n matrix and b is an n x p matrix
  • -1000 <= a[i][j] <= 1000 and -1000 <= b[i][j] <= 1000
  • Every row of a matrix has the same length, and the number of columns of a always equals the number of rows of b
  • Every entry of the result has absolute value at most 100 * 1000 * 1000 = 10^8, so it fits in a 32-bit signed integer

Examples

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

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

Explanation: Source Example 1: square 2 x 2 product; c[0][0] = 1*5 + 2*7 = 19 and c[1][1] = 3*6 + 4*8 = 50.

Input: ([[1, 0, -2]], [[3], [4], [5]])

Expected Output: [[-7]]

Explanation: Source Example 2 (inner product): a 1 x 3 row times a 3 x 1 column gives 1*3 + 0*4 + (-2)*5 = -7.

Hints

  1. Work out the shape of the answer first: how many rows and columns does the product have, and which dimension is summed away?
  2. Entry c[i][j] pairs the elements of row i of a with the elements of column j of b, position by position.
  3. Use the stated bounds to check whether any intermediate sum can leave the 32-bit signed range.

Loading coding console...

Show the approach

Approach

Algorithm: build the product one row at a time. For row i of a, start a row of p zeros; then for each inner index k from 0 to n-1, take the scalar a[i][k] and add a[i][k] * b[k][j] to entry j of that row for every column j. A zero scalar can be skipped because it only adds zeros. Invariant: after inner indices 0..k have been processed for row i, entry j equals a[i][0] * b[0][j] + ... + a[i][k] * b[k][j]. Correctness: after k = n-1 every entry equals the defining sum c[i][j], and rows and entries are produced in index order, so the returned list is exactly c in row-major order. Visiting k before j reads b and writes c along rows, which only changes the order of additions, not the integer result. Edge cases: n = 1 gives an outer product, m = p = 1 gives a single inner product, an all-zero row of a or all-zero column of b gives zero entries, and identity factors return the other operand unchanged. Overflow: each product has absolute value at most 1000 * 1000 = 10^6 and there are at most 100 terms, so every partial sum and every entry stays within 10^8 and fits a 32-bit int in Java and C++.

Time complexity:
O(m * n * p)
Space complexity:
O(m * p)