Microsoft Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
6
of 8 vote

one solution is to traverse till end
while 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

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

I like this solution

- Vincent August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

whats the solution on cracking inteview. i think the space overhead of STACK solution is more due to mantaining a stack

- Anonymous August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution!

- HS August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good One

- Deepak Garg September 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Bin December 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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();
}

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
6
of 6 vote

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;
}

- hao.liu0708 August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is the most elegant solution presented here.

- berkaypamir November 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In Ispalin function, after checking the flag, slow pointer shd be moved fwd by one node. a nice soln though.

- praveen December 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how clever you are, I think these codes are better than me at upstairs. I am very grateful for your nice idea.

- yingsun1228 January 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
6
of 8 vote

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)

- Animesh Sinha August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

In this case you are modifying actual list.

- Deepak Garg September 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

OK, then reverse the second half again. It is still O(n) :)

- aygul November 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

- guest travis August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sometimes taking some extra space will be better as it can give the best time complexity

- guest travis August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

question on cracking code interview

- Vincent August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

wwwDOTgeeksforgeeksDOTorg / archives / 1072

- riteshkyal August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- sandeep September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Alan September 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

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

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

- crystal.rishi2 October 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- agmegharaj November 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool ispar(linklist **t, linklist *s)
{
 if(s==NULL) return 1;
 bool ret=ispar(&((*t)->pnext),s->pnext);
 if(ret==0) return 0;
 if((*t)->data==s->data)
	 return 1;
 else return 0;

}

- Charles August 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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
      }

}

- hammer_skull August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#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;
                                    }
                                    }
//========================================================

- hammer_skull August 25, 2012 | 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