Amazon Interview Question for Software Engineer / Developers






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

Copied from Geeksforgeeks

Here is the solution.

Algorithm:

1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the
second half again and attaching it back to the first half

Implementation:

/* Program to check if a linked list is palindrome */
#include<stdio.h>
#include<stdlib.h>
 
/* Link list node */
struct node
{
    char data;
    struct node* next;
};
 
void reverse(struct node**);
int compareLists(struct node*, struct node *);
 
/* Function to check if given linked list is
  palindrome or not */
int isPalindrome(struct node *head)
{
   struct node *slow_ptr = head;
   struct node *fast_ptr = head;
   struct node *second_half;
   struct node *prev_of_slow_ptr = head;
   char res;
 
   if(head!=NULL)
   {
       /* Get the middle of the list. Move slow_ptr by 1
         and fast_ptrr by 2, slow_ptr will have the |_n/2_|th
         node */
       while((fast_ptr->next)!=NULL &&
               (fast_ptr->next->next)!=NULL)
       {
          fast_ptr = fast_ptr->next->next; 
 
          /*We need previous of the slow_ptr for
           linked lists  with odd elements */
          prev_of_slow_ptr = slow_ptr;
          slow_ptr = slow_ptr->next;
       }
 
       /* Case where we have even no of elements */
       if(fast_ptr->next != NULL)
       {
         second_half = slow_ptr->next;
         reverse(&second_half);
         slow_ptr->next = NULL;
         res = compareLists(head, second_half);
 
         /*construct the original list back*/
         reverse(&second_half);
         slow_ptr->next = second_half;
       }
 
       /* Case where we have odd no. of elements. Neither first
          nor second list should have the middle element */
       else
       {
          second_half = slow_ptr->next;
          prev_of_slow_ptr->next = NULL;
          reverse(&second_half);
          res = compareLists(head, second_half);
 
         /*construct the original list back*/
         reverse(&second_half);
         prev_of_slow_ptr->next = slow_ptr;
         slow_ptr->next = second_half;
       }
 
       return res;
   }
}
 
/* Function to reverse the linked list  Note that this
    function may change the head */
void reverse(struct node** head_ref)
{
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    while (current != NULL)
    {
        next  = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head_ref = prev;
}
 
/* Function to check if two input lists have same data*/
int compareLists(struct node* head1, struct node *head2)
{
    struct node* temp1 = head1;
    struct node* temp2 = head2;   
 
    while(temp1 && temp2)
    {
       if(temp1->data == temp2->data)
       {
          temp1 = temp1->next;
          temp2 = temp2->next;
       }
       else return -1;
    }
 
    /* Both are empty reurn 1*/
    if(temp1 == NULL && temp2 == NULL)
       return 1;   
 
    /* Will reach here when one is NULL
      and other is not */
    return -1;
}   
 
/* Push a node to linked list. Note that this function
  changes the head */
void push(struct node** head_ref, char new_data)
{
    /* allocate node */
    struct node* new_node =
            (struct node*) malloc(sizeof(struct node));
 
    /* put in the data  */
    new_node->data  = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);   
 
    /* move the head to pochar to the new node */
    (*head_ref)    = new_node;
}
 
/* Drier program to test above function*/
int main()
{
    /* Start with the empty list */
    struct node* head = NULL;
 
     push(&head, 'p');
     push(&head, 'e');
     push(&head, 'e');
     push(&head, 'p');              
 
     /* p->e->e->p */
     if(isPalindrome(head) == 1)
       printf("Linked list is Palindrome");
     else
       printf("Linked list is not Palindrome");    
 
     getchar();
     return 0;
}

Time Complexity O(n)
Space Complexity O(1)

- Initrd March 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n/2) for find middle,O(n/2) for reversing 2nd half,O(n/2) for comparison,O(n/2) for again reverse 2nd half..

so n/2+n/2+n/2+n/2=2n=O(n)

linear time solution,no extra space...

good solution...

- Anonymous September 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

bool helpFunction(Node **head , Node *tail)
{
	Node *t = tail;
	if(t==null)
	{
		return true;
	}
	
	if(helpFunction(head , t->next))
	{
		Node * h = *head;
		if(h->Data == t->Data)
		{
			(*head) = (*head)->next; 
			return true;
		}	
	}

	return false;


}
bool IsPalidrome(Node * head)
{
	Node * head1 = head;
	Node * tail = head->next;
	
	return helpFunction(&head,tail);
}

