Design an In-Memory Market-Data Store

Understanding the problem

This is the movie-database problem that runs through the SIG coding loop, promoted to a design round. In the coding version you build a class that returns movies by genre and by a range of years. Here the objects are instruments instead of movies, and a price feed writes into the store while people read from it. The core is identical: pick the right in-memory representation so lookups stop scanning. If you have worked the range and category lookup store, you have already built the heart of this. The design round adds the service around it.

Read the shape before drawing anything. Everything lives in one process and in memory, because a trading system cannot pay a network hop or a disk read on the query path. The instrument universe is bounded, tens of thousands of equities, hundreds of thousands of option and future contracts, so the whole set fits in RAM many times over. Prices change constantly while the reference data behind them barely moves. That split, a small fast-changing layer sitting on a larger nearly-static one, is the design. Say it early and the rest follows.

The Susquehanna angle

SIG grades this round on data-structure judgment and clean stateful code. The firm builds and runs its own low-latency trading systems, and it wants concrete engineering. Pick the right container for the access pattern, lay memory out so a lookup touches few cache lines, and write a class whose state is easy to reason about. The classic misread, reported again and again on the movie version, is reaching for a segment tree on the range query when plain hashmap bucketing is what the interviewer is after. Reach for the ornate structure and you have failed the test the question exists to run. The rounds are in a shared editor in C++ or Python, with C++ weighted heavily on the low-latency desks, so be ready to talk about layout and allocation, not just big-O.

Functional requirements

Keep the scope tight and let the interviewer widen it. The store answers three read shapes and takes one write, and naming that up front is half the design.

Non-functional requirements

Attach a target to each one, because on this problem the non-functional side is the whole game. Read latency comes first. Strategies query the store on their hot path, so a lookup by symbol should cost a memory access or two, low microseconds, never a scan and never a lock that another thread holds. That single target drives almost every later choice. Reads never block, and reads never scan.

Write throughput is the second number. A busy feed pushes a large stream of ticks, tens to hundreds of thousands a second at peak, and each one updates one symbol's latest price. The writes are tiny and independent, so the pressure is rate, not size. The design question this raises is not "how do we store all of it," it is "how does a constant stream of updates coexist with readers that must not stall." Hold that thought for the concurrency deep dive.

Consistency here is per-instrument, and saying so precisely is worth points. A reader should always see one coherent quote for a symbol, its price and size and timestamp from the same tick, never a price from one update stapled to a size from the next. It does not need a single global snapshot across every instrument at one instant. Promising that would force coordination the problem does not need. Prices move independently, so per-symbol consistency is both cheaper and correct. Memory is a real constraint but a comfortable one. A few hundred thousand instruments at a few hundred bytes each is well under a gigabyte, so the job is laying it out for speed, not fitting it in.

• ~100K+ Instruments. Equities, options, futures; the full universe fits in RAM.
• low µs Read latency target. A lookup is a memory access, never a scan or a blocked lock.
• 10K–100K+/s Tick rate. Many tiny independent price updates, one per symbol.
• per-symbol Consistency. One coherent quote per instrument, not a global snapshot.

The set-up

Core entities

Name the few objects the store moves before drawing anything. There are three, and the split between the second and third is where the low-latency thinking starts.

There is no database and no object storage anywhere. Most designs split huge bytes from small metadata and reach for a blob store for the bytes. Here there are no bytes and no persistence on the hot path at all. The store is pure in-memory state, and its source of truth is the feed. On startup it loads the instrument universe from a reference-data file or service, replays recent ticks, then serves everything from RAM. If the process dies, it rebuilds the same way. Durability is somebody else's problem by design, which is exactly why the store can be this fast.

Because it is all in memory, the "database" question becomes a data-structure question. The symbol lookup is a hash map from symbol to a slot. The category lookup is a hash map from category to a list of members. The range lookup is the interesting one, and the deep dive works through why bucketing usually beats a tree here. This is the same reasoning the System Design 101 course covers for Redis and in-memory stores; the SIG twist is that the store lives inside your own process, not behind a network call.

API

