Amazon Interview Question Software Engineer / Developers
Team: Development
Country: India
Interview Type: In-Person
Here is my code
public boolean isPalindrome(LinkedListNode head)
{
if(head == null)
return false;
Stack<Integer> stack = new Stack<Integer>();
LinkedListNode slow = head;
LinkedListNode fast = head;
stack.add(slow.value);
int i = 0;
while(fast.next != null)
{
if(i == 0)
{
fast = fast.next;
i = 1;
}
else if(i == 1)
{
slow = slow.next;
fast = fast.next;
stack.add(slow.value);
i = 0;
}
}
System.out.println(slow.value);
if(stack.size() % 2 == 0)
{
stack.pop();
}
slow = slow.next;
while(!stack.isEmpty() && slow != null)
{
int val = stack.pop();
if(slow == null || val != slow.value)
return false;
slow = slow.next;
}
return true;
}
the algorithm is great, I put more compact java code below:
public static boolean isPalindrome(LinkedList<Character> input) {
if (input == null || input.size() == 0)
return false;
Iterator<Character> fast = input.iterator();
Iterator<Character> slow = input.iterator();
Stack<Character> firstHalf = new Stack<Character>();
int i =0;
while(fast.hasNext()){
fast.next();
if((i & 1) == 0)
firstHalf.push(slow.next());
i++;
}
if ((input.size() & 1) != 0){
firstHalf.pop();
}
while(slow.hasNext()){
if(!firstHalf.pop().equals(slow.next())){
return false;
}
}
return true;
}
What about this implementation in place.
We reverse the sencond half of the list and compare half of the list.
I think It more efficient.
IF WE have to leave the linked list as Its initial state, then we can just reverse the half again.
public static boolean isPalindrome(LNode node){
int size = size(node);
int middle = size/2;
if((size % 2) != 0) middle++; // special clase for odd linked list size
LNode current = node;
LNode runner = node;
int counter = 0;
while(counter < middle-1){
runner = runner.next;
counter++;
}
runner.next = reverse(runner.next);
runner = runner.next;
while(runner != null){
if(runner.value != current.value){
return false;
}
runner = runner.next;
current = current.next;
}
return true;
}
public static LNode reverse(LNode node){
LNode current = node;
LNode next = null;
LNode prev = null;
while(current != null){
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
Use slow/fast pointers to reach the middle node. While doing this reverse the first half of the linked list inplace. Now you have two linked lists -> compare node by node. While doing this reverse the first half again.
p = q = head;
prev = NULL;
while( q != NULL )
{
q = q->next;
if( q->next != NULL )
q = q->next;
break;
// reverse the linked list till p - middle node
temp = p->next;
p->next = prev;
prev = p;
p = temp;
}
forward = temp;
// move p one step backward for linked lists with odd number of elements
if( q == NULL )
temp = p->next;
p->next = forward;
p = temp;
prev = p;
else
prev = temp;
backward = p;
bool palindrome = true;
while( backward != NULL )
{
if( forward->data != backward->data )
palindrome = false; //don't return yet, you have to reverse the list fully
// reverse first half of the linked list again
forward = forward->next;
temp = backward;
backward->next = prev;
backward = temp;
}
return palindrome;
bool chkPalindrom(Node root,Queue queue){
if(root==null)
return true;
queue.add(root.data)
if(!chkPalindrom(root.next,queue))
return false;
if(queue.pop()==root.data)
return true;
}
I think this would take as much time as reversing. Is this too simple of an answer?
public static boolean isPalindrome( LinkedList list )
{
int n = list.size();
boolean state = false;
for (int i = 1; i <= n; i++, n--)
{
if ( list.get(i) == list.get(n) )
state = true;
else
{
state = false;
break;
}
}
return state;
}
simple Solution in O(n) using recursion
private static boolean isPalindrome(Node<Character> startNode,
StringBuffer fwdStr, StringBuffer revStr) {
fwdStr.append(startNode.data);
if (startNode.next != null) {
isPalindrome(startNode.next, fwdStr, revStr);
}
revStr.append(startNode.data);
return fwdStr.toString().equals(revStr.toString());
}
We can simply use an equation...
ax^n + b x^n-1 + C x^n-2 +..............+ Z X^0
a, b, c represents ascii value for each char in the linked list..
Take any arbitrary value for X,
N represents LinkedList lenght -1
Traverse the list from left to right , and right to left and if the sum is same in both the cases.
They are palindrome.
no need of reversing the list.
first calculate a[0]*x^0+a[1]*x^1......+a[n-1]*x^(n-1).
where a[i] means ascii value of character in the list present at position i.
from this you will know n.
now calculate a[0]*x^(n-1)+a[1]*x^(n-2)+......a[n-2]*x^1+a[n-1]*a^0
if both values are same then given list is pallindrome.
Use the concept of slow and fast pointers
- Hello world February 27, 2012With one small change while traversing through the list with the slow pointer load
the values onto a stack
Now after you reach the middle from step 1 traverse the
remaining list with the slow pointer and pop each value from the stack
At each point these values should match if not return false or at the end return true