Microsoft Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
nice logic
tried implementing it but with this also to change head, you'll need some temporary nodes which are not allowed.
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).
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]
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;
}
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..
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
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??
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
char info;
struct Node *next;
}node;
node *head;
void populate();
void print();
void swap();
int main(int argc, char *argv[])
{
populate();
print();
swap();
system("PAUSE");
return 0;
}
void swap()
{
node *temphead,*first,*second,*third;
temphead=head;
first=head;second=head;third=first->next;
first->next=third->next;third->next=second;head=third;
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;
head=temp;
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;
travel=head;
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->
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
char info;
struct Node *next;
}node;
node *head;
void populate();
void print();
void swap();
int main(int argc, char *argv[])
{
populate();
print();
swap();
system("PAUSE");
return 0;
}
void swap()
{
node *temphead,*first,*second,*third;
temphead=head;
first=head;second=head;third=first->next;
first->next=third->next;third->next=second;head=third;
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;
head=temp;
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;
travel=head;
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->
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
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 ?
{ 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("enter your choice:\n");
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);
}
}
}
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
main part of the code
public void reverseByNum(int groupNumber) {
// [1,2,3,4,5,6,7,8,9]
this.head = reverseByNum(groupNumber, this.head);
}
private Node reverseByNum(int groupNumber, Node headNode) {
Node currentNode = headNode;
Node nextNode = null;
Node currentHead = headNode;
int count = 1;
while (currentNode.nextNode != null && count < groupNumber) {
nextNode = currentNode.nextNode;
currentNode.nextNode = nextNode.nextNode;
nextNode.nextNode = currentHead;
currentHead = nextNode;
count++;
}
if (currentNode.nextNode != null) {
currentNode.nextNode = this.reverseByNum(groupNumber,
currentNode.nextNode);
}
return currentHead;
}
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);
}
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;
}
void linklist::alt_rev(){
node *temp=0;
node *newhead=0;
if(newhead==0) {
newhead=head->link;
head->link=newhead->link;
newhead->link=head;
temp=head;
head=head->link;
}
while(head != 0 && head->link!=0) {
temp->link=head->link;
head->link=temp->link->link;
temp->link->link=head;
temp=head;
head=head->link;
}
head=newhead;
}
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.
We can use this function :
void swaplistnodes(Node_S **head)
{
Node_S *ptr1 = *head,*ptr2 = *head,*ptr3 = *head,*ptr4 = NULL;
if((*head != NULL)&&((*head)->next!= NULL))
{
*head = ptr2 = ptr2->next;
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;
}
}
}
}
void swaplistnodes(Node_S **head)
{
Node_S *ptr1 = *head,*ptr2 = *head,*ptr3 = *head,*ptr4 = NULL;
if((*head != NULL)&&((*head)->next!= NULL))
{
*head = ptr2 = ptr2->next;
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;
}
}
}
}
void swaplistnodes(Node_S **head)
{
Node_S *ptr1 = *head,*ptr2 = *head,*ptr3 = *head,*ptr4 = NULL;
if((*head != NULL)&&((*head)->next!= NULL))
{
*head = ptr2 = ptr2->next;
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;
}
}
}
}
What about if we pass pointer to pointers of these two nodes and then, swap the pointers via bitwise XOR!
- Abhijit September 22, 2012void swapNodes(struct Node **n1, struct node **n2){ (*n1) = (int)(*n1)^(int)(*n2); (*n2) = (int)(*n1)^(int)(*n2); (*n1) = (int)(*n1)^(int)(*n2); }