Amazon Interview Question for Software Engineer / Developers Software Engineer in Tests


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
7
of 7 vote

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

struct node
{
	char* data;
	struct node* next;
};

int totalNumOfChars;
int numOfComps = 1;
int totalNumOfCompsRequired = 0;
int len;
int curIndex = 0;
struct node* ptr;

int recursive(struct node* node)
{
	int i;
	int isPal = 1;

	if(node->next != NULL)
	{
		isPal = recursive(node->next);
	}

	if(isPal == 1)
	{
		for(i=strlen(node->data)-1; i>=0 ; i--)
		{
			if(node->data[i] == ptr->data[curIndex])
			{
				numOfComps++;
				curIndex++;
				if(curIndex >=len)
				{
					curIndex = 0;
					ptr = ptr->next;
					len = strlen(ptr->data);
				}
			}
			else
			{
				return 0;
			}
			if(numOfComps >= totalNumOfCompsRequired)
			{
				return 1 & isPal;
			}
		}
		return 1 & isPal;
	}
	return 0;
}

void main()
{
	int isPal = 0;
	struct node* head;
	struct node* first = malloc(sizeof(struct node));
	struct node* second = malloc(sizeof(struct node));
	struct node* third = malloc(sizeof(struct node));

	first->next = second;
	second->next = third;
	third->next = NULL;

	first->data = "abcc";
	second->data = "dcc";
	third->data = "ba";

	totalNumOfChars = 9;
	totalNumOfCompsRequired = totalNumOfChars/2;

	ptr = first;
	head = first;
	len = strlen(head->data);
	isPal = recursive(first);

	printf("\n\n\tIs palindrom = %d", isPal);
}

- pm March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

works perfectly.

- pm March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

pseudocode:
1. link list -> a, b, cde, d, c, b, a 
     g_pointer = head; /*head is pointing to the start of the link list *
2. int recurse(list){
	if(list->next) {
		recurse(list)
	}
	/*here you will get the last node containing 'a' */
	while(size(last_node)) {
		if(g_pointer->data[i] == last_node->data[j]) {
			/*so first character matches so move to second one*/
			/* but before that we need to make sure that g_pointer has any
			   more data or not*/
			if(strlen(g_pointer->data) == j) /* move to next pointer */ {
				g_pointer = g_pointer->next;
 				j=0;
			} else {
				i++;j++;
			}
		} else
			return 0; /* means there is no palindrome */
	}
    }

- try March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

additionally you can check if the total_size_of_palindrome_given_in_the_problem/2 is reached or not.

- try March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Object Oriented:

def isPalindrome(linkedList):
    pl = PalindromeHelper(linkedList)
    return pl.isPalindrome(linkedList)

class PalindromeHelper:
    def __init__(self, linkedList):
        self.leftNode = linkedList;
        self.leftIndex = 0

    def isPalindrome(self, rightNode):
        isPal = True
        if rightNode.next != None:
            isPal = self.isPalindrome(rightNode.next)
        if not isPal: return isPal
        rightIndex = len(rightNode.info) - 1
        while rightIndex >= 0:
            if rightNode.info[rightIndex] != self.leftNode.info[self.leftIndex]:
                return False
            self.leftIndex = self.leftIndex + 1
            rightIndex = rightIndex - 1
            if self.leftIndex == len(self.leftNode.info):
                self.leftNode = self.leftNode.next
                self.leftIndex = 0
        return True

- Amol March 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@pm

first->data = "abc";
second->data = "de";
third->data = "dcba";

I dont think your code works for this input. Please correct me if I am wrong

- Srinivasan July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

If you have a doubly linked list, then you can do this in linear time and constant space.

With a singly linked list, you can't do this in constant space unless you're willing to pay for O(N-squared) time. To do it in linear space, you can push the node pointers corresponding to the first N/2 characters on to a stack, then pop them off as you're working through the last N/2 characters. If you don't want to maintain your own stack, you can use recursion, but there's still a stack, so it's still gonna be linear time. And, really, if you're stuck with linear time, then it might be more simple overall to just slurp all your characters into one big string, and then solve the simpler problem of finding out whether a string is palindromic.

- showell30@yahoo.com March 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution

- siva.sai.2020 March 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Well,
With O(1) space and O(N) time complexity.
This means that while we traverse the list, we need to keep track of already visited characters in come convenient way, without using any extra space.

