## Microsoft Interview Question

Software Engineer / Developers**Team:**bing

**Country:**India

**Interview Type:**In-Person

Hi guys,

How about this one.

Any feedback or correction/bugs are welcome.

```
void RetainMandDeleteNNodes(Node* head, int m, int n)
{
Node* current = head;
Node* temp = NULL;
int i = m;
int j = n;
if(head == null)
return;
while(current!=null)
{
i = m;
j = n;
//retains m nodes
while(current!= null && --i > 0 )
{
current = current->next;
}
//suppose there are 2 nodes and m was given as 3, after moving two nodes
current would be at NUll. After which we cannot continue to delete n nodes.
if(current == null) break;
//deletes n nodes
while(current != null && --j >0)
{
temp = current->next;
if(temp != null)
{
current = temp->next;
free(temp);
}
else
{
break;
}
}
}
}
```

Hi, too many variables and too many checks, I think there's a simpler way to implement this. And also you're forgetting to check M==0 and N==0 corner cases, which simplify the whole thing noticably.

```
size_t count = 0;
List *retain_finish;
while(h != NULL) {
if(count < M) {
if(count == M - 1) retain_finish = h;
h = h->next;
++count;
} else {
List *tmp = h;
h = h->next;
delete tmp;
retain_finish->next = h;
count = count == M + N - 1 ? 0 : count + 1;
}
}
```

@just_passing_through: use-before-set on retain_finish if M == 0 (unless checked and handled outside, not shown).

Yep, I mentioned the corner cases (M==0, N==0) originally. They're being checked and handled outside of the function main loop:

```
if(head == NULL) {
cerr << "try again" << endl;
exit(1);
}
if(N == 0) // nothing to delete
return head;
List *h = head;
if(M == 0) {
// delete the whole list
while(h) {
List *tmp = h;
h = h->next;
delete tmp;
}
return NULL;
}
```

```
void skip_M_del_N(Node * node, unsigned int M, unsigned int N)
{
ASSERT(M + N); // M > 0 || N > 0 -- asking for an infinite loop
// ideally should also check if M and N each fit in a signed int
if ( N == 0 ) return; // nothing to delete -- we are done.
int count = M ? M : -N; // positive => skip; negative => delete. Won't be 0.
Node * last_skipped = 0;
while ( node ) {
if ( count > 0 ) { // more to skip
if ( --count == 0 ) {
count = -N; // flip to deleting
last_skipped = node; // remember where to re-link
}
node = node->next;
} else /* if ( count < 0 ) */ { // more to delete
Node * next = node->next;
delete node; // if necessary
node = next;
if ( last_skipped ) last_skipped->next = next;
if ( ++count == 0) count = M ? M : -N; // flip to skipping
}
} // while ( node )
}
```

```
Node skipMdeleteN(Node node,int M , int N){
if(node==null) return null;
Node current=node;
Node prev=null;
int counter=0;
while(true){
counter=0;
while(current!=null && counter<M){
prev=current;
current=current.next;
counter++;
}
if(current==null) return node;
counter=0;
while(current!=null && counter<N){
Node next=current.next;
current=null;
if(prev!=null)prev.next=next;
else node =current;
current=next;
counter++;
}
if(current==null) return node;
}
```

}

```
Node skipMdeleteN(Node node,int M , int N){
if(node==null) return null;
Node current=node;
Node prev=null;
int counter=0;
while(true){
counter=0;
while(current!=null && counter<M){
prev=current;
current=current.next;
counter++;
}
if(current==null) return node;
counter=0;
while(current!=null && counter<N){
Node next=current.next;
current=null;
if(prev!=null)prev.next=next;
else node =current;
current=next;
counter++;
}
if(current==null) return node;
}
```

}

typedef struct xxx

{

int x;

struct xxx *left;

struct xxx *right;

}tree;

int trav_right(tree *r)

{

while(r!=0)

{

printf("%d\t",r->x);

r=r->right;

}

}

int trav_left(tree *p)

{

while(p!=0)

{

printf("%d\t",p->x);

p=p->left;

}

}

tree* delet(tree *p)

{

printf("\ndelete\n");

trav_right(p);

p=p->left;

p->right=0;

}

tree* create(tree *p,int i)

{

tree *ptr1;

if(p->right==0)

{

ptr1=malloc(sizeof(tree));

ptr1->left=p;

ptr1->x=i;

p->right=ptr1;

ptr1->right=0;

p=ptr1;

}

}

main()

{

int i=0,m,n;

printf("enter the value of M and N:\n");

scanf("%d%d",&m,&n);

tree *p,*r,*q;

p=malloc(sizeof(tree));

p->x=i;

p->left=0;

p->right=0;

r=p;

while(i!=5)

{

i++;

q=create(p,i);

p=q;

}

trav_right(r);

printf("\n");

while(p->left!=0)

{

int x=m;

int y=n;

while(x!=0)

{

i++;

q=create(p,i);

p=q;

x--;

}

printf("after adding M more:\n");

trav_right(r);

printf("\n");

while(y!=0)

{

q=delet(p);

p=q;

y--;

}

printf("\nafter deleting N nodes:\n");

trav_right(r);

printf("\n");

}

}

