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, 2012private static void RearrangeLinkedList(LinkedList head, uint skip /* M */, uint delete /* N */) { if(head == null || skip < 1 || delete < 1) return; bool flag = skip != 1; // skip if true uint counter = skip == 1 ? delete : skip - 1; LinkedList node = head; while (node.Next != null) { if (flag) node = node.Next; else node.Next = node.Next.Next; if(--counter == 0) { counter = flag ? delete : skip; flag = !flag; } } }