I don't know why this was downvoted - it only takes a single counter example to invalidate an absolute claim like "impossible".

Of course I can't prove I independently reinvented the tortoise-and-hare algorithm, you'll have to take my word for it. But it should be obvious that somebody did it or it wouldn't be well known today.

Yeah, considering it was an open question for 12 years, I'd be pretty surprised if you solved it immediately after hearing the solution. If you were provided hints by the interviewer and got to it with some directions, I most would believe it more.

What's more likely, somebody figured the solution out to a problem that previously took over a decade in under an hour and then felt the need to brag about it to strangers on the internet; or somebody lied online to feel better about themselves. People are certainly more likely to assume the latter.

Or perhaps people in the late 2010s are just better placed to answer this sort of question easily than people were in the late 1960s.

I don't remember when I ran into this, but it was certainly earlier than the 2010's. Perhaps 1980's or '90's.

Certainly the Internet has made it more likely that you've run into it and heard the solution.

I didn't know the history, I had no idea it was an open question for 12 years!

As I said, it was a very long time ago when I heard of the problem. I don't think it was in an interview, but I honestly don't remember the circumstances. I do remember being quite proud of myself, so I guess there's truly an element of bragging in my statement. Doesn't mean I lied though.

It appears the tortoise-and-hare solution was found by Floyd in 1967. That means the problem was first proposed in 1955? I'd love to learn more about it, do you have a source for that?

mark-r, when somebody uses the term "impossible" - generally it may mean 2 things: a) it's truly impossible b) It's very unlikely but still possible.

You settled for a). Typically of what geeks do ( yeah, I'm guilty of it too).

Anyway. you seem to be an outlier to being able to solve the problem without having being familiar with it before hand. Do you realize you are extraordinary? (FYI: I'm not saying that with sarcasm, you might indeed be "riddle" genius, or perhaps even a "real problem", problem solver)

I can see now that I was interpreting the statement contrary to the intent of the writer. Sorry about that, and thanks for pointing it out.

I've always thought of myself as being pretty clever, but I'll bet many HN readers would say the same about themselves. "extraordinary" seems a little over the top, but thank you.

>I've always thought of myself as being pretty clever, but I'll bet many HN readers would say the same about themselves. "extraordinary" seems a little over the top, but thank you.

There are enormous implications to this seemingly harmless labeling of yourself ( not blaming you). I insist you are extraordinary, not merely 'pretty clever', not only based on my observation but also judging by other people's reactions to you your post.

Off the top of my head there are 2 implications that can be typically attributed to such traits ( and I'm not saying that you are particularly cause those implications, it's just typical):

- if someone like you is an interviewee for a programming position, your average Joe interviewer who asks you algorithmic questions ( or often some clever question) will not like the fact that you can easily solve the problems that you are presented with.

- If a person like you is an interviewer for a regular corporate programming position( which does not involve algorithms), the person is likely to pose problems of this nature to candidates for the job. When candidates routinely fail to solve those problems the person is left wondering why the candidate pool is so bad. To the interviewer the solutions seems so obvious ( or can be figured out easily) to someone who is just 'clever'.

And the industry complains how it cannot find people for CRUD programming jobs....

Note that I said "basically impossible", so I was leaning towards b :)

I figured, that's what most "normal" people would assume. ( and so would I).

But computer geeks ( we are talking about kind of people who code for 'fun') are not normal people. Their default is to take words' meaning literally, unless they have somehow (often painstakingly) managed to learn the ways of normal folks communicate.

I think what folks are implying here is that the 'somebody' who initially came up with this likely didn't do so in a 55 minute whiteboard session.

Other people are implying that named algorithms, especially those named after someone famous, are somehow more special/difficult. Sometimes they are, but often they aren't. "Linear search" for instance is the name given to the easy idea of: iterate through an array until the value == search value or you hit the end. Most candidates could do this, though they might sweat a bit if you said "find x by implementing linear search" as the name for such a straightforward idea might not be known. They might have trouble writing proofs about its properties, which is where I imagine a lot of supposed scariness comes from. (i.e. "This approach looks correct but I haven't proved it yet." Academics aren't satisfied with just a test suite, or "looking at it".)

My favorite named-after-a-person one like this is Dijkstra's algorithm, which he claimed to have come up with in 20 minutes on the back of a napkin. If we suppose the average professional engineer is at most 3x slower/less brilliant than Dijkstra, it's not that unreasonable to imagine someone could reproduce the design on a whiteboard in a full hour...

Of course I don't buy that assumption, nor do I think it's a good problem or good idea to have as an interview filter even if it was true. (While I enjoy the occasional programming puzzle, I hate that they're lazily used to evaluate people in interviews so at least I avoid ever giving pure algorithm puzzles for interviews.) Nevertheless I agree with Mark that it's not "basically impossible" to come up with a good algorithm for many classes of algorithms and problems. I do wonder though how many people who could reinvent tortoise+hare without seeing it explicitly before would then be able to reinvent the teleporting turtle optimization right after.