TEchnical Interview question: given that each character of word is
stored in each node of singly linked list. how would you determine that
the word is a palindrome?
Anybody with a cleaner method?

<amujoo@yahoo.com> wrote in message
news:1106552517.205356.43670@f14g2000cwb.googlegro ups.com...
This sounds like a homework question. So rather than a solution, here's a
hint: recursion.

--
Roger

"Roger Willcocks" <roger@rops.org> wrote:
Some of these homework questions often produce interesting diversions.
(Like the array puzzle recently.)

What's a reasonable delay before we start posting algorithms and code?

Bill, dunno.

--
http://billpg.me.uk/
usenet(at)billpg(dot)me(dot)uk

Bill Godfrey wrote:
Don't know. One or two days sounds reasonable. Posting _wrong_ solutions
,(or to a related problem) is also acceptable ;-]

Personally, I always get a bit angry by the bad "design" of the
homework-problems. Who would *ever* want to create a linked list
of characters, and then invert it. But, I know, it is only for
demonstration-purposes.

AvK

moi wrote:
[Snip!]
about coding, and has designed a lisp-like language that will use linked
lists as default for strings, on the grounds that
i) You should only worry about performance if profiling shows a
bottleneck (and you could always tell the compiler to go back to
byte-array strings).
ii) He says it makes various recursive string functions easier (maybe
this problem is an example, I don't know).

So, who knows, maybe in a few years people will be using linked lists
for characters.

Ref:
http://paulgraham.com/arc.html

All the best,
Rob M
(keen lurker, first post to comp.programming)

p.s. Do you really approve of giving wrong solutions to problems? Seems
more likely to lead to flame wars.
You: (Wrong solution)
Random passerby: "Your solution is wrong, here's a patronising
explanation why."
You: "I know, I was kidding."
R.P.B: "Idiot."
You: "$%%$^TY&*^$^%!"

Rob wrote:
) p.s. Do you really approve of giving wrong solutions to problems? Seems
) more likely to lead to flame wars.
) You: (Wrong solution)
) Random passerby: "Your solution is wrong, here's a patronising
) explanation why."
) You: "I know, I was kidding."
) R.P.B: "Idiot."
) You: "$%%$^TY&*^$^%!"

You need to make the wrong solution wrong in such an obvious way
that anyone with half a brain would recognize it as a troll/joke.

That way, if an RPB seriously comments that it is wrong, you can
then bait him further for additional laughs. It's okay to do this
at the expense of sait RPB, because he was too stupid to recognize
the jokishness in the first place.

I personally find solutions that actually do what's required, but
are 'wrong' in subtle ways (needlesly complex, recursive when it's
not needed, etcetera).

For example, the following code will check if a linked list of chars
is a palindrome: (C-like, not guaranteed to be actual C)


typedef struct linked_list {
struct linked_list *next;
char character;
} ll_type;

char get_index(ll_type *list, int index)
{
int i;
for (i = 0; i < index; i++) {
list = list->next;
if (!list) error("Index out of bounds!");
}
return list->character;
}

int get_size(ll_type *list)
{
int i;
for (i = 0; list; i++)
list = list->next;
return i;
}

bool check_palindromity(ll_type *list)
{
int i;

for (i = 0; i < get_size(list)/2; i++) {
if (get_index(list, i) != get_index(list, (get_size(list)-1)-i))
return FALSE;
}
return TRUE;
}


Flame on! :-)


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Willem wrote:

I Just noticed.

[Excellent code snipped]

LOL
BTW code seems to parafrase the immortal:

for (i=0; i < strlen(buff); i++) {
... something with buff[i] ...
}
Can't you just overload strlen() in C++ ?

@ Rob Morris: as a matter of fact I recently read most of
Paul Graham's writings on his website.
I don't know lisp, so I skipped most of his attempts to
extend it.

HTHTHW,
AvK

Roger Willcocks wrote:
Can you do it in O(n) using O(1) memory? I don't think you can do it
efficiently using recursion.

CTips wrote:
) Can you do it in O(n) using O(1) memory? I don't think you can do it
) efficiently using recursion.

Of course recursion is efficient, you're basically using the stack as O(n)
extra memory. Note that the recursion is linear.

