Amazon Interview Question
Country: India
Interview Type: Written Test
good approach!.. but left(1 traversal) and right pointers(2 traversal.. totally 3 traversal) are traversing whole list... stop your traversing when left and right pointers point to the same node or right pointer is next to the left ..
Good approach.
The best way to traverse a linked list in reverse order is to put the items in a stack while traversing list in normal order. Once all the items are on stack then whenever we pop the items from stack we get the linked list items in reverse. Here John has used the JVM functionality to store recursive function data in a stack.
Using recursion is considered using extra space. No, the proper approach to do this is to find the middle node, reverse the linked list in place from the middle to the end, and traverse from the beginning and the end simultaneously, comparing characters that occur. Then you repair the original input by again reversing from the middle node to the end.
Yes I thought about both the approach.
But this approach internally build a stack. Not sure but explicitly we are not declaring any variable/stack, so its fine according to the question.
1 suggestion why don't use static node *left instead of node **left ?
No it's not fine according to the question. Extra space is extra space, whether it's declared implicitly or explicitly.
Keep another node pointer. While till the middle, keep adding to the head of the other pointer. After middle, start the comparison. But the problem here is that the list will be split since we can't have additional memory. After the algo is done, we need to merge the list back.
1、 find the middle node of LL to divide LL in two half lists.
2、reverse the nodes of the list before the middle node(time O(N) space O(1)).then we get two lists
3、test if these two lists are the same
Not bad if you only care about the complexities but having an extra traversal would be time consuming if you have a huge data stored as a linked list.
That's the way to do it.
I would add 4) Reverse the nodes before the middle node again to repair the original input.
You also need to be careful how you treat the middle node if there's an odd vs. if there's an even number of nodes.
@Vick: it's not possible to do this with only one pass. How would you do it? If you put entries into a stack and then use that, you are 1) using extra space; and 2) still making a second pass, through the stack instead of the linked list in this case.
i wld like to include this is a link list
applying reversal to first half would be a mess.....
Does anyone tell me the reason for reversing the first half instead of traversing with two pointers(one from the beginning and one from the middle) simultaneously?
Well, that's a logical approach and meets the space constraint (hope you are suggesting using slow and fast pointers to identify the middle of the LL). Just would like to add some notes:
1. At the end, the reversed part of the LL would most probably need to be reverted;
2. When finding the middle, make sure that you take care of both cases when the LL may have either odd or even count of elements;
public static void main(String [] args){
LinkedList<String> ll = new LinkedList<String>();
ll.addAll(Arrays.asList("M A L A Y A L A M".split(" ")));
System.out.println(ll);
Iterator<String> forward = ll.iterator();
Iterator<String> reverse = ll.descendingIterator();
System.out.println(isPalindrome(forward, reverse, ll.size()/2));
}
public static Boolean isPalindrome(Iterator<String> forward, Iterator<String> reverse, int limit){
int count = 0;
System.out.println(limit);
while(forward.hasNext() && reverse.hasNext() && count <=limit){
System.out.println("Processed\n");
count++;
if(!forward.next().toString().equals(reverse.next().toString())){
return false;
}
}
return true;
}
can be calculated in two parse..
for the first parse.....we find the no. of elements
if even first n/2 int are inserted in stack
and for next n/2 they are popped if same element is encountered else not a palindrom
for odd n/2 floor are inserted
and n+1/2 element is ignored and same as for even popping starts for same element
else not a palindrom
Lets try this
Time: worst case 3*n, O(n)
Space: O(1)
void linkedList::reverse() {
int i;
int len = length(); //order n, 1 depends on implementation
node *l = getNodeAtIndex(len - 1); //order n
for(i = 0 ; i < len - 1 ; i++)
insertAtPtr(l,removeAtIndex(0)); //order n
}
int GetLength(Node *head)
{
int count = 0;
while(head != NULL)
{
count ++;
head = head->next;
}
return count;
}
bool IsPalindrome(Node *root, Node *current, int len, int cl)
{
bool b = true;
if (len > 0 && cl != len/2 + 1)
{
b = IsPalindrome(root, current->next, len, cl + 1);
}
while (cl-- > 0) root = root->next;
bool b1 = root->c == current->c;
return b1 && b;
}
There is another approach to it. Keep another node pointer. While till the middle, keep adding to the head of the other pointer. After middle, start the comparison. But the problem here is that the list will be split since we can't have additional memory. After the algo is done, we need to merge the list back.
LinkedList<String> ll = new LinkedList<String>();
ll.addAll(Arrays.asList("M A L A Y A L A M".split(" ")));
boolean noPalind = false;
for(int i=0,j=ll.size()-1; i<(ll.size()/2)+1 || j>((ll.size()/2)+1); i++, j--)
{
if(!(ll.get(i).equals(ll.get(j))))
{
noPalind = true;
break;
}
}
System.out.println(!noPalind);
how about this one:
1. Start from the beginning, Push all charters to the stack
2. While stack is not empty, traverse the list again and compare the characters.
Runtime is O(n) in success case where n is number of characters.
Also, small optimization can be done where push last half of he list to the stack in step 1 above.
Space requirement is bit more. :)
A recursive approach.
call isPalindrome(&root,root);
- john.matheus July 16, 2012bool isPalindrome(struct node **left, struct node *right) { /* stop recursion here */ if (!right) return true; /* If sub-list is not palindrome then no need to check for current left and right, return false */ bool isp = isPalindrome(left, right->next); if (isp == false) return false; /* Check values at current left and right */ bool isp1 = (right->data == (*left)->data); /* Move left to next node */ *left = (*left)->next; /* save next pointer */ return isp1; }