Is it possible(expected) for an individual to figure out(having never seen it before) the algorithm if asked at an interview?
Is it possible? That depends on the algorithm and the candidate. I'd say that the vast majority of candidates would struggle to actually do this kind of thing. (If these problems were that simple, why would someone be famous for having solved them?)
Is it expected? That depends on the foibles of the interviewer, and their expectations of candidates. I'd say that if they really expect candidates to be able to do this kind of thing in an interview they are going to have to interview a lot of candidates. A question like this is more likely to be asked to see how the candidate works / thinks under pressure.
What other problems have equally interesting solutions?
I'm not going top answer that. Rather I'm going to say that:
The likelihood that you (as a candidate) will be expected to do this is small, for a typical job. However, if you are applying for a specialist IT job where there is a particular requirement to know specific algorithms, you might be asked to explain them.
There is little point learning to derive algorithms in case you are asked to. (Or "cheating" by knowing the algorithm beforehand.) If you are actually asked to do this, you try your best ... in the knowledge that most other candidates are likely to struggle as well.
It is useful to know a range of algorithms, or at least know of them, because they may turn out to be useful in your work. However, that very much depends on the field of IT that you will be working in.