- xyz August 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool find(node* node, int i) {
   static node* head = node;
   static int ispalindrome = true;

   if (node) {
      ispalindrome = find(node->next);

      if (ispalindrome && (node->data != head->data)) {
         ispalindrome = false;
      }

      head = head->next;
   }

   return ispalindrome;
}

- Anonymous October 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here you make use of O(N) space in stack, due to activation record space coz of recursion. Space used wld be equivalent to have a local O(N) array or stack(not on heap).

- Anonymous October 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

http://geeksforgeeks.org/?p=1072

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

Hi, I think, it always prints "Linked list is Palindrome". This is because,
1). we return either '-1' or '1' from 'compareLists'.
2). The return value is assigned to 'res' which in turn returned to the 'main' function.
3). The condition 'if(isPalindrome(head))' is always true for any input.

Returning '0' may solve the problem.

Regards,
Hari.

- Hari Prasad Perabattula October 22, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node IsPallin(Node current, Node head)
{
if( head == null) return null;

if(current->next != null) {
 head = IsPallin(current->next, head)
}
if(current->info != head->info) return null;

return head->next ?? head;

}

One can further optimize by adding a parameter to track the comparison and make it halved.

- Recursion October 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can be done in o(n)time. halve it; revert first half;compare;revert first half again.

- langzi October 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution.

- Erik October 19, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about odd number of items

- new_bee February 15, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) approach: a bit messy though
#1. Find the length of the list.
#2. Assuming the size is even, keep putting/pushing all the elements from the beginning till the mid to a stack[mimic a stack using an array]. Reverse the stack. If you are using array then you just have to traverse it in the reverse order, thats it.
#3. Now Pop out one element and compare that with NexttoMid element in the list. Keep doing this in a loop till,

# you reach end, in that case its indeed a palindrome. 
  # you find a mismatch, bail out, declaring that the list is not a palindrome.

# Done !
Space=O(n/2)= O(n)
Time=O(n)

- P October 19, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Reverse the first half of the list in O(n).
Verify for palindrome.
Reverse the first half again.

Got the same question in Yahoo!

- Thiyaneshwaran S October 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please provide more details . Unable to understand.

- Anonymous December 17, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algorithm:

1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the
second half again and attaching it back to the first half

- Anonymous December 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Topic starter:
u should have said singly linked list.
with dll its easy.

- Nunnu December 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simpler linear solution is as follows:

Node* pTempHead = head;
while (head != NULL)
{
if(head->next != NULL && head->next->next-> != NULL)
   {
     if (head->value == head->next->next->value)
         {
              pBeginPoint = head;
              pTrailingEnd = head->next->next;
              break;
          }
         head = head->next;
   }
}
head = pBegnPoint;

if (pTrailingEnd != NULL)
{
  while (head != pBeginPoint)
    {
       if (pTrailingEnd->Next != NULL)
        {
          if (head->value == pTrailingEnd->next->value)
          {
             pTrailingEnd = pTrailingEnd->Next;
            head = head->Next;
           }
        }
    }
}

Need to check for error logic and all ...

Algorithm:
- In LL, find the pivotal point in the LL, where one before and one after the pivotal point are equal
- Then start from the head of the LL until one before pivotal point, and one after the pivotal point and make sure the nodes are equal 
- This is more efficient than recrusion or reversing LL

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

your logic is wrong. can u write full working code for the same

- Anonymous July 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not more efficient. If you have a lot of small palindromes embedded in the list (worst-case), you'll be O(n^2).

- JeffD September 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

singly linke list palindrome...no big deal..just use recursion
first find the middle of the list..using one fast and slow iterators..
then traverse second half of the list in reverse order while first half in forward..
compare values
use a global variable flag to save the value of comparison.
but once the its no longer palindrome..we can't break the recursive calls..
so glabal variable flagchanged is used to keep track of the flag var.

int flag =0;
int changedflag =0;
node* reverse(node * n1,node* n2)
{
if(n1==NULL)
return n2;
else
{ node *temp = reverse(n1->next,n2);
if(temp->data == n1->data)
{
if(changedflag==0)
flag=1;
}
else
{
if(changedflag==0)
{ flag=0;
changedflag=1;
}

}
return n2->next;

}
}

- Reshmi January 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sorry!! indentation went wrong due to copy pasting from editor

int flag =0;
int changedflag =0;
node* reverse(node * n1,node* n2)
{
if(n1==NULL)
return n2;
else
{ node *temp = reverse(n1->next,n2);
if(temp->data == n1->data)
{
if(changedflag==0)
flag=1;
}
else
{
if(changedflag==0)
{ flag=0;
changedflag=1;
}

}
return n2->next;

}
}

