Performance round for low-latency engineering roles.
Why the loop order matters
The question
Two implementations of matrix multiplication have identical complexity but one runs several times faster. Why?
Have a go before you open the solution. If you are stuck after a few minutes, the first paragraph below is usually enough of a nudge.
Show the worked solution
The answer
Memory access pattern. The faster order walks memory contiguously and keeps the cache lines useful.
With row-major storage, the naive i-j-k order strides down a column of the second matrix, touching a new cache line on every access.
Reordering to i-k-j reads both matrices along rows, so each loaded cache line serves many operations.
Blocking takes it further by working on submatrices that fit in cache, which is what tuned libraries do, along with vectorisation.
The general point interviewers want: for compute-bound numerical code, asymptotic complexity stops predicting runtime and the memory hierarchy takes over.
What it is testing
Whether you think about hardware, not only algorithms.
Try these next
Maximum drawdown in one pass
Warm-upGiven an array of prices in time order, compute the maximum drawdown in a single pass.
Rolling median of a stream
HardMaintain the median of the last k values of a stream efficiently.
Design a limit order book
HardWhat data structures would you use for a limit order book that must add, cancel and match quickly?
Sample from a stream of unknown length
StandardPick one element uniformly at random from a stream whose length you do not know in advance, using constant memory.
Preparing properly
Live opportunities
Interviewing soon? See who is hiring
Open vacancies we track at quant firms, grouped by role and city. Adverts are anonymised.
Hiring for these roles? Brief the desk on a hire or check your fit for a role.
Research desk
Speak to a quant market specialist
Ask what a firm really pays, how a desk hires, or where your profile sits. One reply from the research desk, in confidence, no obligation.