## Microsoft Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

What about if we pass pointer to pointers of these two nodes and then, swap the pointers via bitwise XOR!

``````void swapNodes(struct Node **n1, struct node **n2){
(*n1) = (int)(*n1)^(int)(*n2);
(*n2) = (int)(*n1)^(int)(*n2);
(*n1) = (int)(*n1)^(int)(*n2);
}``````

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

nice logic
tried implementing it but with this also to change head, you'll need some temporary nodes which are not allowed.

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

If he's asking you to do this:
input: a->b->c->d->e
output: e->d->c->b->a
do the following:
1. Get the length of the list: n.
2. swap the value in index 0 and index n-1:
e->b->d->d->a
swap the value in index 1 and index n-2:
e->d->c->b->a
...
(swap the value in ith and n-1-ith places until i == n/2)
the swap function is perfectly defined by Abhijit.
Time complexity: O(n^2).

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

Excuse me if I am doing it wrong but I am getting the following compilation error while trying to compile the xor swap pointer function

error: invalid conversion from 'int' to 'Node*' [-fpermissive]
error: invalid conversion from 'int' to 'Node*' [-fpermissive]
error: invalid conversion from 'int' to 'Node*' [-fpermissive]

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

One condition : data item should be either integer, or float, or char. but not string, or others
then what ever @Abhijit has written is correct, for implementation use following

``````void swap(Node *N1, Node *N2)
{
N1->data = N1->data-N2->data;
N2->data = N2->data + N1->data;
N1->data = N2->data-N1->data;
}``````

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

The solution is just swap data values for eg:a->b->c->d->e if i want to swap c and d then just swap data values of the nodes..

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

I think this would be the simplest and fastest solution ;) Only fear! After such simple solution the interviewer should not get furious and kick the person out :P

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

``i thought the same. But we wud be asked to leave :P``

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

It will be easy if we want to swap first two nodes in a list,for eg:1->2->3->4->5 if i want to swap 3 and 4 then i have two store node 5 address in node 3 link field and node 3 address in node 4 link field and node 4 address in node 2 link field ,with out using extra how can i get node 2 address??

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

They asked not to use a extra node but we can use extra pointers.

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

``````#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
char info;
struct Node *next;
}node;
void populate();
void print();
void swap();
int main(int argc, char *argv[])
{
populate();
print();
swap();
system("PAUSE");
return 0;
}
void swap()
{
third=third->next;second=second->next;first=first->next->next;
while(first!=NULL){

third->next=first;
second->next=first->next;
first->next=second;

second=third->next;first=first->next;
if(first->next!=NULL)
{third=first;second=third->next;first=second->next;}
else
first=NULL;
}
print();
printf("\n");
}
void populate()
{
node *temp,*temp1;
int i=1;
temp=(node *)malloc(sizeof(node));
if(temp==NULL){
printf("\nCannot allocate Memory");
system("pause");
}
temp->next=NULL;temp->info=65;
while(i<9){
temp1=(node *)malloc(sizeof(node));
if(temp==NULL)
printf("cannot allocate memory");
temp1->next=NULL;temp1->info=65+i;
temp->next=temp1;
temp=temp->next;
i++;
}

}
void print()
{
node *travel;
printf("\n");
while(travel){
printf("%c\t",travel->info);
travel=travel->next;
}
}``````

Input: a->b->c->d->e->f->
output: b->a->d->c->f->e->

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

But they asked me not to use any extra node.

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

this is pairwise swap not simple 1

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

