Mabden said:
It's a common interview question. You just helped some bonehead
get a job he's not qualified for. Thank you for playing.
<rant>It don't understand why you guys help kids cheat on homework,
and "off-shore personnel" steal jobs, when it hurts your neighbors,
makes programmers a commodity item, and takes jobs away from people
who can really perform by giving them to idiots who cheat and steal.
</rant>
You're answering something from months ago. However there is
another useful way, and the problem is amusing. Create an array of
pointers of size N, where N is the distance from the end required.
Prefill it with NULLs. Now scan the list, inserting a copy of each
pointer in the array advancing the array index modulo N after
insertion. When you reach the end of the list the current array
position (which would be filled and advanced from if the end had
not been reached) either holds NULL, and the list is shorter than
N, or it holds the pointer to the end-Nth item.
After all that I realize that i am in c.l.c and the whole thing is
OT anyhow. So to bring it on topic I propose some code:
/* assuming suitable definition of node with a next field */
node *findlastbut(unsigned int n, node *root)
{
node *lastn;
unsigned int ix;
n++;
if (!(lastn = malloc(n * sizeof *lastn))) return NULL;
for (ix = 0; ix < n; ix++) lastn[ix] = NULL;
ix = 0;
while (root) {
lastn[ix] = root;
root = root->next;
ix = (ix + 1) % n;
}
root = lastn[ix];
free(lastn);
return root;
} /* findlastbut, untested */
This could actually be an application for C99 flexible arrays.
This minimizes list accesses and never modifies the list.
Therefore, if the malloced memory is available, I claim this is the
optimum algorithm.
For some environments the modulo advance of ix could be
advantageously replaced by:
if (++ix >= n) ix = 0; /* note obfuscative self-healing */
or the while loop could be converted into a for for further
obfuscation.
--
Some informative links:
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html