The interface is small and every method is called on the hot path, so keep it lean and return exactly what a strategy needs. The read methods do no work beyond a lookup; the write method is the only thing that mutates state.

The read methods each return the latest quote alongside the reference data, so a consumer gets a usable answer in one call and never has to make a second lookup for the price. That is a small choice that matters on a hot path: one call, one coherent record.

High-level design

The whole thing is one process, but it has two clearly separate paths inside it, and you should draw them apart. A write path takes the feed and updates state; a read path answers queries and must never wait on the write path. The diagram codes each box by role: blue for outside sources and consumers, violet for our components, green for the in-memory state. The walkthrough tags each piece the same way.

1) Ingest and normalize. The Exchange feeds push raw messages into the Feed handler and normalizer, which parses each one and maps it to a canonical internal tick: one symbol, one price, one size, one timestamp. This is where venue quirks get ironed out, so nothing downstream has to know that two exchanges spell the same instrument differently. What we keep off the hot path here is all the parsing and mapping cost; by the time a tick reaches the store it is already clean. The bottleneck being punted: the feed is unreliable at the edges and sends late or duplicate messages. Deciding when a tick is stale enough to drop is a real concern, handled in the reliability dive.

2) Apply the tick. The Store writer, a single thread, takes the normalized tick and overwrites the symbol's slot in the Latest-quote table with the new price, size, and timestamp. It does not touch the indexes, because the set of instruments has not changed, only one instrument's price has. That is the key move: a price update is a single write to one array slot and nothing else. What stays off the path is any index maintenance, which is why a tick is cheap no matter how fast they arrive. The bottleneck being punted: that write happens while readers are reading the same slot, so making the overwrite safe without a lock is the concurrency deep dive.

3) Serve queries. A consumer calls the Query API, which resolves the query through the Symbol, category, and range indexes to a set of symbol ids. It then reads each id's current quote from the Latest-quote table and returns coherent records. A symbol lookup is one hash hit, and a category lookup adds a read of the member list. A range query walks only the matching part of the range structure, never the whole universe. No query ever scans all instruments and no query waits on the writer. The bottleneck being punted: exactly how the range structure avoids a scan, and why a hashmap usually beats a tree here, is the first and most important deep dive.

Technology choices

Each box above is a role. Name a concrete structure for each and be ready to defend the category, because the follow-ups here are all "why that and not the fancier thing." The theme running through every choice: this is an in-memory data-structure problem, so the answers are containers and layout, not services and clusters.

• The symbol index is a plain hash map from symbol string to an integer id, and everything else keys off that id. Intern symbols to small integers once, at load time, and the quote table can be a flat array. A lookup becomes an array index instead of a hash of a string. The failure to plan for is a symbol that is not present, which just returns null; there is no partial state to corrupt because the writer only ever overwrites existing slots.
• The category index is a hash map from category to a list of ids. Categories are low-cardinality, a handful of asset classes and exchanges, so this is a tiny map whose values are member lists. When the universe changes you append or remove an id from a list, an O(1) or O(list) operation done off the hot path. Readers get the whole category in one hash hit plus a walk of the list, which is optimal since they asked for every member.
• The range structure is the one real decision. For a low-cardinality discrete field like expiry date or a strike ladder, use a hash map from bucket value to a list of ids. A range query iterates the handful of bucket values inside the range and gathers their members. For a high-cardinality continuous field, a sorted array of (value, id) with binary search, or a balanced tree such as C++ std::map, gives a clean range walk in O(log N + k). The deep dive works through when each applies; the point is to match the structure to the field, not to default to a segment tree.
• The latest-quote table is a flat array indexed by symbol id, holding a small fixed-size quote per instrument. A flat array beats a hash map here because the access is always by a dense integer id, so there is no hashing and no pointer chasing, and the memory is contiguous and cache-friendly. This is the layer that changes on every tick, so its layout is where microseconds are won or lost.
• There is deliberately no external database, no message queue, and no cache tier. Adding Redis or Kafka to a single-process in-memory store is the classic over-build: it puts a network hop on the exact path that has to be microseconds. The feed itself is the durable log, and the store is the cache. Naming that you considered and rejected them, and why, reads far better than drawing them in.
• The language is C++ or Python, and the choice colors the answer. In C++ you talk about struct layout, contiguous vectors, and avoiding allocation on the tick path. In Python you lean on dicts and lists and are honest that the concurrency story leans on the interpreter rather than fine-grained atomics. On the low-latency desks the expected answer is C++, and layout questions are fair game.

