> Many of those questions were thesis/publication-worthy decades ago when first solved

The hare and tortoise (cycle detection via Floyd's) is a legendary impossible interview question. It wasn't solved until the 1960s with a PhD thesis. It is a hard problem to face in an interview. I had seen it twice in my career. I failed the first time. The second time I had the answer memorised, then put on my very best Morgan Freeman stage acting to pretend I was discovering the answer during the interview. What a joke. I was laughing to myself as I was "stumbling" towards the answer while the interviewer was providing minor hints.