Reported interview periodFeb 2026–Aug 2026
Parallel Prefix Matrix Products with Autograd
Given square matrices W[0..n-1], compute inclusive prefix products P[i] = W[0] @ ... @ W[i] using a Hillis–Steele doubling scan, then implement the backward pass without relying on an automatic-differentiation …
Practice focusRequirements - weights has shape (n, d, d) ; return prefixes with the same shape. - Each scan round combines entries 2 r positions apart, using out-of-place round updates so values from one round are not mixed with the next. - Backward returns the gradient for every input matrix for an arbitrary gradient on every prefix. - Handle n=0 , n=1 , non-commutativity, and floating-point dtype consistently. - Explain saved intermediates and complexity in sequential work, parallel depth, and memory. Follow-ups 1.…