[mvgoogler]

I would ask the interviewer and use it as an opportunity to show your knowledge of data structures and your ability to reason about trade-offs and talk through priorities.

I would say something like: "I think a balanced tree, such as an rb-tree, would be useful here for <reasons that make sense given the problem and the properties of rb trees>. I've written rb trees before and think I could write a basic one in 10-15 minutes or I could use <class from the std library, which uses a balanced tree>. Which would you prefer?"

Assuming what you said made sense I would take an interaction like that as a positive signal.