That thing strikes me with hash comparing hash values of both strings.

Let's compute the length of the original string which in this case comes out to be : 13

so place a pointer on mid of the string, i.e on 'g'.

Now compute hash value of string from 'a' till one element less than 'g' == h1

and compute hash value of the other string from 'g'+1 to end of list == h2

if h1 == h2. then palindrome.

hashing mechanism that could be used (position based) : h = 31*h+ascii(char(i));

- abhishek6498@gmail.com October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution looks pretty good.....but here even if you get till the middle node of linked list it may not be the middle of the string.....like it wont be the end of pallindrom string from back side.....please correct me if i m wrong

- xian_7 November 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The hashing mechanism you have suggested doesn't take any positional parameters. If position is not considered your solution is wrong. Also, the second half of the string will be in the reverse order. I am not sure how can you do this algorithm in O(1) space.

- Anjana November 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anjana, We can introduce another parameter like while calculating hash-function by Abhishek.
New function hash-count look like:
h = 31*h*count+ascii(char(i));
for calculating h1 -> increment count from 1 to half of the list i.e. 6 in this case.
And for calculating h2-> decrease count from 6 to 1. This way hash function will start considering order of the character in the string.

- sumeet.kukkar November 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Take nod->data from all the nodes and concatenate in string1, then take two pointer, one
moving forward another backward ,move both pointers one by one from both sides check to see if characters are equal till pointers cross esch other, return true if all charaters match else false...........

- REAMS.AL October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you cannot use any string or any other data structure to store the contents. Need to do this in o(1) space complexity and o(N) time complexity

- vibsy October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is my code to check palindrome
this is just modified version of checking link list palindrom which contain only one character per node

left=head ot LL
right=head of LL
int checkpalindrom(struct nodes **left,struct nodes *right){
    static int a=1,b=0,ri=0;
    int li,r;
    if(right==NULL)
        return 1;
    b=b+1;
    r=checkpalindrom(left,right->next);
    if(r==0)
        return 0;
    li=strlen(right->c);
    
    if(b-a<0)
       return 1;
    while(li>0){
       if(((*left)->c)[ri]!=(right->c)[li-1])
           return 0;
       li--;
       ri++;

       if(((*left)->c)[ri]=='\0'){
           (*left)=(*left)->next;
           a=a+1;
           b=b-1;
           ri=0;
       }
    }
    
    return 1;

}

- dhamu.31954 October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

single list cannot backward

- Anonymous October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

its not going backward
first right pointer reached at end
till now left still pointing to head
after this compare
right->data to left->data
if not same return not a link list not palindrom return 0
if same increment (*left)=(*left)->next
return 1
after return 1 left pointing to 2nd node and right pointing to 2nd from last
and so on till b-a>=0
'b' increment from 1
and ' a' decrement from n(number of nodes in list)
when b-a=0 both left and right pointing to middle node
after this we do not need to do nothing simply return 1
this is the idea

- dhamu.31954 October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

try to run following code u will get your answer

struct nodes {
  char *c;
  struct nodes *next;
};


struct nodes *newnodes(char *c){
      struct nodes *temp=malloc(sizeof(struct nodes));
      temp->c=malloc(sizeof(*c));
      strcpy(temp->c,c);
      temp->next=NULL;
      return temp;
}

void pushs(struct nodes **head,char *c){
      struct nodes *temp=*head;
       if(*head==NULL){
          *head=newnodes(c);
           return;
       }
      *head=newnodes(c);
      (*head)->next=temp;
      return;
}

void prints(struct nodes *head){
     struct nodes *t=head;
     while(t!=NULL){
     printf("%s-->",t->c);
     t=t->next;
     }
     printf("NULL \n");
}


int checkpalindrom(struct nodes **left,struct nodes *right){
    static int a=1,b=0,ri=0;
    int li,r;
    if(right==NULL)
        return 1;
    b=b+1;
    r=checkpalindrom(left,right->next);
    if(r==0)
        return 0;
    li=strlen(right->c);
    if(b-a<0)
       return 1;
    while(li>0){
       if(((*left)->c)[ri]!=(right->c)[li-1])
           return 0;
       li--;
       ri++;
       if(((*left)->c)[ri]=='\0'){
           (*left)=(*left)->next;
           a=a+1;
           b=b-1;
           ri=0;
       }
    }
    return 1;
}



