Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
void deleteNthfromLast(struct node **p)
{
struct node *start,*t1,*temp;
int n;
start = *p;
printf("Enter the nth element from end to be deleted = ");
scanf("%d",&n);
while(n && start) //
{
start = start->next;
n--;
}
if(!start) //if the input provided is less than the linklist size
{
printf("\nWrong input provided");
return;
}
if(!start->next) //frist node to be deleted
{
temp = *p;
*p = (*p)->next;
free(temp);
return;
}
start = start->next; //t1 should point to one node behind the actual node to delete
t1 = *p;
while(start->next)
{
start = start->next;
t1 = t1->next;
}
temp = t1->next;
t1->next = t1->next->next;
free(temp);
return;
}
#include<iostream>
using namespace std;
struct node
{
int k;
node *next;
};
node *HEAD = NULL;
node* create(int v)
{
node *temp = new node;
temp->k = v;
temp->next = NULL;
return temp;
}
void insert(node *n)
{
if(HEAD == NULL)
HEAD = n;
else
{
node *m = HEAD;
while(m->next != NULL)
{
m = m->next;
}
m->next = n;
}
}
void show()
{
node *m = HEAD;
while(m != NULL)
{
cout<<m->k<<"->";
m = m->next;
}
cout<<"NULL";
}
void delete_Nth(int v)
{
node *m = HEAD;
node *prev = HEAD;
bool continu = true;
while(continu && m!= NULL)
{
int i;
node *n = m;
for(i = 0; i < v && n != NULL ;)
{
i++;
n = n->next;
}
if((i == v) && (n == NULL))
{
if(m == HEAD)
HEAD = m->next;
else
prev->next = m->next;
delete m;
continu = false;
}
else
{
prev = m;
m = m->next;
}
}
show();
}
int main()
{
char ch = 'y';
int v;
do
{
cout<<"Enter new key : ";
cin>>v;
insert(create(v));
cout<<"Enter more (y/n) ? : ";
cin>>ch;
}while(ch == 'y');
cout<<"\n\nEnter the last nth node number to delete : ";
cin>>v;
delete_Nth(v);
return 0;
}
Node* DeleteNthLast(Node* head, int n)
{
Node* temp = head;
Node* t = head;
int m = 0;
if( head== NULL )
return head;
while( temp != NULL )
{
temp = temp->next;
if( m >= n+1 )
t = t->next;
m++;
}
if( m == n)
return head;
temp = t->next;
t->next = t->next->next;
delete(temp);
return head;
}
#include<iostream>
using namespace std;
typedef struct node{
int data;
struct node* next;
}* Node;
Node createSLL(const int& n){
if(n <= 0)
return NULL;
Node head = (Node) malloc(sizeof(struct node));
head->data = 1;
head->next = NULL;
Node tempHead = head;
for(int i = 2; i <= n; i++){
Node tempNode = (Node) malloc(sizeof(struct node));
tempNode->data = i;
tempNode->next = NULL;
tempHead->next = tempNode;
tempHead = tempNode;
}
return head;
}
void printSLL(Node head){
Node tempHead = head;
while(tempHead){
cout << tempHead->data << " ";
tempHead = tempHead->next;
}
cout << endl;
return;
}
bool deleteNthElement(Node& head, const int& n){
if(head == NULL || n <= 0)
return false;
Node tempHead = head;
int count = 0;
Node p, q = tempHead;
while(q != NULL && count++ < n)
q = q->next;
if(count == n+1){
p = tempHead;
while(q->next != NULL){
p = p->next;
q = q->next;
}
p->next = p->next->next;
return true;
}else if(count == n){
head = head->next;
return true;
}else{
return false;
}
}
int main(int argc, char* args[]){
Node head = createSLL(8);
printSLL(head);
if(deleteNthElement(head, 8)){
cout << "delete success..." << endl;
printSLL(head);
}else{
cout << "fail to delete node..." << endl;
}
return 0;
}
1. Have two pointers ptr1 and ptr2 pointing to head of linked list
- siva December 10, 20122. Traverse one pointer say ptr2 to distance n from head
3. Now, traverse both
4. When ptr2 reaches the tail, ptr1 is at distance "n" from the tail of linked list
Need to do validation like
1. null check,
2. n might be greater than the length of linked list,
3. loop check and etc.,