## Microsoft Interview Question Software Engineer in Tests

- 0of 0 votes
Given a very very long linked list with 'n' nodes.

Also given a positive integer 't'>1.

Delete every 't'th node. In the resultant linked list, again delete 't'th node. Repeat this till only t-1 nodes remains.

Find the node.

Eg:

Linked list : 10->20->30->40->50->60->70

n = 7

t = 3

Phase 1:

10->20->40->50->70

Phase-2:

10->20->50->70

Phase-3:

10->20->70

Phase-4:

10->20

Simple solution with many traversals is obvious.

Is there a solution with one traversal or O(n)?

b) Similar for circular linked list.

Keep deleting 't'th node till 1 node remains.

Note here not till 't-1' nodes but till 1 node remains.

for first part - delete all elements starting from 't'th node to end of list

for second part - delete elements starting from 't'th node to end

now only t-1 elements are remaining, delete the first node from that list - since a traversal of t nodes from 1st node on a list of length t-1 would end at 1st node

From there on follow simple traversal and delete nodes.

Wondering if the last part can be generalized

MS IDC makes fool of people.

People have to come to office on weekends due to workload and do night outs, no work life balance. They pay 10-20% more make people labour.

Do take the feedback from employees before joining MS.

And work is junk, all junk wor from Redmond is transferred to IDC. Ask any team, whether they design, implement products or just do porting or maintenance or make tools.

For a circular list:

```
node* RemoveTthNode(int t)
{
node *curr=head;
node *temp;
int count=1;
//limiting condition(circular list with only 1 element)
while(curr!=curr->next)
{
if (count==t-1)
{
temp=curr->next;
curr->next=temp->next;
free(temp);
//Reset count after deleting Tth node
count=1;
}
else
{
count++;
curr=curr->next;
}
}
return curr;
}
```

What I don understand here is the steps involved.

The problem statement is very simple. You have to delete the

Tth node until t-1 nodes are left.

So why don we initialize the link of t-1 th node to null i.e., in the above example..

10->20->40->50->70

step 1: 10->20->null // list ends here...

Obviously for first task only first t-1 elements in list will survive.

- gevorgk on May 20, 2010 Edit | Flag Reply