void main(){


struct nodes *head=NULL;
struct nodes *left;
struct nodes *right;

//a-->bcd-->ef-->g-->f-->ed-->c-->ba. 
//a-->bcd-->efgf-->edc-->ba 
pushs(&head,"ba");
pushs(&head,"edc");
pushs(&head,"efgf");
pushs(&head,"bcd");
pushs(&head,"a");
//pushs(&head,"zgy");
//pushs(&head,"ef");
//pushs(&head,"bcd");
//pushs(&head,"a");

left=head;
right=head;

prints(head);
printf("\n%d\n",checkpalindrom(&left,right));
prints(head);
}

- dhamu.31954 October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It seems good but again space O(n) in recursion

- shani October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

with out recursion we have to reverse half list
following isolution is with out recursion

struct nodes *reverse(struct nodes *head){

struct nodes *p=NULL;
struct nodes *c=head;
struct nodes *n=head->next;


while(c!=NULL){
c->next=p;
p=c;
c=n;
if(n!=NULL)
n=n->next;
}
return p;
}


int  checkpalindrom2(struct nodes *head){
   
   char *r;
   struct nodes *t=head;
   struct nodes *s=head;
   struct nodes *f=head;
   int ri,li,a,b;
   while(f->next!=NULL && f->next->next!=NULL){
     s=s->next;
     f=f->next->next;
   }
   s->next=reverse(s->next);
   f=s->next;
   li=0;
   while(f!=NULL){
      ri=strlen(f->c);
      while(ri>0){
         if((t->c)[li]!=(f->c)[ri-1]){
            s->next=reverse(s->next);
            return 0;
         }   
         ri--;
         li++;
         if((t->c)[li]=='\0'){
            t=t->next;  
            li=0;
         }

       }
       f=f->next;
    }
    if((t->c)[li]!='\0'){
     r=malloc(strlen(&(t->c)[li]));
     strcpy(r,&(t->c)[li]);
      li=0;
      ri=strlen(r);
      while(ri>li){
        if(r[li]!=r[ri-1]){
            s->next=reverse(s->next);
            return 0;
         }
         li++;
         ri--;
      }
         

    }
       
    s->next=reverse(s->next);
    return 1;
}

- dhamu.31954 October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

first reached at mid point
then reverse last half
then start comparing from head to last half reversed list
then again reverse last half to retain orignal list
try to run this code u will understand
now space complexity is O(1)
please comment if something seems wrong

