Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
whats the solution on cracking inteview. i think the space overhead of STACK solution is more due to mantaining a stack
How to just add "half the elements of the total elemnts travesrsed so far" into a stack?
From my understanding, a more simple way is adding all elements into an array until the end of the list, then traverse half of this array and compare a[i] with a[n-i-1], break the loop if they are not equal, and we can conclude this list is not palindrome.
Additionally, traversing list could cost more time than traversing an array.
Agree?
I implement you idea by c++, only for using stack, and if it does not correspond to the form, you can use c implement a stack. here is the code:
#include<iostream>
#include<stack>
using namespace std;
typedef struct node{
int data;
struct node *next;
}LinkNode, *LinkList;
void create_list(LinkList *L, int *a, int n) {
int i = 0;
LinkNode *p = NULL;
LinkNode *temp = NULL;
while(i < n) {
p = (LinkNode*)malloc(sizeof(LinkNode));
p->data = a[i];
p->next = NULL;
if(*L == NULL) {
*L = p;
} else {
temp->next = p;
}
temp = p;
i++;
}
}
int is_palindrome(LinkList head) {
int length = 0;
int mid = 0;
int i;
stack<LinkNode*> m_stack;
LinkNode *p = head;
LinkNode *temp = NULL;
int flag = 1;
while(p) {
length++;
p = p->next;
}
if(length %2 == 0) {
mid = length / 2;
} else {
mid = length / 2 + 1;
}
p = head;
i = 1;
while(i <= mid - 1) {
m_stack.push(p);
p = p->next;
i++;
}
if(length % 2 == 0) {
m_stack.push(p);
}
p = p->next;
while(!m_stack.empty() && p) {
temp = m_stack.top();
m_stack.pop();
if(temp->data != p->data) {
flag = 0;
break;
}
p = p->next;
}
return flag;
}
void main() {
int a[] = {1, 2, 3, 4, 5, 5, 4, 3, 2, 1};
int n = sizeof(a) / sizeof(int);
LinkList head = NULL;
create_list(&head, a, n);
if(is_palindrome(head)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
getchar();
}
1. Keep two pointers (fast and slow), you only need O(n) with the help with a stack.
2. Could find the mid point when fast pointer reaches the end of the list.
3. Then compare the top of stack with current slow pointer's data.
Below is the code:
#include <iostream>
#include <stack>
struct node
{
int data;
node* next;
node(int eData, node* eNext)
{
data = eData;
next = eNext;
}
};
bool isPanli(node* head)
{
std::stack<node*> stk;
node* slow = head;
node* fast = head;
bool flag = false;
while (fast)
{
stk.push(slow);
slow = slow->next;
fast = fast->next;
if (fast)
{
fast = fast->next;
}
else
flag = true;
}
if (flag)
stk.pop();
while (!stk.empty())
{
if (stk.top()->data == slow->data)
{
stk.pop();
slow = slow->next;
}
else
return false;
}
return true;
};
int main()
{
node* n5 = new node(1, NULL);
node* n4 = new node(2, n5);
node* n3 = new node(3, n4);
//node* n2 = new node(3, n3);
node* n1 = new node(2, n3);
node* n0 = new node(1, n1);
bool res = isPanli(n0);
return 0;
}
In Ispalin function, after checking the flag, slow pointer shd be moved fwd by one node. a nice soln though.
Traverse till the middle of the linked list and then reverse the linked list from the middle to the end inplace. After that, just compare the elements from the head and the middle.
Time Complexity = O(n)
Space Complexity = O(1)
you cant do it in O(n) through recursion without using any temp buffer.
in ur case
T(n) = T(n-2) + O(n)
and this is never gonna be equal in O(n).
i guess u chose space complexity over time complexity.
that u should nt have done.
if u take a temp array
then you will do it in O(n) time and space complexity O(n)
but TP will be better.
following is the short code for recursively checking palindrome behaviour:
bool is_palindrome(node * start)
{
static node *start1=start;
if(!start)
return true;
else
{
if(is_palindrome(start->next) &&start->data==start1->data)
{start1=start1->next;
return true;
}
return false;
}
}
I don't think this will work.
Start and start 1 are going to be equal each stack frame.
So && start->data==start1->data is going to compare the list forwards.
And the first time you hit start1=start1->next; you are actually setting it to null. but it doesn't matter because it does not effect the pointer in the other stack frame.
You would need to manage this with a pointer to a pointer or a pointer to a reference.
bool IsPalindrom(ListNode *&forward, ListNode *backward)
{
if (backward == NULL) return true;
bool isPalin = IsPalindrom(forward, backward->nextNode);
if (!isPalin) return false;
if (forward->data != backward->data) return false;
forward = forward->nextNode;
return true;
}
bool IsPalindrom(ListNode *list)
{
if (list == NULL) return true;
ListNode *forward = list;
ListNode *backward = list;
return IsPalindrom(forward, backward->nextNode);
}
Reverse the list and compare with the original list
Reversing is very easy
void reverseList (struct Node **head) {
struct Node *current = *head, *prev = NULL, *next;
while (current) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head = prev;
}
Now we can compare with original list
I guess we can do that in O(n) with only O(1) helper space.
My idea is
1\ Traversal the linked list and get length() O(n) time;
2\ Get center middle node according to the length o(n) time;
3\ Reverse the 2nd half of the linked list O(n);
4\ Keep two pointers, one from the head, one from the head of reversed 2nd half;
5\ Traversal each half and compare each nodes O(n) time
6\ Recover the 2nd half if necessary;
Therefore the total time is O(n) and space is O(1)
Comment if I got wrong, please
I am doing this by,
1) suppose we have a source linked list, now copy the entire linked list to other linked list i,e target linked list;
2) now reverse the target linked list;
3) now check if the data in the source linked list and target linked list are equal, if they are equal they are palindrome, otherwise theya are not palindrome.
4) now free the target linked list.
I know this is not best solution, but it works. Below is the code.
#include<stdio.h>
#include<malloc.h>
struct node {
int data;
struct node *link;
};
int append_source(struct node **source,int num) {
struct node *temp,*r;
temp = *source;
if(temp == NULL) {
temp = (struct node *) malloc(sizeof(struct node));
temp->data = num;
temp->link = NULL;
*source = temp;
return 0;
}
while(temp->link != NULL)
temp = temp->link;
r = (struct node *) malloc(sizeof(struct node));
r->data = num;
temp->link = r;
r->link = NULL;
return 0;
}
int display(struct node *source) {
struct node *temp = source;
while(temp != NULL) {
printf("list data = %d\n",temp->data);
temp = temp->link;
}
return 0;
}
int copy_list(struct node **source, struct node **target) {
struct node *sou = *source,*temp = *target,*r;
while(sou != NULL) {
if(temp == NULL) {
temp = (struct node *) malloc(sizeof(struct node));
temp->data = sou->data;
temp->link = NULL;
*target = temp;
}
else {
while(temp->link != NULL)
temp = temp->link;
r = (struct node *) malloc(sizeof(struct node));
r->data = sou->data;
temp->link = r;
r->link = NULL;
}
sou = sou->link;
}
return 0;
}
int reverse_list(struct node **target) {
struct node *head = *target,*next,*cursor = NULL;
while(head != NULL) {
next = head->link;
head->link = cursor;
cursor = head;
head = next;
}
(*target) = cursor;
return 0;
}
int check_pal(struct node **source, struct node **target) {
struct node *sou = *source,*tar = *target;
while( (sou) && (tar) ) {
if(sou->data != tar->data) {
printf("given linked list not a palindrome\n");
return 0;
}
sou = sou->link;
tar = tar->link;
}
printf("given string is a palindrome\n");
return 0;
}
int remove_list(struct node *target) {
struct node *temp;
while(target != NULL) {
temp = target;
target = target->link;
free(temp);
}
return 0;
}
int main()
{
struct node *source = NULL, *target = NULL;
append_source(&source,1);
append_source(&source,2);
append_source(&source,1);
display(source);
copy_list(&source, &target);
display(target);
reverse_list(&target);
printf("list reversed\n");
display(target);
check_pal(&source,&target);
remove_list(target);
return 0;
}
make a global pointer at starting of given linked-list.
traverse linked-list from right to left recursively and keep on increasing global pointer .
psudo code:
node* gptr=head
is_palindrom(gptr, head)
{
while (head != null)
{
is_palindrom( gptr , head->next)
}
if ( gptr->data == head->data)
{
gptr = gptr ->next
return;
}
else
{
cout<<" not a palindrom"
// exit_code here
}
}
#include<iostream>
using namespace std;
//node definition
typedef struct node{
node* next;
int data;
}n;
int is_palindrom(node** ptr, node** head);
n* gptr;// global pointer
void add(node** ,node**,int);
void intersect(node**,node**);
node* tail,*head;
//driver program
int main()
{ // node contains 1-2-1-1-2-1
tail=head=(node*)0;
add(&tail,&head,1);
add(&tail,&head,2);
add(&tail,&head,1);
add(&tail,&head,1);
add(&tail,&head,2);
add(&tail,&head,1);
gptr=head; // global pointer storing head
int k= is_palindrom(&gptr,&head);
cout<<k;
system("pause");
}
//utility program to check palindrom prints 1 if palindrom
// -1 if not palindrom
int is_palindrom(node** ptr, node** head)
{
int t;
if((*head)->next!=(node*)0)
t = is_palindrom( ptr, &((*head)->next));
if(t==-1)
return -1;
if((gptr)->data==(*head)->data)
{ (gptr)=((gptr)->next);return 1;}
else
{cout<<"not a palindrom"<<endl ;
return -1;}
}
// utility program to add node
void add(node** head,node** tail,int data)
{
node* temp=(node*) malloc(sizeof(node));
temp->next=(node*)0;
temp->data=data;
if(*head==(node*)0)
{
*tail=temp;
*head=temp;
}
else
{
(*head)->next=temp;
*head=temp;
}
}
//========================================================
one solution is to traverse till end
- Anonymous August 25, 2012while traversing keep on adding elements half the elements of the total elemnts travesrsed so far, in a STACK and keep on updating a variable which points to centre of list
once finding the end of list, start traversing again from center and keep on comparing travesed element with popped elemnt from stack