Arrays, Nodes and the Cost of a Pointer
The most-asked data structure in trading-firm developer interviews is not a tree or a graph. It is a queue on a circular buffer, asked independently at several major firms, and it is asked because it exposes in five minutes whether a candidate thinks about memory at all.
Two ways to store a sequence
Everything in this section is a variation on one choice: elements next to each other, or elements anywhere with pointers between them.
Contiguous (array, vector)
Index the middleConstant, one address calculation
Insert in the middleLinear, shift everything after
GrowAmortised constant, occasionally copies everything
Memory per elementThe element
Cost per step in a scanA fraction of a cache miss
Linked (list, node chain)
Index the middleLinear, follow every pointer
Insert in the middleConstant, if you already hold the node
GrowConstant, one allocation per element
Memory per elementThe element plus one or two pointers
Cost per step in a scanA cache miss and a dependent load
Identical asymptotics, very different machines.
The rest of this lesson is for subscribers
Unlock every lesson in Programming for Quantitative Developers, and every other premium course.
Subscribe to continueTest your knowledge
Questions are only available to subscribers.
Keep reading Programming for Quantitative Developers
25 lessons in this course, and every other premium course, on one subscription.
- Every lesson in every course, with the worked examples and interactive simulators
- Graded questions on every lesson, with explanations for the wrong answers as well as the right one
- The trainers, timed assessments and brainteaser library that go with them