- dhamu.31954 October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You cant reach the midpoint without knowing the size of linked list. :(

Probably, a dequeue might help where we fill it up first, and compare it from both the sides by popping one character from both ends.

- Jay October 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

we can reach mid point of linklist without knowing its size
just take two pointer fast and slow
initialy

struct node *mid(struct node *head){
struct node *fast=head
struct node *slow=head

while(fast->next!=NULL && fast->next->next!=NULL){
slow=slow->next;
fast=fast->next->next
}
return slow;
}
fast->next!=NULL condition for LL of odd number of node
fast->nex->nextt!=NULL condition for LL of even number of node
after this slow point to mid point of LL

Jay try to run above code post by me u will find it is working properly

- dhamu.31954 October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Dhamu
Can u please elaborate for this example(5 nodes):
abcdef -> ghihgfed -> c -> b -> a

- shani October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If any node can hold any amount of data, then we could append seconds node's data into first one ...and third node's also in first node...and so on ...we keep appending each node's data into first node.

Finally first node contains a string , which we have to find is a palindrome or not.

- abhishek October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ sK thanks i was also thinking about this case
my iretrative solution wrongly asume that mid point of combined string lies in mid point of LL ,which can,t give correct answer to your case(abcdef -> ghihgfed -> c -> b -> a)
in your example mid point of combined string lies in second node
which is not mid point of list so its does not give correct answer
but my recursive solution will work for this but it takes O(n) space due to recursion
i m try to modifie my iretrative soln to work for all case
thanks sK once again for this example because of this i find error on my code
i will back with update soln

- dhamu.31954 October 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Take @pm solution and convert it to C#. One thing to improve though, it traverse through the full length of the linkedlist to determine Pallindrome - we only have to go through half that many.

using System;
using System.Collections.Generic;
using System.Text;

namespace Pallindrome
{
    class Pallindrome
    {
        static void Main1(string[] args)
        {
            //string s1 = "civic";
            //string s2 = "ciic";
            //string s3 = "xx";
            //string s4 = "x";
            //string s5 = "";
            //string s6 = null;
            //string s7 = "chu";

            //PrintPallindrome(s1);
            //PrintPallindrome(s2);
            //PrintPallindrome(s3);
            //PrintPallindrome(s4);
            //PrintPallindrome(s5);
            //PrintPallindrome(s6);
            //PrintPallindrome(s7);

            int i1 = 1234321;
            int i2 = 1;
            int i3 = 1121;
            PrintPallindrome(i1);
            PrintPallindrome(i2);
            PrintPallindrome(i3);

        }

        static void PrintPallindrome(int i)
        {
            if (IsPallindrome(i))
                Console.WriteLine("yes");
            else
                Console.WriteLine("no");
        }

        static bool IsPallindrome(int n)
        {
            int div = 1;
            int len = 1;
            while (n / div > 10)
            {
                div *= 10;
                len++;
            }

            if (len == 1) return true;

            for (int i = 0, j=len-1; i < j; i ++, j--)
            {
                int l = n / div;
                int r = n % 10;
                if (l != r) return false;
                //n = (n - l * div - r) / 10;
                n = n % div / 10;
                div /= 100;
            }
            return true;

        }

        static void PrintPallindrome(string s)
        {
            if (IsPallindrome(s))
                Console.WriteLine("yes");
            else
                Console.WriteLine("no");
        }

        static bool IsPallindrome(string s)
        {
            if (s == null || s == string.Empty)
                return false;
            int len = s.Length;
            for (int i=0, j=len-1; i<j; i++, j--)
            {
                if (s[i]!=s[j]) return false;                   
            }
            return true;
        }
    }

    class PallindromeLinkedList
    {
        static LinkedListNode<string> head = null;
        static int curIndex = 0;
        static int len;

        static void Main()
        {
            string[] words = { "acb", "bc", "defdc", "bbca" };

            LinkedList<string> ll = new LinkedList<string>(words);
            head = ll.First;
            len = head.Value.Length;

            if (true == IsPallindrome2(head))
                Console.WriteLine("yes");
            else
                Console.WriteLine("no");
        }

        static bool IsPallindrome2(LinkedListNode<string> node)
        {
            int i;
            bool isPal = true;
            if (node.Next != null)
            {
                isPal = IsPallindrome2(node.Next);
            }
            if (isPal)
            {
                for (i = node.Value.Length - 1; i >= 0; i--)
                {
                    char[] arr = node.Value.ToCharArray();
                    if (arr[i] == (char)head.Value.ToCharArray().GetValue(curIndex))
                    {
                        curIndex++;
                        if (curIndex >= len)
                        {
                            curIndex = 0;
                            head = head.Next;
                            if (head!=null) len = head.Value.Length;
                        }
                    }
                    else
                        return false;
                }
                return true;
            }
            return false;
        }
    }
}

- Anonymous April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

first traverse whole list nd calc length of list; after n/2 + 1 element till nth element reverse the list. now u have 2 list , compare both list element one by one

- Manish October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

reversing a linked list can be done quite easily . But here other than reversing the lined list , you also need to reverse the characters inside the node . Doing that also wont be an issue . The problem comes when n/2+1 element will be part of the same node :- For example in a-->bcd-->efgf-->edc-->ba.... After calculating length as 13 , we have to reverse from 7th element , how will you achieve this when you have to reverse some part and leave the remaining part and in the end do not hamper the original structure of the linked list

- vibsy October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isLLPalindrome(LinkedList<String> list){
String s = "";
for(int i=0;i<list.size();i++)
s = s+list.get(i);

return isPalindrome(s);
}

- Andi October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public static boolean isPalindrome(String abc){
int mid = abc.length()/2;int i=-1,j=-1;
if(abc.length()%2==0){
i=mid-1;j=mid;
}else
i=j=mid;


for(; j>=0; i++,j--){
if(abc.charAt(i)==abc.charAt(j))
continue;
else
return false;
}
return true;
}

- Andi October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Constraint is: u have do in O(1) space

- shani October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse LL and get total no of character "n".

Traverse again starting from root and keep pushing the character into stack until ti reaches to size of n/2, escape 1 character if n is odd. and start traversing from this point while each character comes next pop a character from stack and compare it to current character . if it not same return false.
if any one of the stack or LL end return false
otherwise return true(when both stack and LL ends together )

- niraj.nijju October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you have to do inplace and also in o(n) time...

- REAMS.AL October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

whole we need to traverse 2 times, so O(n)
and need stack of size n/2, so O(n) again.

i don't get what you(REAMS.AL) want to say

- niraj.nijju October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

see inplace means you cannot use any other data structure , not even another list, and you have to do this in o(n) time , if you traverse the list again it is ok...but you cannot use any other ds also....now how would you do in o(n) time?

- REAMS.AL October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(1) space and O(n) time solution:

1.) traverse the LL to find the size of all letters(we do not care about the size of the LL).
2.) find the middle charecter MID = n >> 1 - 1.
3.) traverse the LL to find in which node MID character is.
4.) split the node int two parts - 1st part with the characters before mid(included), 2nd with chars after MID.
5.) reverse the second part of the LL (including the 2nd splitted node)
6.) traverse with two pointers 1st from the start, 2nd to the reversed part, untill we hit MID
7.) after 6.) we know if this is palindrom just need to restore the LL if the task require it --> will skip the restoring since it will be easy, just undo what you have done till step 5

