I agree that I think this is what most experienced people mean when they think of understanding data structures and algorithms.
The problem is that this kind of understanding is very rarely what coding interviews check for. They either don't check for this at all - instead just making sure people can write simple code while reasoning through a simple problems under time pressure - or they check for whether people memorized a textbook, looking for a specific non-obvious data structure and algorithm.
What I try to do, because I think it almost ticks all the boxes without asking for memorization, is ask questions that start with the simple "can you program at all" part, with follow up parts that end up in a place where we can have a conversation (without implementation) about how different tradeoffs could be improved, which often leads to discussing what useful prior art might exist.
Unfortunately I think this still has very high false negative issues. I've worked with people who prove to be perfectly capable of noticing when an appropriate data structure will make a big difference in their actual work, without that coming out in their interview.
My recommendation is to have a lot of different stuff in an interview, so you aren't making a final judgement on someone over any individual part of the interview. That means the candidate can stuff up one or more parts of the interview, and you can still get good signal.
For example, do all the things you suggest. Get them to write some simple code. Talk to them about an algorithm problem. Also, give them some simpleish code with some failing unit tests and ask them to debug the code. (This requires some prep, but its a fabulous assessment to do.) Ask them about their prior work. Just do everything you can think of, and don't give any specific part of the interview too much time or attention.
In my experience, this gives candidates a lot more opportunities to impress me. I don't really care if one person on our team is particularly weak on data structures. Its kinda better if we have someone who's an absolute gun at debugging, and someone else who's amazing at data structure work. That creates a better team than if everyone is impressive in the same way.
The problem is that this kind of understanding is very rarely what coding interviews check for. They either don't check for this at all - instead just making sure people can write simple code while reasoning through a simple problems under time pressure - or they check for whether people memorized a textbook, looking for a specific non-obvious data structure and algorithm.
What I try to do, because I think it almost ticks all the boxes without asking for memorization, is ask questions that start with the simple "can you program at all" part, with follow up parts that end up in a place where we can have a conversation (without implementation) about how different tradeoffs could be improved, which often leads to discussing what useful prior art might exist.
Unfortunately I think this still has very high false negative issues. I've worked with people who prove to be perfectly capable of noticing when an appropriate data structure will make a big difference in their actual work, without that coming out in their interview.