The question on the interviewee's mind is whether the interview is a proxy for first principles ability or whether they really want you to implement such-and-such exactly correctly. In principle I agree with you -- I had the conversation recently that I have no idea how to implement a red-black tree anymore and would probably fail a "balance a red-black tree when inserting X" type of question, even though I had to do it perfectly in C++ in school. I'm not even sure which color has which constraint by convention. But I more or less remember the constraints, and as I talked through it I sort of remembered how the constraints leads to self-balancing (and an approach to do it). Given time and a responsive interviewer who can answer even dumb questions like "red-black trees are defined to be binary trees right?" I could probably produce something on a whiteboard, but I have my C++ code somewhere and I'm pretty certain I couldn't reproduce that precisely on a whiteboard. What I could do would satisfy some interviewers probably, but would not satisfy others.

On the interviewer side of the table, if there's a particular property I want to test for, then I'll try and test for it directly if it's possible. One such property was "ability to make changes to a program one didn't write and can't fit entirely in one's head" since that's the majority of employed work (especially at larger companies) and I've had successes testing that directly on intern candidates by having them do just that in a stripped down version of part of some front-end code.

There are a lot of employed devs who seem to struggle with first principles. I don't think it's a good thing and would want to filter on it for a company I controlled from the start... But if we want to test for that specifically, I'm not convinced data structure questions are a good way to do it. Since discrete math should be a standard part of the curricula, I think asking for some proofs of certain theorems given certain axioms and reminders of the rules of inference would be more fruitful. But that would likely be even less popular than linked list style questions. In the limit what I'd really be most satisfied by in terms of having nice proxy measures on cognitive abilities like first-principles reasoning, (system|task|...) decomposition, etc. would be testing IQ and big-5 personality traits directly, plus interviewees should only have to do it once (or at infrequent intervals) rather than every company having their own process, though I think legally you'd have to pay the Wonderlic tax to do it.