- GKalchev October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the 4 point you said to split into two parts?Will you not use one more extra node for this?

- anon October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Using single linked list, while traversing list, each time concatenate the present node key to previous node key. At the end of traversal the last node key contains the whole list characters. then apply your palindrome technique on final node key. traversal will take O(n) complexity and palindrome check will take O(n). So time complexity can be approximate to O(n) and since we didn't use any new keys space complexity remains same i.e O(1). Plese let me know if i am wrong.

- AJIT October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Interesting. Good insight.

- Jay October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No..you are still using O(n) space where n is the size of the whole String and not the size of the linked list..that's why it was mentioned that it cannot be concatenated to a String because if the size(String) >> size(list) then a lot of space is required!

- BoredCoder October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

step 1 recurse through the list and count the total length of string, in case of this example count is 13

step 2 Math.ceil(count/2) = 7 in case of example data

step3 recurse through the list node with two head pointer increment both pointer and reverse the string from position 8 to last so new list will be like
a - bcd - ef - g - ab - c - de - f

step4 recurse through the list with 2 pointers keep 1st at head and move 2nd to 8th position then using runner technique keep matching 1st char to 8th, 2nd to 9th till 6th to 13th all matched return true.

O(n)

- Amitesh Madhur October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Lets take the example as a-->bcd-->efgf-->edc-->ba.....The above approach needs to be updated on cases where the middle element falls in the middle of a given node.

- Anonymous October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

step3: How to reverse the String? We need to reverse the half list and then reverse the node member char arrays in each node..Then, reversing the half-list is not a O(n) operation..Is there any way to reverse a list in O(n)?

- BoredCoder October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Reversing is a list is an O(n) operation BoredCoder

- DashDash March 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

step 1 loop through the list and concat the value of other nodes in first head node.
so the new list will be abcdefgfedcba - null - null - null - null - null - null - null

step 2 apply the general o(n) palindrome finding algo on head node value

- Amitesh Madhur October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package algo.solutions;

import algo.datastructures.LinkedList;

public class PalindromeList {
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList(new char[]{'m', 'a'}, new LinkedList(new char[] {'l','a','y'}, new LinkedList(new char[] {'a', 'l', 'a', 'm'}, null)));
		LinkedList[] l = new LinkedList[1];
		l[0] = list;
		System.out.println(isPalin(list, new int[1], l));
		list = new LinkedList(new char[]{'a'}, new LinkedList(new char[] {'b','c','d'}, new LinkedList(new char[]{'e','f'}, 
				new LinkedList(new char[] {'g'}, new LinkedList(new char[] {'f'}, new LinkedList(new char[] {'e','d'}, new LinkedList(new char[] {'c'}, 
						new LinkedList(new char[]{'b','a'}, null))))))));
		l[0] = list;
		System.out.println(isPalin(list, new int[1], l));
	}
	
	private static boolean isPalin(LinkedList tail, int[] headPt, LinkedList[] head)
	{
		if(tail == null) 
		{
			return true;
		}
		
		boolean ret = true;
		if(tail.next != null) 
		{
			ret = isPalin(tail.next, headPt, head);
		}
		
		if(ret)
		{
			char[] tailchar = (char[])tail.value;
			int tailPt = tailchar.length-1;
			while(true )
			{
				char[] headchar = (char[])head[0].value;
				if(headchar[headPt[0]++] != tailchar[tailPt--]) 
				{
					return false;
				}
				if(headPt[0] == headchar.length) 
				{
					head[0] = head[0].next;
					headPt[0] = 0;
				}
				if(tailPt == -1) 
				{
					break;
				}
			}
		}
		return ret;
	}

}

