Design in-memory trade subscription processor
Company: Bloomberg
Role: Software Engineer
Category: System Design
Difficulty: medium
Interview Round: Onsite
You are asked to design and implement the internal logic of an in-memory trade subscription processor in C++. A simplified interface is provided:
```cpp
using HANDLE = int;
struct Tread {
std::string symbol; // e.g. "AAPL"
int size; // number of shares
std::string flag; // e.g. trade condition / venue flag
};
class TreadProcessor {
public:
TreadProcessor() {}
// Called whenever a new trade arrives from the market feed.
void onNewTread(const Tread &tread);
// Register interest in trades matching a given template.
// Returns a handle that can later be used to unsubscribe.
HANDLE subscribe(const Tread &filter,
std::function<void(const Tread &)> callback);
// Cancel a previous subscription.
void unSubscribe(HANDLE handle);
private:
// Design and add your internal data structures here.
};
```
You may assume:
- A **subscription** is defined by a `filter` of type `Tread` and a `callback` function.
- A new trade `t` delivered via `onNewTread` **matches** a subscription `filter` if:
- `t.symbol == filter.symbol` (exact match), and
- optionally, for this question, you can assume `size` and `flag` must also match if they are non-zero / non-empty in the filter (i.e., the filter can act as a simple template with optional fields).
- If a trade matches multiple subscriptions, **all** corresponding callbacks must be invoked with the trade.
Functional requirements:
1. `subscribe(filter, callback)`
- Registers a new subscription using the given `filter` and `callback`.
- Returns a unique `HANDLE` that identifies this subscription.
2. `onNewTread(tread)`
- Called for every incoming trade.
- Must efficiently find all subscriptions that match `tread` and invoke their callbacks.
3. `unSubscribe(handle)`
- Cancels the subscription associated with `handle` so that its callback is no longer invoked for future trades.
Non-functional / design goals:
- There can be up to `10^5` active subscriptions.
- There can be tens of thousands of trades per second.
- Aim for efficient average time complexity for `onNewTread` and `subscribe`.
- Design for reasonable memory usage.
- Assume at least one thread will be calling `onNewTread`, and another thread may be adding/removing subscriptions. Discuss how you would handle thread safety.
**Task**
Describe and justify a design for the internals of `TreadProcessor`:
- What data structures will you store in `private` to support fast matching?
- How will `subscribe`, `onNewTread`, and `unSubscribe` be implemented conceptually using those data structures?
- Analyze the time and space complexity of your design.
- Discuss how you would handle concurrency (e.g., locks, lock-free approaches, sharding, or other strategies) to support high throughput while maintaining correctness.
Quick Answer: This question evaluates a candidate's ability to design concurrent, high-throughput in-memory subscription matching systems, covering skills in data structure selection, algorithmic complexity analysis, and concurrency control.