The Susquehanna angle

That last bullet is the one to deliver with conviction. Reaching for Kafka and a database on a "which container do I use" problem is the SIG anti-signal. It says you pattern-matched the phrase system design to a distributed pipeline without reading the numbers. What lands is the opposite. Point at the bounded universe, the in-memory constraint, and the microsecond target, and let almost everything a normal design would add fall away, leaving hash maps, a sorted structure, and a flat array. That is the whole design, and confidently keeping it that small is exactly the judgment the round is testing.

Potential deep dives

The skeleton is small on purpose. Nearly all the signal is in the next four questions, and the interviewer will pick one or two and push hard. The first two are where the round is usually decided.

1) What does "O(1) by category and by range" actually mean, and how do you get it?

Start by being honest about the "O(1)," because the phrasing is a trap and the interviewer is watching for whether you fall in. A lookup by symbol or by category really can be O(1) to find: hash the key, get the slot. But a query that returns every matching instrument cannot be literally O(1), because producing k results is at least O(k) no matter how you store them. So "do the range query in O(1)" cannot mean constant time end to end. What it means, and what you should say out loud, is O(1) to locate the matches, no full scan of the universe. The candidate who says "O(1) to find, plus O(k) to return the k results you asked for" has already passed the part of the question the interviewer cares about.

With that framed, the question is how to locate a range's matches without scanning all N instruments. There are three shapes of answer, and the reported failure mode is reaching straight for the most elaborate one.

The sorted-array answer is genuinely good, and for many fields it is the right one. What pushes toward the next tier is a specific observation about the fields SIG queries: many of them are discrete and low-cardinality. Expiry dates fall on a monthly or weekly schedule. Strikes sit on a fixed ladder. When the number of distinct values a range can span is small and bounded, you can drop the log factor entirely.

The scaling reads lesson covers indexing and read-path design in general. Here the trick is choosing the index that matches the field, the same judgment the coding range and category lookup store drills.

2) You are handed a naive O(N) version. How do you optimize it?

This is the most-reported SIG design-flavored round, and it deserves its own treatment because the framing differs from a blank-page design. You get working code and about thirty minutes to make it fast. Often it reads a CSV of records and exposes a search that loops over the list, filtering by category and range. The code already works and passes tests. Your job is to change how it stores the data, not what it computes.

Work it in a fixed order, out loud. First, read the access pattern: which queries repeat, and on which fields. A search called once is not worth indexing; a search called on every tick is. Second, move the cost from query time to load time. The naive version does zero work at load and O(N) work per query. Build the indexes once when the data loads, and each later query drops to a hash hit plus its results. Third, name the trade you just made. Indexes cost memory and make writes do a little more work. You spend both to buy fast reads, the right trade when reads dominate.

What the interviewer grades is the diagnosis. You see that the data is not indexed for the query, then make the minimal change that fixes it, rather than rewriting the whole thing or adding structures the queries do not need. Say what you are measuring, change the storage, and re-state the new complexity. That narration is most of the score.

The Susquehanna angle

This round is design wearing coding clothes, and SIG uses it precisely because it separates people who reach for the fitting structure from people who reach for the impressive one. Do the small correct thing, index for the query and stop, and resist the urge to demonstrate range. The firm runs its own low-latency systems, so an engineer who over-builds a thirty-minute optimization is showing the exact instinct they do not want near a hot path. Restraint is the positive signal here, not a lack of ambition.

3) Ticks and reads hit the same data. How do reads stay fast without locking?

Here is the tension. The writer overwrites a symbol's quote while readers are reading that same quote. If a reader catches the write half-done, it could see a new price with an old size, which is a torn, incoherent quote and a correctness bug. The obvious fix is a lock around every quote. That is the one thing the latency target forbids, because a reader waiting for the writer's lock is a reader that stalls on the hot path. So the question becomes how to make the overwrite atomic enough that readers never tear and never block.