- sethuraj.32 October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isListPalindrome(SNODE *head, SNODE *tail)
{
int i, j;
int hlen, tlen;
SNODE *p, *r;
p = head;
r = tail;

hlen = strlen(p->str);
tlen = strlen(r->str);
i = 0;
j = tlen-1;

while(p != r)
{
while(i<hlen && j>=0)
{
if(p->str[i] == r->str[j])
{
i++;
j--;
}else
{
return FALSE;
}
}

if(i==hlen)
{
p = p->next;
i = 0;
hlen = strlen(p->str);
}
if(j<0)
{
r = r->pre;
tlen = strlen(r->str);
j = tlen-1;
}
}

return TRUE;

}

- Bin October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have compiled an implementation with some of the ideas already proposed. Basically, I find the middle char of the whole String and then reverse the second part of the list followed by linear char comparisons of the first part and the second reversed parts. I am not sure whether this a true O(n) time complexity since the reversing part takes more and there is no other way to avoid. Space is O(1). I have covered the boundary case where the middle char is positioned either at the beginning of the node char array or in some other position!

private static boolean isPalindrome(ListNode head) {
ListNode curr = head;
int charArrSize = 0;
while (curr != null) {
charArrSize += curr.member.length;
curr = curr.next;
}
int mid = 0;
if (charArrSize % 2 == 0) {
mid = (charArrSize / 2) + 1;
} else {
mid = (charArrSize / 2) + 2;
}
curr = head;
ListNode midNode = null;
ListNode cNode = null;
char midChar = ' ';
int currSize = 0;
int midIdx = 0;
boolean flag = false;
while (curr != null && !flag) {
int size = curr.member.length;
for (int i = 0; i < size; i++) {
currSize++;
if (currSize == mid) {
if (i == 0) {
midNode = curr;
} else {
midNode = curr.next;
}
midChar = curr.member[i];
midIdx = i;
flag = true;
break;
}
}
curr = curr.next;
}
curr = head.next;
cNode = head;
while (curr != midNode) {
curr = curr.next;
cNode = cNode.next;
}
if (midNode == null || midChar == ' ') {
return false;
}
ListNode mNode = reverseMidList(midNode);
cNode.next = mNode;
int i = 0;
int j = 0;
if (midIdx == 0) {
curr = mNode;
i = 0;
} else {
curr = midNode;
i = midIdx;
}
j = curr.member.length - 1;
while (curr != null) {
while (i <= j) {
char temp = curr.member[i];
curr.member[i] = curr.member[j];
curr.member[j] = temp;
i++;
j--;
}
curr = curr.next;
if (curr != null) {
i = 0;
j = curr.member.length - 1;
}
}
char first = head.member[0];
char second = ' ';
ListNode firstNode = head;
ListNode secondNode = null;
if (midIdx == 0) {
secondNode = mNode;
} else {
secondNode = midNode;
}
int firstIdx = 0;
int secondIdx = 0;
int sz = secondNode.member.length;
for (i = 0; i < sz; i++) {
if (secondNode.member[i] == first) {
second = secondNode.member[i];
secondIdx = i;
break;
}
}
if (first != second) {
return false;
}
flag = false;
while (!flag) {
if (secondNode == null) {
flag = true;
continue;
}
if (firstNode.member[firstIdx] != secondNode.member[secondIdx]) {
return false;
}
if (firstIdx < firstNode.member.length - 1) {
firstIdx++;
} else {
firstNode = firstNode.next;
firstIdx = 0;
}
if (secondIdx < secondNode.member.length - 1) {
secondIdx++;
} else {
secondNode = secondNode.next;
secondIdx = 0;
}
}
return true;
}

