Microsoft Interview Question for Interns


Country: India
Interview Type: In-Person




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

Node* swap(Node* head)
{
	if (head == NULL || head -> next == NULL)
		return head;
		
	Node* temp = head;
	head = head -> next;
	Node* succ = head -> next;
	head -> next = temp;
	temp -> next = swap(succ);
	return head;
}

This method is pretty straightforward if we just treat the nodes as pairs. Assuming we have at least one pair of nodes remaining, we can swap them. We set "succ" to the next node AFTER the pair we are looking at, swap the two nodes in our pair, then link the new second element to the properly swapped set of nodes that follow. To make sure the rest of the nodes are swapped, we just make sure to linked to the SWAPPED successor from our new second node.

Then, if it turns out we don't have a valid pair, that's our base case. If we have one node, then we don't need to worry about swapping, so we just return that node. If we don't have any, then we return NULL, since it's the end of our swapped list.

Just call "head = swap(head)", or wrap that up in a function, and your list should swap.

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

really nice solution...

- artemis October 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very elegant solution and excellent explanation as well. Tried using C++ and works perfect.

- mmalik1981 October 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wanted to share my thoughts... this solution is essentially a recursive version of 'Anonymous''s solution which is iterative in nature. It is so important to understand that recursive solutions are bound to fail with stack overflow when data size are huge. In essence always favor iterative solution to recursive one.

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

buckCherry speaks the truth, this solution will NOT perform as well as its iterative counterpart due to its recursive nature. Hopefully this algorithm gives a clearer picture of what is actually going on in the iterative solution and makes it easier to understand, but remember to favor iteration over recursion when possible (like in an application using this algorithm)

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

paulj91:
As far as favoring iterative solution to recursive solution is concerned I guess you are at one with me in your response.
However not sure what do you mean by ."..iterative counterpart due to its recursive nature." will NOT perform!! Would you please explain how the iterative solution by 'Anonymous' has recursive nature and why it won't perform for large data where recursive solution would fail with stack overflow!

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

nice and super solution

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

buckCherry:
I meant to say that Anonymous' solution would perform better than my listed solution for large data sets because of *my* solutions recursive nature, not any recursive nature of Anonymous' algorithm.

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

An easy and iterative way....just keep on swapping nodes while you reach the end....

static ListNode swapAdjacentNodes(ListNode head) {

if(head==null || head.next==null) {
return head;
}else {
ListNode current=head;
head=current.next;
current.next=head.next;
head.next=current;
while(current.next!=null && current.next.next!=null) {
ListNode temp=current.next;
current.next=current.next.next;
temp.next=current.next.next;
current.next.next=temp;
current=current.next.next;
}
return head;
}
}

- Anshul December 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 vote

node* swap2(node* head)
{
if( head == NULL || head->next == NULL)
return head;

node* node1 = head;
node* node2 = node1->next;
node* node3 = head->next;
node* prev = NULL;

while(node1 != NULL && node2 != NULL)
{
if(prev)
prev->next = node2;

node1->next = node2->next;
node2->next = node1;
prev  = node1;

node1 = node1->next;
if(node1)
node2 = node1->next;
}

return node3;
}

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

could u please explain this code???

- abh October 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am trying to understand the code but there is one error which will give segfault anyway. You need to pass Node** head and put the updated head here or you could return something which is initialized on free-store in this function.

- Bruce October 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

My solution is in C#

public static void SwapConsecutive(ref Node head) // ref because head will change
        {
            if (head == null || head.next == null)
                return;
            Node current = head;
            Node tmp = head.next;
            if (tmp != null)
                head = tmp;
            Node next;
            Node last = null; // that is from the previous swap
            while (current != null && current.next != null)
            {
                tmp = current.next;
                next = tmp.next;
                tmp.next = current;
                if (last != null)
                    last.next = tmp;
    
           current.next = next;
                last = current;
                current = next;
           }

}

- berkaypamir November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

...............[n11]->[n12]->[n13]->[n14]...............

lets have ptr(Node *ptr) pointer at [n11]
and we have to swipe [n12] and [n13]

Node *temp;
temp = ptr->next;
ptr->next-= ptr->next->next ;
temp->next = ptr->next->next;
ptr->next->next = temp;