And about O(n) time and O(1) memory: Are you allowed to alter the
linked list ? If not, I doubt it can be done within those restraints.
(Assuming it's singly linked, of course. Doubly linked is easy.)


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

amujoo@yahoo.com wrote:
This should do it:

/* Subject: Palindrome in Linked list Date: 23 Jan 2005 23:41:57
-0800 From: amujoo@yahoo.com Organization:
http://groups.google.com Newsgroups: comp.programming

TEchnical Interview question: given that each character of word
is stored in each node of singly linked list. how would you
determine that the word is a palindrome? */

#include <stdio.h>

#include <stdlib.h>

typedef struct litem { struct litem *next; char ch; } litem,
*litemp; /* ------------------ */ static litem
*appendtolist(litem *oldlist, const char *str) { litem *new;

while (*str) { if (!(new = malloc(sizeof *new))) break; else {
new->next = oldlist; new->ch = *str++; oldlist = new; } } return
oldlist; /* fail by not appending */ } /* appendtolist */ /*
------------------ */ /* believed necessary and sufficient for
NULL terminations */ /* Reverse a singly linked list. Reentrant
(pure) code */ static litem *revlist(litem *root) { litem *curr,
*nxt;

if (root) { /* non-empty list */ curr = root->next; root->next =
NULL; /* terminate new list */ while (curr) { nxt = curr->next;
/* save for walk */ curr->next = root; /* relink */ root = curr;
/* save for next relink */ curr = nxt; /* walk onward */ } } /*
else empty list is its own reverse; */ return root; } /* revlist
*/ /* ------------------ */ static void showlist(litem *list) {
while (list) { putchar(list->ch); list = list->next; } } /*
showlist */ /* ------------------ */ static int qpalind(litem
*list) { char ch;

if (NULL == list) return 1; else { ch = list->ch; if (NULL ==
(list = list->next)) return 1; list = revlist(list); if (ch !=
list->ch) return 0; else { list = list->next; return
qpalind(list); } } } /* qpalind */ /* ------------------ */ int
main(int argc, char **argv) { litem *list; int i;

if (argc < 2) fprintf(stderr, "usage: qpalind string"); else { /*
form full list */ list = NULL; list = appendtolist(list,
argv[1]); for (i = 2; i < argc; i++) { list = appendtolist(list,
" "); list = appendtolist(list, argv[i]); } showlist(list); /*
check for palindrome */ if (qpalind(list)) printf(" is"); else
printf(" is not"); printf(" a palindrome\n"); } return 0; } /*
qpalind main */



--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

CBFalconer wrote:
) This should do it:
)
) <snip excellent piece of code>

Nice one. ^_^ I forgot the bit where the regulars try to outdo each other,
doesn't happen that often. Took me a bit to realise that it's quite a gem,
efficiency-wise.. At first glance, I hadn't noticed it. Very well done.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

In article <20050124061408.737$br@newsreader.com>, bill-godfrey@sunny-
daventry.invalid says...
Someone suggested a couple of days. That's far too short IMO. Sure, some
of them will wait until the last minute to ask. Others may just go for
the free help on day one, with 2 weeks to turn in an answer.

I really don't see any reason to supply a complete working solution
instead of hints, given AFTER they have posted their current progress
toward a solution.

At least make them think about it for a while...

--
Randy Howard (2reply remove FOOBAR)

In article <41F51594.2F9EB245@yahoo.com>, cbfalconer@yahoo.com says...

:-)

