I agree that knowing the details of a red-black tree rebalancing is not fair game. I wouldn't bother implementing one unless I had access to a paper written by

I agree that knowing the details of a red-black tree rebalancing is not fair game. I wouldn't bother implementing one unless I had access to a paper written by an expert like Sedgwick. Which leads into my gripe with programming interviews. My biggest problem with this culture of interviewing is that most people don't seem to know/appreciate the complexity of the questions they are asking. There's been a number of times where my interviewer completely lacks any knowledge on the background theory/history on the question they asked me. Afterwards I tend to find the question in Knuth or an Algo book. That being said, I do think knowing that red-black trees, like AVL trees, fundamentally rely on Tree Rotations to maintain invariants about the tree which ensures its height balance IS fair game, IF you require formal algo knowledge from your candidates. With that knowledge, theoretically a well-read interviewer can guide someone to towards a partial implementation. And from that knowledge, if someone would to introduce the concept of a splay tree, I could guess that since its a self-balancing binary search tree, it likely relies on tree rotations as well. You would need to bounce that off the interviewer obviously. But if you're not familiar with the concept of tree rotations, and/or data structure invariants, you probably won't succeed no matter how much coaching your interviewer provides, due to pressure on your working memory.