## Microsoft Interview Question for Interns

• 1
of 1 vote

Country: India
Interview Type: In-Person

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

``````Node* swap(Node* head)
{

Node* succ = head -> next;
temp -> next = swap(succ);
}``````

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.

Comment hidden because of low score. Click to expand.
0

really nice solution...

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
0

nice and super solution

Comment hidden because of low score. Click to expand.
0

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.

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....

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

Comment hidden because of low score. Click to expand.
1
of 3 vote

``````node* swap2(node* head)
{

node* node2 = node1->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;
}``````

Comment hidden because of low score. Click to expand.
0

could u please explain this code???

Comment hidden because of low score. Click to expand.
0

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.

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
{
return;
if (tmp != null)
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;
}``````

}

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;

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

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

}

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

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
}
{
next1= current.next;
next2=next1.next;

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

Comment hidden because of low score. Click to expand.
0

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

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

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

swap()
{
struct Node *ptr;
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;
}

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;

}``````

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

``````Node *temp,*first,*second,*third;
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;
}

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;

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

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
node=node->next;                     //swap step 2 update node

new_joint=node->next;                // saving joining point

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

}``````

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

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

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;
while(temp!=NULL)
{
temp=temp2;

}

}``````

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.

### 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.