private static ListNode reverseMidList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode restReverse = reverseMidList(head.next);
ListNode curr = restReverse;
while (curr.next != null) {
curr = curr.next;
}
curr.next = head;
head.next = null;
return restReverse;
}

- BoredCoder October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have implemented the problem in O(number of characters stored in the Linked list).

private static boolean isPalindrome(SingleLinkedList list)
	{
		
		if(list!=null)
		{
			Node fp=list.getHead();
			Node sp=list.getHead();
			while(fp!=null&&sp!=null)
			{
				sp=sp.getNext();
				if(sp!=null)
				{
					sp=sp.getNext();
					if(sp!=null)
					{
						fp=fp.getNext();
					}
				}
			}
			//fp contains last node in the first part
			
			//reverse second part
			
			Node temp=fp.getNext();
			Node prev=null;
			while(temp!=null)
			{
				Node temp1=temp.getNext();
				temp.setNext(prev);
				prev=temp;
				temp=temp1;
				if(temp==null)
				{
					fp.setNext(prev);
				}
			}
			
			Node fp1=list.getHead();
			Node sp1=fp.getNext();
			int fcount=0;
			int scount=-1;
			while(fp1!=null&&sp1!=null)
			{
				char[] fa=fp1.getData().toString().toCharArray();
				char[] sa=sp1.getData().toString().toCharArray();
				if(scount==-1)
				{
					scount=sa.length-1;
				}
				while(fcount<fa.length&&scount>=0)
				{
					if(fa[fcount++]!=sa[scount--])
						return false;
						
				}
				if(fcount<fa.length)
				{
					scount=-1;
					sp1=sp1.getNext();
				}
				else if(scount>=0)
				{
					fcount=0;
					fp1=fp1.getNext();
				}
				else
				{
					scount=-1;
					sp1=sp1.getNext();
					fcount=0;
					fp1=fp1.getNext();
				}
				
			}
			
			
		}
		return true;
	}

- Eswar October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive approach: space O(1) ; time O(n) approx

//Class level variables
int totalLength;
	int reversePtr;
	int forwardPtr;
	int innerFwdPtr;
	int innerRevPtr;
	Node fwdNode;
	boolean isPal = true;


	private void recurseNode(Node n) {

		if (n==null) {
			return;
		}
		
		//assumption node does not have empty string
		totalLength=totalLength+n.value.length();
		recurseNode(n.next) ;
		
		if (!isPal) {
			return;
		}
		
		for(int i=n.value.length()-1;i>=0;i--,innerFwdPtr++,forwardPtr++) {
			
			if(forwardPtr>=totalLength/2) {
				break;
			}
			char ch = n.value.charAt(i);
	
			if (innerFwdPtr>=fwdNode.value.length()) {
				fwdNode=fwdNode.next;
				innerFwdPtr=0;
			}
			
                       //check each char at a time last char vs first char so on ..

			if (ch==fwdNode.value.charAt(innerFwdPtr)) {
			
			}else {
				isPal=false;
				return;
			}
			
		}
		
		return;
		
		


	}

- hack October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Dhamu Bhai is Right it is not going backward

- Rohit Saraf December 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about if we store first half of string and put second half in stack reverse it and comapre

- vikrant January 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) Time, space O(1).
Using the idea of hashing of characters (someone mentioned earlier) to check if the string is a palindrome. Can use SHA1 or MD5 or custom hasing logic.

Thought is -
1) Reverse the linked list in forward walk (interatively). In this step, add each character to the hash. So the hashing would be done on the string "abcdefgfedcba"
2) Now that the linklist is reversed, we can reverse this reversed linked list back to the original list. During this step, we will hash the characters from last to first. For e.g.: for the 2nd node in original list "bcd", we should hash characters in the reverse order (ie. "dcb") during this step.
3) f the string is a palindrome, forward walk hash value and backward walk hash value will be same. Return true if so. Else false.

- jtr.hkcr March 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a recursive traversal of the list and check if nth char from beginning is equal to nth char from the end. Something like below. I haven't verified it

bool is_palind = true;
node *head;
int index=0;

char
get_next() {
  if(!head) {
    return '\0';
  }
  if(index == head->data.size()) {
    /* Done with this node's data */
     head = head->next;
     index = 0;
     return head->data[index++];
  } else {
    /* return the next char */
    return head->data[index++];
  }  
}

