Amazon Interview Question
Software Development ManagersCountry: India
Interview Type: Phone Interview
O(N) time, O(1) space: recursive
1. Traverse till middle
2. One pointer at start, second half of the string will recurse till end
3. Keep matching, at first unmatch, break and report false
4. Return true if all matches
(Somewhat tricky to write but optimal)
O(N) time O(1) space:
1. Find length (if not given)
2. Traverse till middle of list
3. Reverse second half of list
4. Keep two pointers, one at start, other at middle
5. Keep comparing until you match them all (i.e., reach till end of second half)
6. If at any point characters don't match break and report false, else true
7. Reverse the second half again to restore or if there is a specification that you can't modify the input.
O(N) time, O(N) space:
If you are asked not to reverse the list then following can be brute force idea:
1. Traverse the list once
2. Make string out of it
3. Check if the string is palindrome
We can do it even without string variable:
1). Find the middle element, using node->next and node->next->next, and
simultaneously find the length of the list.
2). If the length is odd, delete the middle element.
3). Reverse the second half of the list (recursive method).
4). Compare the first and the second half of the list.
Working Correct
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
class Node{
public:
char name;
Node *next;
Node(char n){
name=n;
next=NULL;
}
};
class sll{
public:
Node *head;
sll(){
head=NULL;
}
void insert(char name){
Node *n=new Node(name);
Node *temp=head;
if(head==NULL){head=n;return;}
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=n;
}
void display(){
Node *temp=head;
while(temp!=NULL){
cout<<temp->name<<"-->";
temp=temp->next;
}
}
};
void func(Node *ptr1,Node *ptr2){
if(ptr2==NULL) return;
func(ptr1,ptr2->next);
if(ptr1->name!=ptr2->name) {cout<<ptr1->name<<" not equals to "<<ptr2->name<<endl;
cout<<"Not a palindrome\n";
system("pause");
exit(1);}
*ptr1=*ptr1->next;
}
void checkPalindrome(sll list){
Node *ptr1, *ptr2;
ptr1=ptr2=list.head;
while(ptr1!=NULL&&ptr1->next!=NULL){
ptr1=ptr1->next->next;
ptr2=ptr2->next;
}
if(ptr2!=NULL){
func(list.head,ptr2);
}
}
int main(){
sll list;
string str;
cout<<"Enter a string to check for palindrome: ";
cin>>str;
for(int i=0;i<str.length();i++){
list.insert(str[i]);
}
checkPalindrome(list);
cout<<"Palindrome\n";
system("pause");
return 0;
}
oopas my soltion doesn't quite work. Correction to my previous post. Some pallidrome's have 1 character that is not repeated like "radar".
public String adjustString(String nodeString, String s) {
if (s.indexOf(nodeString) == -1) {
s += nodeString;
} else {
s = s.replaceAll(nodeString, "");
}
return s;
}
public boolean isPallindrome(Node head) {
Node n = head;
String s = "";
while (n.next != null) {
adjustString(n.data, s);
n = n.next;
}
adjustString(n.data, s);
return (s.length() <= 1);
}
Declare a linked list of type string
linkedlist<String>l1 = new linkedlist<string>();
int size =l1.size();
boolean res = boolean pali( LinkedList l1); //recursive function call;
if (res ==1)
sysout("pali");
else
sysout(not a pali");
boolean pali(LinkedList L1)
{
Int i,j,size;
for (i = size; i>=0;i++) //Pointing to the last node of the list
{
for (j=0;j<=size;j++)//Pointing to the first node of the list
{
if (l1.get(i) == l1.get(j))// comparison of last node with first node
return 1;
Else
return 0;
}
}
}
This routine doesn't use a string. It traverses the list using 2 pointers - one fast (2x) and one slow to find the middle of the list. Once the middle is found, the middle pointer continues recursively to the end of the list and then each char is compared as the recursive stack unwinds.
{
struct llist {
char c;
struct llist *next;
};
typedef struct llist List;
int isPali(List *list)
{
List *sp = list;
List *fp = list;
List *bp = list;
if (list == NULL) return 0;
while (fp != NULL)
{
sp = sp->next;
fp = fp->next;
if (fp != NULL) fp = fp->next;
}
return pali(&bp, sp);
}
int pali(List **first, List *second)
{
int t;
if (second == NULL) return 1;
t = pali(first, second->next);
if (t == 0) return 0;
if ((*first)->c != second->c) return 0;
*first = (*first)->next;
return 1;
}
}
string str = "";
string copyLL(Node *start)
{
if(start == null) return str;
str = concat(str,start.value);
start = start->Next;
copyLL(start);
}
isPalindrome(string str)
{
int len = len(str);
int i, j;
int count = 0;
for (i = 0, j = len-1; i <(len/2); i++, j--)
if(str[i] == str[j])
count = 1;
if(count != 0) return true;
else return false;
}
}
Its simple..
- Pappu Pager January 17, 20121) find the middle element of list using slow/fast pointer approach.
2) when u r traversing till middle, keep writing all chars in a temporary string variable
3) when u reach middle, read the temp string backwards and compare that with the next nodes in the list.. :))