First, remove half the problem. Put all writes on a single thread, as in the design. Now there is no writer-versus-writer contention at all, and the only interaction left is one writer against many readers, which is a much easier problem than the general case.

The handling contention lesson goes deeper on locks, atomics, and lock-free reads; the SIG-specific point is that separating the fast-changing quotes from the nearly-static indexes lets each use the cheapest scheme that fits it.

4) How do you lay the memory out for the low-latency desks?

Push here for senior and low-latency roles, where big-O stops being the interesting axis and constant factors take over. Two lookups can both be O(1) and differ by an order of magnitude in wall-clock time depending on how many cache lines they touch. The reference-data instinct is "an array of instrument objects, each with a pointer to its quote." That is the slow layout. Following a pointer to a quote that lives somewhere unrelated in memory is a likely cache miss, and a cache miss can cost more than everything else the lookup does.

Separate hot from cold, and lay the hot data out contiguously. Keep the latest quotes in one dense array indexed by symbol id, so a tick writes one slot and a symbol read touches one cache line, with no pointer to chase. Keep the colder reference fields elsewhere, since a price update never needs them. A range query scans a single field across many instruments. A struct-of-arrays layout, one contiguous array per field, lets that scan read only the bytes it needs, and the hardware prefetcher can run ahead. The alternative pulls whole instrument records to read one field from each.

Round it out with allocation discipline. Pre-size the containers at load so the tick path never allocates, and reuse buffers for query results instead of allocating per call. An allocation on the hot path is an unpredictable stall. Interning symbols to integer ids, from the first deep dive, pays off again here, since integer-indexed arrays are the most cache-friendly structure there is. None of this changes the asymptotic story, and all of it is what the low-latency desks listen for. Reaching this level unprompted is a strong senior signal; on an entry-level loop, naming that hot and cold data should be separated is already enough.

The Susquehanna angle

Memory layout is where SIG's low-latency character shows up in the design round. The firm's edge is in systems that react to market data fast. An engineer who talks fluently about cache lines, contiguous arrays, and avoiding allocation on the tick path speaks the language of the desks that would hire them. You do not need production trading code behind you to say the right things here. Show that you know where the bytes sit matters as much as which structure holds them. For an entry or associate role this is a bonus; for senior and quant-developer roles it is close to required.

What is expected at each level

How far you carry the range structure, the concurrency, and the memory layout is roughly what sorts the levels. Here is what to land for the role you are interviewing for.

Associate / Software Engineer

Breadth-first, about 80/20. Reach a working store: hash map by symbol, hash map by category, a range structure that avoids the full scan, and a clear statement of what "O(1)" honestly means. Above all, read the query and choose the fitting structure instead of a segment tree, and be able to turn a naive O(N) search into indexed lookups. Naming that hot quotes and cold reference data should live apart is a bonus, not a requirement. The bar: a correct, right-sized in-memory design with sensible data structures and a clean interface, argued rather than recited.

Senior Software Engineer

Depth enters, roughly 60/40. You should reach the field-dependent index choice yourself, bucketing for discrete fields and a sorted structure for continuous ones, and defend the boundary. You should raise the reader-versus-writer problem unprompted and get to a lock-free read scheme, single-writer plus per-quote atomics or a seqlock, and explain why readers never block. Handle a bad or late tick as a first-class concern, not an afterthought. The bar: you find the concurrency and range-index deep dives on your own and defend the specific structures against the fancier alternatives.

Quant Developer / low-latency teams

Depth leads, roughly 40/60, and the constant factors become the conversation. Expect to reason about memory layout in detail, struct-of-arrays versus array-of-structs for field scans, cache-line behavior, symbol interning, and keeping allocation off the tick path. Market-data normalization across venues, safe reclamation of a swapped-out index, and how the store fits alongside an order book are all fair game. The bar: you own the latency argument end to end, from data structure to cache behavior, and the interviewer redirects you rather than rescues you.