Amazon Interview Question
Software Engineer / DevelopersTeam: RCX
Country: India
Interview Type: In-Person
The following algorithm will have O(n) time and O(n) space complexity...
1) Start from the first node and add every element to a stack.
2) Once the stack is created, again start from the beginning of the LL and compare top of stack with the element in the LL.
3) The moment you find a mismatch, exit the loop and report that it is not a palindrome. If the stack gets emptied, it indeed is a palindrome.
Having given this algorithm, I would like to know if there is a better approach than O(n). Thanks :)
I will put all the elements in the LL in a String. After that I will check if that String is palindrome by either :
a) reversing the string and comparing
b) checking it myself for example:
public static boolean isPalindrome(char[] data, int start, int end) {
int len = (end - start) + 1;
for (int cursor = start; cursor < start + (len / 2); cursor++) {
if (data[cursor] != data[end - cursor + start])
return false;
}
return true;
}
bool ispalin(node** head,node* last)
{
if(last->next==NULL) return true;
cout<<"!!! comparing "<<(*head)->ch<<" "<<last->ch<<" "<<last->next<<" "<<(*head)->next<<" "<<head<<" "<<last<<endl;
bool temp = (ispalin(head,last->next) && ((*head)->ch == last->ch));
cout<<"comparing "<<(*head)->ch<<" "<<last->ch<<" "<<last->next<<" "<<(*head)->next<<" "<<head<<" "<<last<<endl;
(*head)=(*head)->next;
return temp;
}
cout<<ispalin(&head,temp)<<endl;;
1)Take two pointers
2) Traverse the first pointer to the end of the LL
3) Now increment the second pointer by 1 and decrement the first pointer by 1.
4) Compare their values in the position.
5) If there is a mismatch before the pointers intercept then its not a palindrome.
so you require n+n/2 passes .. hence the complxity would be O(n)
geeksforgeeks.org/archives/1072
- pk January 05, 2012