I've had a long career making a good living working for companies that never asked me to write a self-balancing binary search tree off the cuff. No one should

I've had a long career making a good living working for companies that never asked me to write a self-balancing binary search tree off the cuff. No one should be asking you to write a self balancing binary search tree off the cuff. One of the simplest would be a Splay tree, and even that's way too much. More relevant would be to ask for 3 or so things each of which are 1/10th the complexity, but then see if you can specify how to integrate those things together into a system in a way that shows you have experience with the pitfalls of actual coding and debugging.