- PKT October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node* swap(node *head)
{
    if(head) {
           nextNode = head->next;
           newHead = head;
           if(nextNode) {
                      rest = nextNode->next;
                     newHead = nextNode;
                      nextNode->next = head;            
                      assert(swapPair(rest, nextNode))
            }              
           return newHead;

}


int swapPair(node *list, node *back)
{
           if(list) {
                      first = list;
                      second = list->next;
                      rest = null;
                      if(second) {
                                 rest = second->next;
                                 second->next = first;
                                 first->next = rest;
                      }
                      back->next = second;
                                 
                     swapPair(rest, );
           }
}

- Noobie October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1->2->3->4->5->6->7
here current =1, next1= 2, next2=3
we change the links pairwise, first 1 and 2, then 3 and 4, then 5 and 6 when our current is 7 and its next is null we stop

below code will give
2->1->4->3->6->5->7

Node{
        int data
        Node next
}
void ChangeLinks(Node head)
{
current = head;
next1= current.next;
next2=next1.next;

while(current.next!=null)
{
next1.next= current;
current.next=next2;
current = next2;
next1 = current.next;
next2= next1.next;
}
}

- Man October 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its understood that next1 and next2 are type Node
Node next1 = new Node()
Node next2 = new Node()

- man October 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void swapelements(struct list **l)
{
struct list *y = *l;
struct list *x;
if(NULL == y || NULL == y->next)
return;
x = y->next;
y->next = x->next;
x->next = y;
*l = x;
swapelements(&(x->next->next));
}

- venkat October 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node *head=NULL;
swap()
{
struct Node *ptr;
ptr=head;
int count=0;
while(ptr->next!=NULL)
{
count++;
if(count%2!=0)
{
temp=ptr->data;
ptr->data=ptr->next->data;
ptr->next->data=ptr->data;
}
else
ptr=ptr->next;
}

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

Node swapNodes(Node ptr)
	{
		
		if (ptr == null)
		{
			return null;
		}
		
		if (ptr.next == null)
		{
			return  ptr;
		}
		
		Node ptr1,startPtr = null;
		int count=0;
		ptr1= ptr;
		
				
		while(ptr!= null && ptr.next!=null)
		{
			count++;
			ptr1= ptr.next;
			ptr.next=ptr1.next;
			ptr1.next= ptr;
			
			
			if (count==1)
			{
				startPtr = ptr1;
			}
			
			ptr = ptr.next;
			ptr1 = ptr1.next;
			
			if(ptr!=null && ptr.next!=null )
			{
				ptr1.next=ptr.next;	
			}
			
			
		
			
		}
	
		return startPtr;
	
	}

- Sushant October 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node *temp,*first,*second,*third;
first=head;
second=first->next;
temp=second;
third=second->next;
while(first!=NULL)
{
second->next=first;
first->next=third->next;
first=third;
second=first->next;
third=second->next;
}

head=temp;

- I am not having the head as an argument. Assume it's declared globally. November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

list * alternateSwap(list * node)
 {
      if (node!=NULL&&node->next!=NULL)
      {       
      list *temp= new list;
      temp->next=node->next->next;         //swap step 1   //save the next nodes link;
      node->next->next=node;               //swap step 2   //break & update next nodes link
      node=node->next;                     //swap step 3 update node
      node->next->next=alternateSwap(temp->next);       //find next link of swapped node
      delete temp;
      }
      return node;

}

example 1 -> 2-> 3

swap step 1 : save 2->next=3
swap step 2 : 2->next =1
swap step 3 : 2= node or head
step 4 : 2->next->next=alternateSwap(3) => 1->next=alternateSwap(3) = 3;

therefore final result = 2->1->3;

- sahil.bathla1 November 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

iterative code

list * alternateSwap(list * node)
 {
      list *previous_joint,*new_joint,*temp;
      previous_joint=new list;
       
       while (node!=NULL&&node->next!=NULL)
      {       
      temp=node->next->next;        
      node->next->next=node;               //swap step 1   //break & update next nodes link
      if(node==list_head)
      list_head=node->next;
      node=node->next;                     //swap step 2 update node
      
      new_joint=node->next;                // saving joining point       
      
      if(node!=list_head)
      {
      previous_joint->next=node;           //joining previous joint with new swapped node
      previous_joint=new_joint;
      }
      else
      previous_joint=new_joint;            //saving first joining point

      node=temp;
      
      } //end of while

      previous_joint->next=node;
      
      return list_head;

}

- sahil.bathla1 November 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

take a look at this....

void swap(nd *start,nd *ptr1,nd *ptr2)
{
if(start->next==NULL)
{
return;
}

else
{
nd *temp,*nt;
nt=ptr2->next;
temp=ptr1;
start->next=ptr1->next;
ptr2->next=temp;
temp->next=nt;
//temp->next=NULL;
p("%d %d",start->next->data,start->next->next->data);
start=start->next->next;

if(start->next!=NULL&&start->next->next!=NULL)
{
//p("coe ejfodfodfo fo foufoifojldfjlf ljf ljfl \n");
swap(start,start->next,start->next->next);
return;
}
}
}

void print(node *pointer)
{
//pointer=pointer->next;
if(pointer==NULL)
{
return;
}
//printf("elements are...\n");

printf("%d\n",pointer->data);
print(pointer->next);
}

- mandeep624 November 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node* Swap(Node* node)
{
	if (node == NULL || node->next == NULL)
	return node;
	
	Node* cur = node;
	Node* next = node->next;

	node->next = Swap (node->next->next);
	next->next = cur;

	return next;
}

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

void swapalternate(node * p)
{
//p is the header of the original list and following it are temp1,temp2.
temp=p;
temp1=temp->link;
temp2=temp1->link;
p=temp1;//header changed here 
while(temp!=NULL)
{
temp1->link=temp;
temp->link=temp2->link;
temp=temp2;
temp1=temp->link;
temp2=temp1->link;

}

}

- Anonymous July 24, 2013 | 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