Implement a Risk-Score Priority DetectionStore With Put and GetNext in C++
Company: Crowdstrike
Role: Backend Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
Design and implement a data structure, `DetectionStore`, that stores security detections and hands them out by priority.
A `Detection` has three fields: `unique_id`, a unique identifier; `risk_score`, the detection's risk score; and `data`, its payload. Implement the two methods of `DetectionStore`:
```cpp
struct Detection {
std::string unique_id;
unsigned long risk_score;
std::string data;
};
class DetectionStore {
public:
void Put(const Detection& detection); // store a detection
std::unique_ptr<Detection> GetNext(); // remove and return the next detection to process
};
```
`GetNext` chooses the next detection according to `risk_score`. Write the class in C++ and state the time and space cost of each method.
```hint Two operations, two speeds
You insert arbitrary detections and always remove the current best one. Think about which structure makes both of those cheaper than scanning everything, and what each one costs.
```
```hint Handing over ownership
`GetNext` returns a `std::unique_ptr`. Check whether the container you pick lets you move its best element out, or only gives you read-only access to it.
```
### Constraints and Clarifications
- The interface and the field types are given; the internal representation is up to you.
- The source does not say whether a higher or a lower `risk_score` is served first, how equal scores are ordered, what `GetNext` returns on an empty store, or what `Put` does with a `unique_id` that is already stored. Ask, or state your choice and design for it.
### Clarifying Questions
- Is the next detection the one with the highest `risk_score`?
- Among detections with the same `risk_score`, which comes first: the oldest, or is any order acceptable?
- What should `GetNext` return when the store is empty: a null pointer, or should it wait until a detection arrives?
- If `Put` receives a `unique_id` that is still stored, should it replace the stored detection, keep the higher score, be ignored, or report an error?
- Will several threads call `Put` and `GetNext` at the same time?
- Roughly how many detections are pending at once, and how large is `data`?
### What a Strong Answer Covers
- A priority structure with logarithmic or better `Put` and `GetNext`, and an explicit, deterministic rule for equal scores
- Correct ownership: the result leaves the store as a `std::unique_ptr` without copying `data` again and without dangling references into the container
- Defined behavior for an empty store and for a repeated `unique_id`, with the extra indexing that behavior requires
- Correct ordering of `unsigned long` scores across their full range
- Time and space complexity of each method, and a comparison with at least one alternative structure
- Thread safety, or an explicit statement of why the class is not thread-safe
### Follow-up Questions
- Many producer threads call `Put` and several workers call `GetNext`. How do you make the store safe, and how would a blocking `GetNext` with a timeout work?
- Add `Update(unique_id, new_score)` and `Remove(unique_id)`. What changes in your data structures, and what do the operations cost?
- Low-risk detections may wait forever while high-risk ones keep arriving. How would you prevent starvation without delaying urgent detections?
- The store may hold at most a fixed number of detections. What happens when it is full and another `Put` arrives?
Overview: Implement a C++ DetectionStore whose Put stores security detections with an id, an unsigned risk score and a payload, and whose GetNext removes and returns the next detection by risk score as a unique_ptr. Tests priority-structure choice, ownership semantics, tie and duplicate-id policies, and thread safety.