Is it possible(expected) for an individual to figure out(having never seen it before) the algorithm if asked at an interview? What other problems have equally interesting solutions?
Edit: Due to the confusion of the actual algorithm I am referring to, it is the Floyd's cycle-finding algorithm, aka, tortoise and hare algorithm.
Well, nothing's impossible as they say it.
However, if you have never heard of Dijkstra's or Flloyd's it is next to impossible to figure this out in the span of a single interview.
People spend a whole life in developing a single algorithm, just in case you were in two minds about it.
No, it's not. It took years for greatest mathematicians/computer scientists of their time to formulate those algorithms, you are not going to do the same in 2 minutes while under pressure.
For the second part of your question... Well, i don't really know what you consider interesting here. If its algorithms, data structures and combinatorics what you like, just read "The art or computer programing", it doesn't get much better than that.
The interviewers might ask an impossible or nonsensical question in order to see your reactions.
They are just wanting to understand your approach to problems, not necessarily the knowledge itself.
There is soo much information out there to retain, that the important thing is google competence and how to consume information from a firehose.
Like @fanatic23 said, if you've never heard of Dijsktra, is quite hard to figure out Floyd's algorithm, however, if you've done some graph studying, Floyd is one of the basic algorithms. If you're looking for job positions which might require you to have some competent algorithmic skills, I would urge you to at least read about a few algorithms considered important when using graphs:
With these 4 topics, you can navigate thru any basic to mid graph question in an interview.
As this is an interview question, you always have to ask yourself the most important question first:
What can a potential employer expect from a typical candidate and how can I do better?
Obviously, almost no one (and certainly not a prototypical candidate) will be able to perform work that took brilliant scientists years within the time constraints of an interview. So that is not what they expect from you.
What else could the employer expect?
You may already know the algorithm. This is simple and boring. You can just tell so and most likely the topic will be switched, because there is not much more to be learnt about yourself (from the point of view of the employer).
You may not know the algorithm. This is actually the typical candidate's state to be in, and if that is expected, what should the result be? Consider the company's perspective here and you will find that it is most likely not a good thing if a candidate is unable to state the obvious: I do not know this algorithm. If you start giving vague sentences and talk around the real issue here, then you will give a bad impression. So the primary purpose of asking such a question is not to expect you to be able to answer it, but to test your reaction when encountering things you do not know.
You may not know the algorithm, but... to come back to the original question above: how can you do better? You may know similar algorithms, so do explain the similarities you recognize (for example, Floyd's Tortoise+Hare algorithm uses a similar approach as the Polard-Rho-Algorithm). You may have impressive code-reading/understanding skills, etc.. Of course, this part is the hardest, but then again, it's only available if you actually are better than the average candidate, which by definition makes it kind of easier.
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.
