An indexable skip list is a skip list annotated with, like you said, the number of elements in the sub list. I think you are discounting the setting of the inte

An indexable skip list is a skip list annotated with, like you said, the number of elements in the sub list. I think you are discounting the setting of the interview. It's not an impossible question, just like it's not an impossible question for an electrical engineer to discuss PID control tuning, but it's something that is not very appropriate for an interview. There's a reason these style interviews are called "grilling". Interviews are stressful without the pop quiz style questions. One could easily misread the question as "calculate the median of a list of integers" and forget the sliding window aspect of the question, and spend 15 minutes explaining sorting a list, grabbing the middle element, then getting thrown off when they realize it's a data structure question instead. These are reasonable problems outside the interview context, but not appropriate within.