Achilles and the Tortoise is one of the Greek philosopher’s Zeno’s paradoxes.
In a race, the quickest runner can never overtake the slowest, since the pursuer must first reach the point whence the pursued started, so that the slower must always hold a lead. – as recounted by Aristotle, Physics VI:9, 239b15
Which basically means that while the fast runner covers the distance that was between them at certain moment, the slowest goes a little farther, so the fast one has to overtake him again, and while he covers that (smaller) distance the slow one again goes on, and so the gap between them is always shortened but never disappears completely.
Recently I stumbled upon an interview question about singly linked list that made me recall this paradox.
How can you find the middle element of the list in ONE pass?
That is, not follow the list to the end to find out its size and then repeat from the beginning until you make half of the count. No, the question was to do it in just one go.
The solution to this task is to have two pointers, moving at the same time. The first would take one step, while the second would at the same time take two. When the second pointer reaches the end of the list, the first should be right in the middle. Such is the theory, and I think it is rather clever.
But what is the middle element of a list which has an even count? Is it null, or the last element in the first half, or the first element of the second?
I wish Zeno would answer that.