When i interviewed with them long time back the same person was asking the same question. I am surprised how lame they are with their questions. I can tell you that this must have been asked to you by a person with initials N.N

their interviews were so lame that i felt that they can put up a board "Trespassers will be recruited"

```
node* skipMDeleteN(node* head, int m, int n)
{
if(head == NULL)
{
printf("\nList is empty");
getch();
return head;
}
if(length(head)<m)
{
printf("\nlenght of the list is less than m");
getch();
return head;
}
if(m == 0 && n == 0)
return head;
if(m == 0 && n > 0)
return NULL;
node* current = head;
node* prev = NULL;
int counter = 0;
while(current != NULL && counter < m)
{
//skip m element
prev = current;
current = current->link;
counter++;
}
counter = 0; //reset counter
node* temp = NULL;
while(current != NULL && counter < n)
{
temp = current;
current = current->link;
temp->link = NULL;
free(temp);
counter++;
}
prev->link = skipMDeleteN(current,m,n);
return head;
}
```

```
struct node* skipdelete(int n, int m, struct node* head)
{
int i;
struct node* skip = head; // m is the number of nodes to skip and n is the no. of nodes to delete.
struct node* runner;
struct node* head1;
struct node* temp;
while(1)
{
for(i=0; i<m-1; i++)
{
skip = skip->next;
if(skip == NULL)
return head;
}
runner = skip;
head1 = skip;
for(i=0; i<n; i++)
{
temp = skip->next;
if(temp == NULL)
return head;
runner = skip->next->next;
free(temp);
if(runner == NULL)
{
head1->next = NULL;
return head;
}
head1->next = runner;
}
skip = head1->next; // we have to update the skip only when all the n nodes are deleted.
}
}
```

I used C++ here:

```
void IterateThenDeleteNode( node *head, int m, int n ) {
int count(0);
node *current = head;
node *old = NULL;
if( !head )
return;
while( current ) {
if( count == m ){
count = 0;
for( int i = 0; i < n; i++ ) {
if( !current )
return;
old->next = current->next;
delete current;
current = old->next;
}
} else {
old = current;
current = current->next;
count++;
}
}
}
```

the algo will be as follows: (let m = 2 and n = 3)

1) take two pointers temp1 and temp 2 and two counters m and n initialized to 0.

2) let temp1 and temp2 initially be equal to the head of the list.

3) Repeat the following steps till temp1 ! = null

(a) while m<2, temp1 = temp 1 ->next (bring temp1 to the mth position.

(b) while n<3 and temp1 -> next != null

temp1 -> next = temp 2 (make temp2 the next node of temp1)

temp1 -> next = temp2 -> next

free(temp2)

this will delete the next n nodes.

```
void restoreM_DeleteN(node *head, int M, int N){
if (head == NULL || M<1 ||N<1) return;
while(M!=1){
if (head == NULL){ print "Error:Length is shorter than M"; return;}
head = head->next;
M--;
}
first = head;
head = head->next;
while(N!=1){
if (head == NULL){print "Error: all nodes deleted"; return ;}
temp = head;
head = head->next
free(temp);
N--;
}
first->next = head;
}
```

```
typedef struct _Node
{
int data;
struct _Node *next;
}Node;
void deleteMN(Node *h,int M,int N)
{
Node *prev=h;
Node *curr=h->next;
Node *temp;
int countM=0,countN=0;
while(curr!=NULL)
{
if(countM<M)
{
prev=prev->next;
curr=curr->next;
countM++;
}
else if(countM==M)
{
countN=0;
while(countN<N)
{
temp=curr->next;
prev->next=temp;
curr=temp;
countN++;
}
countM=0;
}
}
}
```

Flawless code... Enjoy!!

```
void keepMdeleteN(node* &head, int M, int N)
{
// No element needs to be deleted
if (!head || N < 1)
return;
int m = M, n = N;
node *p = head, *prev = head, *next = head;
// Complete list will be deleted
if(M<1)
head = NULL;
while(p)
{
next = p->next;
if(m>0)
{
m--;
prev = p;
p = next;
}
else if(n>0)
{
n--;
delete p;
p = next;
}
else
{
m = M;
n = N;
prev->next = p;
}
}
}
```

```
function linklist ($m, $n) {
$curr = $this->head; //Assign curr node to head pointer
while($curr != NULL) { //Go through all the nodes and keep until you hit mth node
$curr = $curr->next;
$count++;
if ($count == $m) { break; } //When you hit mth node, break out of the loop
}
while ($n) { //Go through n nodes, from the mth node
$temp = $curr; //Mark your mth node
$curr = $curr->next;
$n--;
}
$temp->next=$curr;
}
```

Havent tested the code out just so that you know.

Tried and tested code properly.

void DelMN_Node(struct node**root, int n, int m)

{

struct node *head, *delNode;

int countM, countN;

countM=0;countN=0;

head = *root;

while(head)

{

while(countM++ < m-1 && head)

head = head->next;

if(head)

{

delNode = head->next;

while(delNode && countN++ < n)

{

head->next = delNode->next;

free(delNode);

delNode = head->next;

}

head = head->next;

countM=0;

countN=0;

}

}

if(m==0)

{

free(*root);

*root=NULL;

}

}

- Artur Sokhikyan March 25, 2012