``````#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
char info;
struct Node *next;
}node;
void populate();
void print();
void swap();
int main(int argc, char *argv[])
{
populate();
print();
swap();
system("PAUSE");
return 0;
}
void swap()
{
third=third->next;second=second->next;first=first->next->next;
while(first!=NULL){

third->next=first;
second->next=first->next;
first->next=second;

second=third->next;first=first->next;
if(first->next!=NULL)
{third=first;second=third->next;first=second->next;}
else
first=NULL;
}
print();
printf("\n");
}
void populate()
{
node *temp,*temp1;
int i=1;
temp=(node *)malloc(sizeof(node));
if(temp==NULL){
printf("\nCannot allocate Memory");
system("pause");
}
temp->next=NULL;temp->info=65;
while(i<9){
temp1=(node *)malloc(sizeof(node));
if(temp==NULL)
printf("cannot allocate memory");
temp1->next=NULL;temp1->info=65+i;
temp->next=temp1;
temp=temp->next;
i++;
}

}
void print()
{
node *travel;
printf("\n");
while(travel){
printf("%c\t",travel->info);
travel=travel->next;
}
}``````

Input: a->b->c->d->e->f->
output: b->a->d->c->f->e->

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

The easiest would be to swap data. But if reference of nodes are stored already then swapping data would create chaos, In that case one should swap nodes itself.

Lets say list is a->b->c->d->e and we want to swap c with d,
lets take two pointers p and q, where p points to b and q points to c. Following three lines will swap the nodes.
p->next = q->next (so now b points to d)
q->next = p->next->next (now c points to e)
p->next->next = q (now d points to c)

this will result in a->b->d->c->e

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

I guess we shouldn't use any extra nodes

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

Will this logic work..if i want to swap the first and last node? in that case where should p and q be initially pointing to ?

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

This code only seems to work when we are swapping two sequential nodes and neither of them is the starting node.

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

{ suppose we have 1 2 3 4 and we have to swap 2 with 3 so after swapping ge get 1 3 2 4 .now let we have to struct pointer *p and *q. *p indicating number 2 and *q indicating number 3.
code: }

#pragma pack(1)
typedef struct node
{
int info;
struct node *next;
}node;
void display(node *p)
{

while(p!=0)
{
printf("%d ",p->info);
p=p->next;
}
printf("\n");

}
void swap(node *p)
{
node *q;
q=p->next;
p->next=q->next;
q->next=p->next->next;
p->next->next=q;
printf("after swaping nodes are:\n");
display(p);
}
main()
{
void display(node *);
void swap(node *);
node *p,*q,*r;
int i;
printf("create node:\n");
scanf("%d",&i);
r=(node *)malloc(sizeof(node));
r->info=i;
r->next=0;
p=r;
while(scanf("%d",&i))
{
if(i==0)
break;
q=(node *)malloc(sizeof(node));
q->info=i;
q->next=0;
r->next=q;
r=q;
}
while(1)
{
printf("1: to display\n");
printf("2: to swap\n");
printf("3: to exit\n");
scanf("%d",&i);
switch(i)
{
case 1: r=p;
display(r);
continue;
case 2: swap(p);
continue;
case 3: exit(0);
}
}
}

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

I was also asked this question as a part of MS Online Coding round.
However, swapping '2' values is just an example.
Actual question involved reversing every 'k' elements.
e.g if k=3 and input is a->b->c->d->e->f->g->h->i->j
Output = c->b->a->f->e->d->i->h->g->j

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

it is not difficult, if k = 2, a->b, just swap the value of a and b,
if k = 3, a->b->c, swap a and c, if k=4, a->b->c->d, swap a, d, then b, c....

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

main part of the code

public void reverseByNum(int groupNumber) {
// [1,2,3,4,5,6,7,8,9]
}

private Node reverseByNum(int groupNumber, Node headNode) {
Node nextNode = null;
int count = 1;
while (currentNode.nextNode != null && count < groupNumber) {
nextNode = currentNode.nextNode;
currentNode.nextNode = nextNode.nextNode;
count++;
}

if (currentNode.nextNode != null) {
currentNode.nextNode = this.reverseByNum(groupNumber,
currentNode.nextNode);
}

}

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

Have not been able to test, but following are my thoughts...