Willem wrote:
EXCELLENT! But the fragment does destroy the linked list
(don't know if that was allowed ...) Try:

/* ------------------ */ static int qpalind(litem *list) { char ch;
if (NULL == list) return 1; else { ch = list->ch;
if (NULL == list->next) return 1; list->next =
revlist(list->next); list = list->next; if (ch !=
list->ch) return 0; else { return qpalind(list->next); } } }

[manually regoogled ;-]

This will (hopefully) the list somewhat intact (except for some random
changes ...)

AvK

"Willem" <willem@stack.nl> wrote in message
news:slrncva52t.1b7p.willem@toad.stack.nl...
Here's a recursive version that doesn't alter the list but does use the
stack as additional memory (so that list length is limited by available
recursion depth.) This code would be too opaque for a homework answer.

typedef struct _list { struct _list *next; int c; } list;

list *recurse(list *dp, list *up)
{
if (! dp) return up;
if ((up = recurse(dp->next, up)) == 0 || up->c != dp->c) return 0;
return up->next ? up->next : dp;
}

int isPalindromic(list *head) { return recurse(head, head) == head; }

--
Roger

CBFalconer wrote:
Yet another attempt:


/* ------------------ */
static int qqpalind(litem **hand) { char ch; if (!*hand) return 1;
else { ch = (*hand)->ch; if (!(*hand)->next) return 1; rrevlist(&
list->next); hand = &(*hand)->next; if (ch != (*hand)->ch) return 0;
else { return qpalind((*hand)->next); } } } /* this will need a
different kind of reverse ... */ void rrevlist(litem **hand) {
litem *this,*new; for(this = *hnd, *hnd = NULL; this; this=new) {
new = this->next; this->next = *hand; *hand = this; } }

Warning: untested code!

HTH,
AvK

"Willem" <willem@stack.nl> wrote in message
news:slrncva52t.1b7p.willem@toad.stack.nl...
Not forgetting, of course, that you can represent a doubly-linked list with
a single link. See e.g. http://c2.com/cgi/wiki?TwoPointersInOneWord which
leads to an O(n) time O(1) space implementation - rewrite the list as a
bidirectional list; check for a palindrome; rewrite the list back to as it
was originally.

But you don't of course need to reverse the entire list - just the first
half - and you might just as well simply reverse the pointers as you go
rather than doing any funky xor stuff....

/* O(n) time O(1) space check for palindromic singly-linked list */

/* reverse pointers until we get half way down the list, then start
comparing
outwards, fixing the pointers as we go */

int isPalindrome(list *head)
{
list *tail, *walk = head;
list *back = 0;
int retval = 1;
while (walk && walk->next) {
tail = head->next;
walk = walk->next->next;
head->next = back;
back = head;
head = tail;
}
if (walk)
head = head->next;
while (head) {
if (head->c != back->c)
retval = 0;
walk = back;
head = head->next;
back = back->next;
walk->next = tail;
tail = walk;
}
return retval;
}

--
Roger

Willem wrote:
Thanks. It is far from an efficient way of testing a string for
recursion, but it meets the question. I have since made it even
more obscure by taking out the end recursion, and removed reliance
on memory recovery at program exit. At any rate, he is welcome to
submit it to his instructor! In part it is formatted so that
existing software here can process the final source form.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

moi wrote:

Roger Willcocks has a nice approach else thread. It is actually
efficient, which mine makes no claim to being. :-)

Therefore I am appending mine in clear, without the qpalin()
routine, to facilitate a test bed for other versions. Just insert
your own guts in qpalin. NOTE: ispalin is NOT an available name,
per standard. So I use q for query instead.

#include <stdio.h>
#include <stdlib.h>

#define BLANK " "

typedef struct litem {
struct litem *next;
char ch;
} litem, *litemp;

/* ------------------ */

static litem *appendtolist(litem *oldlist, const char *str)
{
litem *new;

while (*str) {
if (!(new = malloc(sizeof *new))) break;
else {
new->next = oldlist;
new->ch = *str++;
oldlist = new;
}
}
return oldlist; /* fail by not appending */
} /* appendtolist */

/* ------------------ */

/* Reverse a singly linked list in place. */
static litem *revlist(litem *root)
{
litem *curr, *nxt;

if (root) {
curr = root->next;
root->next = NULL;
while (curr) {
nxt = curr->next;
curr->next = root;
root = curr;
curr = nxt;
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ------------------ */

static void showlist(const litem *list)
{
putchar('"');
while (list) {
putchar(list->ch);
list = list->next;
}
putchar('"');
} /* showlist */

/* ------------------ */

/* Check for palindromic list, destructive */
/( return 1 for palindrome, 0 if not */
static int qpalind(litem *list)
{
/* guts removed */
return 1;
} /* qpalind */

/* ------------------ */

int main(int argc, char **argv)
{
litem *list;
int i;

if (argc < 2) fprintf(stderr, "usage: qpalind string");
else {
list = appendtolist(NULL, argv[1]);
for (i = 2; i < argc; i++) {
list = appendtolist(list, BLANK);
list = appendtolist(list, argv[i]);
}
showlist(list = revlist(list));
if (qpalind(list)) printf(" is");
else printf(" is not");
printf(" a palindrome\n");
}
return 0;
} /* qpalind main */

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

Hi guys,

My solution was that go the the center of the linked list and then from
that onwards reverse the list getting the middle list pointer. then
compare the original list and the half reversed list.
isnt that better than recursion which takes O(n2) time and O(n) space.
or the one suggested by Falcon which also takes O(n2).

Thanks
Mujoo

Randy Howard wrote: