> Приведи пример алгоритма с временной сложностью O(n^3) (Go)

Короткий ответ

Классический пример - перемножение двух матриц размера n×n наивным тройным циклом. Внешние два цикла задают координаты результата, внутренний пробегает по общей размерности, поэтому число операций пропорционально n^3. На senior-уровне важно сразу назвать trade-off: O(n^3) приемлемо для малых n или как baseline, а на практике применяют Штрассена, блочные алгоритмы или BLAS.

Подход к решению

Идея в том, чтобы получить три вложенных цикла, каждый из которых линеен по n. Для матриц C = A × B элемент C[i][j] равен сумме A[i][k] * B[k][j] по k. Внешние циклы по i и j дают n^2 итераций, внутренний по k добавляет множитель n. Итого O(n^3) по времени и O(n^2) по памяти для результата. На Go стоит учитывать cache locality: обход B по столбцам плохо ложится на кэш, поэтому часто применяют транспонирование B или блочный (tiled) вариант.

Пример кода

GO
package main

import "fmt"

// MultiplyNaive возвращает A × B для квадратных матриц размера n×n.
// Временная сложность: O(n^3), память: O(n^2).
func MultiplyNaive(a, b [][]int) [][]int {
	n := len(a)
	c := make([][]int, n)
	for i := range c {
		c[i] = make([]int, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			sum := 0
			for k := 0; k < n; k++ {
				sum += a[i][k] * b[k][j]
			}
			c[i][j] = sum
		}
	}
	return c
}

func main() {
	a := [][]int{{1, 2}, {3, 4}}
	b := [][]int{{5, 6}, {7, 8}}
	fmt.Println(MultiplyNaive(a, b)) // [[19 22] [43 50]]
}

Edge cases

Пустые матрицы или n = 0 требуют раннего возврата, иначе паника на индексации. Несогласованные размерности (len(a[0]) != len(b)) нужно валидировать до циклов. Переполнение int при больших значениях - на senior-уровне стоит упомянуть big.Int или int64. Ragged-матрицы (разная длина строк) ломают предположение о квадратности. Также важно помнить, что in-place умножение без дополнительной памяти невозможно для общего случая.

Как отвечать на собеседовании

Начните с формулировки: три вложенных цикла, каждый линеен по n, отсюда O(n^3). Приведите матричное умножение как канонический пример, затем назовите альтернативы - Floyd-Warshall, наивная проверка всех троек в графе, тройной вложенный перебор в задачах оптимизации. Покажите, что понимаете разницу между теоретической и практической сложностью: упомяните кэш, блочность, SIMD. Если спросят про оптимизацию, предложите транспонирование B или переход к Штрассену O(n^2.81).

Что проверяет интервьюер

Умение приводить конкретный пример, а не абстракцию. Понимание, откуда берётся куб - из комбинации трёх линейных циклов. Знание практических ограничений и альтернатив. Способность обсуждать trade-off между простотой и производительностью. Владение Go на уровне аллокаций, срезов и cache-friendly обхода.