- Anonymous January 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this:

If extra O(n) space is allowed then. Use 1 stack and 1 queue.

put first half in queue. Second half in stack.
Then pop from stack and dequeue from list and compare.
If length if list is even both will be empty in the end.
Else the middle element will remain, in the stack or queue (your choice).

- alwaysalearner February 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

best wud be to take two pointers...fast and slow.....find the middle point. now take a third global pointer point it to head...use recursion(NO NEED TO REVERSE THE LIST)

node * global_head;//points to original head

int main()
{
node *head, *fp,*sp;//given head, fastpointer, slowpointer
fp=sp=global_head=head;
if(head==NULL || head->next==NULL||(head->next->next==NULL&&head->val==head->next->val))
     {
     cout<<"yes palindrome";
     exit(0);
     }

while(fp==NULL||fp->next==NULL)
       {
       fp=fp->next->next; sp=sp->next;
       }
 check(sp->next);
return 0;
}

void check(node *p)
{
if (p==NULL) return;
check(p->next);
if(global_head->val!=p->head) 
    { 
    cout<<"NOT A PALINDROME";
    exit(0);
    }
global_head=global_head->next;
}

- utscool February 24, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why not this:

String actual;
String reverse;
Function(Node current)
{ 
actual = actual + current.value;
if(current.next != null)
  Function(current.next)
reverse = reverse + current.value;
}

if(actual == reverse)
  palindrome = true;
else
 palindrome = false;

- shiva March 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ptth://********************geeksforgeeks.org/?p=1072

Remove stars and reverse the "ptth" from the above written link,

- manan.brahma June 11, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Program to check if a linked list is palindrome */
#include<stdio.h>
#include<stdlib.h>
#define bool int

/* Link list node */
struct node
{
char data;
struct node* next;
};

void reverse(struct node**);
bool compareLists(struct node*, struct node *);

/* Function to check if given linked list is
palindrome or not */
bool isPalindrome(struct node *head)
{
struct node *slow_ptr = head;
struct node *fast_ptr = head;
struct node *second_half;
struct node *prev_of_slow_ptr = head;
char res;

if(head!=NULL)
{
/* Get the middle of the list. Move slow_ptr by 1
and fast_ptrr by 2, slow_ptr will have the |_n/2_|th
node */
while((fast_ptr->next)!=NULL &&
(fast_ptr->next->next)!=NULL)
{
fast_ptr = fast_ptr->next->next;

/*We need previous of the slow_ptr for
linked lists with odd elements */
prev_of_slow_ptr = slow_ptr;
slow_ptr = slow_ptr->next;
}

/* Case where we have even no of elements */
if(fast_ptr->next != NULL)
{
second_half = slow_ptr->next;
reverse(&second_half);
slow_ptr->next = NULL;
res = compareLists(head, second_half);

/*construct the original list back*/
reverse(&second_half);
slow_ptr->next = second_half;
}

/* Case where we have odd no. of elements. Neither first
nor second list should have the middle element */
else
{
second_half = slow_ptr->next;
prev_of_slow_ptr->next = NULL;
reverse(&second_half);
res = compareLists(head, second_half);

/*construct the original list back*/
reverse(&second_half);
prev_of_slow_ptr->next = slow_ptr;
slow_ptr->next = second_half;
}

return res;
}
}

/* Function to reverse the linked list Note that this
function may change the head */
void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}

/* Function to check if two input lists have same data*/
int compareLists(struct node* head1, struct node *head2)
{
struct node* temp1 = head1;
struct node* temp2 = head2;

while(temp1 && temp2)
{
if(temp1->data == temp2->data)
{
temp1 = temp1->next;
temp2 = temp2->next;
}
else return 0;
}

/* Both are empty reurn 1*/
if(temp1 == NULL && temp2 == NULL)
return 1;

/* Will reach here when one is NULL
and other is not */
return 0;
}

/* Push a node to linked list. Note that this function
changes the head */
void push(struct node** head_ref, char new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to pochar to the new node */
(*head_ref) = new_node;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 'p');
push(&head, 'e');
push(&head, 'e');
push(&head, 'p');

/* p->e->e->p */
if(isPalindrome(head) == 1)
printf("Linked list is Palindrome");
else
printf("Linked list is not Palindrome");

getchar();
return 0;
}

- Vishwaatma June 27, 2010 | Flag Reply


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