Quant developer HFT course · Module 3: Containers and memory
Drill: containers and memory
Five prompts that test whether you know what a container does in memory, not just its complexity. Answer out loud, pick the options, then compare.
Prompt 1: The amortised promise
The interviewer says
push_back is O(1) amortised. Is that good enough for our order entry path?
Before you answer
Question · choose every correct option
Which statements are correct? Choose all that apply.
Amortised bounds average over a sequence; the latency path cares about the worst single operation.
Answers that lose the point
Yes, O(1) is as good as it gets.
Treats the average as the worst case.Vectors are slow, use a list.
Swaps one occasional spike for an allocation on every insert.
A strong answer
Not on its own. Amortised O(1) means the total cost of n pushes is linear, but the push that hits capacity allocates a bigger buffer and moves every element, and that one operation is a spike.
On the order path I would reserve capacity at start-up for the busiest day we have seen plus margin, reuse the container by clearing it, and alert if the capacity ever changes in production. If there is a hard bound, a fixed-capacity container makes the overflow an explicit decision.
Prompt 2: The slow lookups
The interviewer says
Order lookups in an unordered_map are usually fast, with a few that are a hundred times slower. Where do you look?
Before you answer
Question · choose every correct option
Which are plausible causes? Choose all that apply.
Worst-case lookup is O(n) for a chain, not O(log n). Rehashes, bad hashing and cold memory are the usual culprits.
Answers that lose the point
Hash maps are O(1), so it must be something else.
Average O(1), with tails that come from exactly these mechanisms.
A strong answer
I would check three things. First, whether the slow lookups coincide with inserts that trigger a rehash; reserving for the peak removes those. Second, the distribution of chain lengths with bucket_size on a real day's ids, because exchange ids often have structured bits and an identity hash can pile them into a few buckets; a mixing hash fixes that. Third, whether the slow lookups are simply cold, which shows up as cache misses in the counters.
If those are fixed and the tail remains, I would move to an open-addressing table storing handles into the order pool, which removes the per-node allocation and the pointer chase.
Prompt 3: Ordered and fast
The interviewer says
We need price levels in order for the book, with frequent inserts and deletes near the best price. std::map?
Before you answer
Question · choose every correct option
What would you say? Choose all that apply.
A hash map loses the ordering the book needs. A tick-indexed array keeps both speed and order for the dense part of the book.
Answers that lose the point
unordered_map, because it's faster.
Fast lookup, no ordering: you cannot find the next level.std::map is always fine.
It is a reasonable start; the question is whether it is good enough at the touch.
A strong answer
std::map is a sound starting point: ordered iteration and lower_bound are exactly what a book needs. Its costs are a node allocation per new level and a pointer chase per lookup.
Near the best price, levels sit on a dense tick grid, so I would keep them in an array indexed by tick offset from a reference price, recentred occasionally, which gives constant-time access and ordered iteration by index. Levels far from the touch are rare and can stay in a sorted structure. I would measure both on a recorded day before committing.
Prompt 4: Allocating at speed
The interviewer says
We create orders and per-message scratch objects at a high rate. How do we avoid malloc?
Before you answer
Question · choose every correct option
Which techniques fit? Choose all that apply.
Pools fit fixed-type objects with individual lifetimes; arenas fit objects that die together; pmr lets standard containers use either.
Answers that lose the point
Write a custom allocator.
Which kind, for which lifetime? The answer is in the matching.
A strong answer
I would match the allocator to the lifetime. Orders live individually and are freed in any order, so they go in a preallocated pool with a free list: constant-time acquire and release, no heap, all orders in one warm array. Scratch objects for one message all die together, so they go in an arena that is reset after the message, with std::pmr containers pointed at it and a null upstream in tests so overflow fails loudly.
Both are owned by one thread. I would plan the capacity, alarm on exhaustion, and make sure objects freed on another thread come back through a queue.
Prompt 5: Strings on the hot path
The interviewer says
Is std::string a problem in our message structs?
Before you answer
Question · choose every correct option
What is true? Choose all that apply.
Small string optimisation avoids allocation for short contents, at the cost of a larger object and a library-dependent limit.
Answers that lose the point
Strings always allocate, ban them.
Wrong for short strings; right instinct for the wrong reason.
A strong answer
Short strings are stored inline, so a symbol or venue code does not allocate, but the limit depends on the library, 15 characters in libstdc++ and 22 in libc++, and every string member adds 24 to 32 bytes to the struct. Concatenation and anything longer allocate.
For hot message structs I would use fixed-size character fields, such as an eight-byte symbol compared as one integer, so the size is fixed, nothing branches on inline versus heap, and the struct can be copied as plain bytes.
After the drill
The thread through all five: know what the container does in memory, plan capacity up front, and match the allocation strategy to the lifetime. Module 4 adds the hardest dimension, more than one thread.