``````/*
Assumptions on requirements...
input ----- output
NULL ----- NULL
a->NULL ----- a->NULL
a->b->NULL ----- b->a->NULL
a->b->c->NULL ----- b->a->c->NULL
a->b->c->d->NULL ----- b->a->d->c->NULL

*/
Node* recur_modify(Node *p, int &num_nodes) {
++num_nodes;
if (p->next == NULL) return p;

Node *next = recur_modify(p->next, num_nodes);
if (next->next == NULL)
if (num_nodes % 2 != 0) return p;

p->next = next->next;
next->next = p;
return next;
}

void modify(Node *root) {
if (root == NULL) return root;
int num_nodes = 0;
root = recur_modify(root, num_nodes);
}``````

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

public void swap(int number)
{
linkedlist curr = firstnode, next = null, prev =null, temp = null;
while(curr.info != number)
{
prev = curr;
curr = curr.nextReference;
next = curr.nextReference;
System.out.println(prev.info + ":" + curr.info + ":" + next.info);
}
temp = next.nextReference;
prev.nextReference = next;
next.nextReference = curr;
curr.nextReference = temp;

}

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

void swap(node * pre, node *a, node * b){
a->next = b->next;
b->next = a;
pre->next = b;
}

in the code, pre->a->b->....->tail;

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

just swap the value of a and b
void swap(node * a, node * b){
a->data = a->data + b->data;
b->data = a->data - b->data;
a->data = a->data - b->data;
}

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

Swaping the values in the link list , gives you only few data type to swap, but not all the information ......just reverse the link list .....by exchanging the head pointer......

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

We can use doubly linked list and just change the reference of the respective nodes this should always take constant time. But the realization of the node can be or order O(n).

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

``````void linklist::alt_rev(){
node *temp=0;

}
}

}

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

If a and b are neighbors (x->a->b->c), it is easy.

``````swapNeighbors(a,b)
{
a.next=b.next;
b.pre=a.pre;
b.next=a;
}``````

If b is not directly after a then:

keep swapping a with its neighbor, until you reach b. (count how many times you did this=n)
Swap a with b.
keep Swapping b with its parent n times.

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

We can use this function :

{
{
if(ptr2->next!=NULL)
{
ptr3 = ptr2->next;
while((ptr3!=NULL)&&(ptr3->next!=NULL))
{
ptr2->next = ptr1;
ptr1->next = ptr3->next;
ptr1 = ptr3;
ptr2 = ptr3->next;
ptr3 = ptr3->next->next;
}
if(ptr3==NULL)
{
ptr2->next = ptr1;
ptr1->next = NULL;
}
else if(ptr3->next==NULL)
{
ptr2->next = ptr1;
ptr1->next = ptr3;
}
}
}
}

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

``````void swaplistnodes(Node_S **head)
{
{
if(ptr2->next!=NULL)
{
ptr3 = ptr2->next;
while((ptr3!=NULL)&&(ptr3->next!=NULL))
{
ptr2->next = ptr1;
ptr1->next = ptr3->next;
ptr1 = ptr3;
ptr2 = ptr3->next;
ptr3 = ptr3->next->next;
}
if(ptr3==NULL)
{
ptr2->next = ptr1;
ptr1->next = NULL;
}
else if(ptr3->next==NULL)
{
ptr2->next = ptr1;
ptr1->next = ptr3;
}
}
}``````

}

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

{
{
if(ptr2->next!=NULL)
{
ptr3 = ptr2->next;
while((ptr3!=NULL)&&(ptr3->next!=NULL))
{
ptr2->next = ptr1;
ptr1->next = ptr3->next;
ptr1 = ptr3;
ptr2 = ptr3->next;
ptr3 = ptr3->next->next;
}
if(ptr3==NULL)
{
ptr2->next = ptr1;
ptr1->next = NULL;
}
else if(ptr3->next==NULL)
{
ptr2->next = ptr1;
ptr1->next = ptr3;
}
}
}
}

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.