void
recurse(node *p) {
  if(p == NULL) {
    return 0;
    string front = head->data;
  } else {
    int back_index = recurse(p->next);
    string back_data = p->data;
    int n = back_data.size();
    for(int i=0; i<back_data.size(); i++) {
      /* CHeck if n-th char from last is same as nth char from beginning */
      if(x[n-i-1] != get_next()) {
        is_palind = false;
      }    
      back_index++;
    }
    return back_index;
  }
}

bool
is_list_palindrome(node *ip) {
  head = ip;
  recurse(ip);
  retutn is_palid;
}

struct node {
  public:
    string data;
    node* next;
};

- Anonymous March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do a recursive traversal of the list and check if nth char from beginning is equal to nth char from the end. Something like below. I haven't verified it


bool is_palind = true;
node *head;
int index=0;

char
get_next() {
if(!head) {
return '\0';
}
if(index == head->data.size()) {
/* Done with this node's data */
head = head->next;
index = 0;
return head->data[index++];
} else {
/* return the next char */
return head->data[index++];
}
}

void
recurse(node *p) {
if(p == NULL) {
return 0;
string front = head->data;
} else {
int back_index = recurse(p->next);
string back_data = p->data;
int n = back_data.size();
for(int i=0; i<back_data.size(); i++) {
/* CHeck if n-th char from last is same as nth char from beginning */
if(x[n-i-1] != get_next()) {
is_palind = false;
}
back_index++;
}
return back_index;
}
}

bool
is_list_palindrome(node *ip) {
head = ip;
recurse(ip);
retutn is_palid;
}

struct node {
public:
string data;
node* next;
};

- prakash1529 March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Approach:

1. By using Array:
-Find the total no. of char by node traversal in List= length
-Have an Array and put length/2 char from List [first char to length/2 char]
-now start traversing from (length-length/2)th char and compare with Array's last char
-in case match move one more char in node or next node in case previous char was the last char in node and compare Array's second last char..... continue till end

2. The great Recursion:
-initialize a global pointer *ptr with head of list
-go till the end in recursive function which returns an object of Class ReturnValue {Node* node;int index}
[write code in recursive fun after calling recursive method ]
-Once reached to the end process last node(got through recursion loop) and *ptr node
-Compare last (got through recursion loop) node's char set to *ptr node char set
-Go to the last (got through recursion loop) node's last char and match with *ptr node's first char
-in case match found
-check for ptr node's next char to last (got through recursion loop) node's second last char
-in case ptr node had only one char move global ptr to next node [ptr=ptr->next]
-in case last (got through recursion loop) node had only one char then exit from last recursive function and return ptr node and index of char in ptr node keeping in a object of Return Value.
-now last recursive fun will be exited and recursive fun will point to second last node of the list
-perform same operation.

- PKT March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

edit: do not skip N/2 nodes, skip nodes until skipped nodes contain half of the characters (which may not necessarily be N/2)

- chatbot March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Pkt can you post the code in java for array method

- dum March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.List;

/**
*
* @author Ralph
*/
public class Palindrome {
public boolean isPalindrome(List<String> list) {
String forward = "";
String backward = "";

for (int i = 0; i < list.size(); i++) {
forward = forward + list.get(i);
backward = backward + reverse(list.get((list.size() - 1 - i)));
}

if (forward.equalsIgnoreCase(backward)) {
return true;
}

return false;
}

public String reverse(String string) {
String reverse = "";

for (int i = (string.length() - 1); i >=0; i--) {
reverse = reverse + string.charAt(i);
}

return reverse;
}

public static void main(String [] args) {
List<String> list = new LinkedList<String>();
list.add("re");
list.add("vi");
list.add("ver");

Palindrome p = new Palindrome();
System.out.println(p.isPalindrome(list));
}
}

- Ralph March 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You could also take the list, break all the strings into chars, push them onto the stack, then pop them off and compare the 2 strings.

- Ralph March 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool IsPalindrome(node *head, node *tail)
{
while(head<tail)
{
if( head.data==tail.data)
{
head=head->next;
tail= tail->prev;
}
return false;
}
return true;
}

- kalpana July 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Use Doubly Circular linked list. Traverse with one pointer from front and one from back

- Anonymous October 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Idiot !

- LoserWeeder October 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wow! why din't i think of this.

- Tik October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More