Quant developer HFT course · Module 1: Reading hot code
Drill: reading hot code
Five prompts in the order an interviewer would ask them. Answer each out loud before you open anything, then make the multiple-choice pick, then read what weak answers sound like and compare yours with the strong one.
Prompt 1: Two loops, same complexity
The interviewer says
Both our loops over the day's quotes are O(n). Ours takes twice as long. Why might that be?
Before you answer
Question · choose every correct option
Which explanations are worth raising? Choose all that apply.
Every correct option is a per-iteration cost or a measurement problem. The Big-O constant is not a fixed property you look up; it is exactly what the other options decompose.
Answers that lose the point
Both are O(n), so they should be the same speed.
Contradicts the evidence the interviewer just gave you.It's cache misses.
Possibly right, but it is a guess offered as an answer. Name the method first.Theirs is probably using SIMD, which is eight times faster.
Invents both a cause and a number.
A strong answer
Big-O tells us the two loops grow the same way, so the factor of two is in what one iteration costs. I would walk one iteration of each: how the data is laid out and whether it is read in order, whether the body allocates, copies or logs, whether calls are direct and inlinable, and whether there are branches without a pattern.
Before chasing any of that, I would check the benchmark itself: that it uses realistic data, is warmed up, and that the compiler has not removed or simplified one of the loops. Then I would confirm the suspected cause with counters such as cache misses and branch misses.
Prompt 2: Vector or list
The interviewer says
We keep the recent quotes for a contract and walk all of them on every update. Vector or list?
Before you answer
Question · choose every correct option
Which statements belong in a strong answer? Choose all that apply.
The scan rewards contiguity; the list's strengths are stability and splicing, which this use does not need.
Answers that lose the point
Vector, always.
Right choice, no reasoning, and it ignores the cases where a list is right.List, because removing old quotes from the front is O(1).
Front removal is real, but a ring buffer or deque gives it without scattering nodes.
A strong answer
A vector, or a ring buffer if old quotes are dropped from the front. The scan is the hot operation, and contiguous storage means each cache line fetched holds the next two or three quotes and the hardware can prefetch ahead. A list puts each quote in its own node, so every step is a dependent load to an unpredictable address.
I would choose a list only if I needed iterators that survive insertions or cheap splicing, and even then I would try an intrusive list over a preallocated pool first.
Prompt 3: Why nearby is cheap
The interviewer says
You keep saying contiguous memory is faster. Explain why, at the level of the hardware.
Before you answer
Question · choose every correct option
Which statements are correct? Choose all that apply.
Lines, cache hits on the rest of a line, and prefetching are the three mechanisms. Where data lives is decided by access history, not by whether it is contiguous.
Answers that lose the point
L1 is 1 ns and DRAM is 100 ns.
Figures quoted without a machine or a measurement. Say "an order of magnitude or two" and offer to measure.It depends on the hardware.
True and useless. The line-based model holds on every machine you will discuss.
A strong answer
The CPU moves memory in cache lines, 64 bytes on the machines we would run on. Reading one quote brings in its whole line, and with 24-byte quotes that line also holds most of the next two, so those reads hit the cache.
On top of that, the prefetcher notices that we are walking upward through memory and starts fetching the following lines before we ask. With scattered nodes neither effect helps: each node may be in a different line, and its address is not known until the previous load completes, so the misses cannot overlap.
Prompt 4: The handler with no new in it
The interviewer says
This handler builds a std::string tag, pushes into a local std::vector and creates a shared_ptr for every order. There is no new in it. Does it allocate?
Before you answer
Question · choose every correct option
Which are real costs here? Choose all that apply.
Library types allocate on your behalf. Allocator fast paths are quick, but the slow paths set the latency tail.
Answers that lose the point
No new, no allocation.
The point of the question is the allocation you did not write.Allocation is fast nowadays.
The average is fast. The occasional slow path is what shows up as a spike.Write a custom allocator.
A real tool, but you skipped finding the allocations and the simpler fixes.
A strong answer
Yes, three times or more. The string allocates once the tag is longer than its inline buffer. The local vector allocates its buffer on the first push_back, every call, because it starts empty each time. make_shared allocates the order and its reference count.
Each of those is usually quick, but each can take the allocator's slow path, and that is where latency spikes come from. I would keep the tag as an integer and format it off the hot path, make the vector a member that is cleared and reused, and take orders from a preallocated pool. Then I would confirm the hot path makes no allocations after warm-up with an allocation hook in a test.
Prompt 5: The three-times-faster benchmark
The interviewer says
Your new version benchmarks three times faster. Convince me.
Before you answer
Question · choose every correct option
Which checks would you mention? Choose all that apply.
Each check rules out a way the number can be wrong. Line count says nothing about speed.
Answers that lose the point
The benchmark says so.
The benchmark is exactly what is being questioned.I ran it once and it was 3.1 times faster.
One run, one number, no spread.
A strong answer
I would first make sure the benchmark measures the work: the results are kept alive so the compiler cannot delete the loop, it runs on recorded production data rather than a constant, and it is warmed up. Then I would show the distribution over several repetitions, not one figure.
Then I would explain the gain. If I removed allocations, the allocation count should drop to zero; if I fixed the layout, cache misses should fall. If the counters agree with the story, I would check it end to end on recorded traffic, because an improvement in isolation can vanish once other code is sharing the cache.
After the drill
The same pattern runs through all five answers: name the cost per iteration, name the mechanism, name the fix, and say how you would measure it. Module 2 takes the same approach to object lifetime and ownership, which is where most C++ bugs in these interviews come from.