Microsoft Interview Question Software Engineer in Tests

  • microsoft-interview-questions
    0
    of 0 votes
    21
    Answers

    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.

    - Abhinav on May 19, 2010 Report Duplicate | Flag
    Microsoft Software Engineer in Test Algorithm C Coding



Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- gevorgk on May 20, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is a O(N) solution.

- Charles on January 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- d on May 19, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for second part, consider 2t-1 element. You cannot simply delete all starting from t.

- Siddique on August 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

gevorgk is correct. Move to the t'th element in the list and delete that element and all remaining elements in the list.

- dfmcla on May 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous on June 03, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

chutyaa banaane ke liye ham log hi mile the tujhe
?

- markZukerberg on June 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Agent on June 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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...

- Sal on June 16, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is correct..

- Anonymous on March 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right, but not just the 20->null, all the memory used in LL following 20 should be deleted.

- shanuapril on December 11, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

2nd Part
Delete every 't' th node till node->next=node

- Arun on July 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@sal- dude u deserve to be in microsoft or amazon...do u think careercup r bunch of fools to publish d question the way u interpreted......wow :)...wat an answer

- logical head on July 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

guys use 2 pointers...
one will traverse the link list...
other will delete the required node and move by required t postion....
the complexity is o(n)...as d slow pointer is the one which will set the loop condition

- logical head on July 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

guys use 2 pointers...
one will traverse the link list...
other will delete the required node and move by required t postion....
the complexity is o(n)...as d slow pointer is the one which will set the loop condition

- logical head on July 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This looks like "Lucky Numbers" problem. Please take a look in geeksforgeeks.org

- aaa on August 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can solve the problem in O(nlogn)

- python.c.madhav on August 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can solve the problem in O(nlogn)using tree

- python.c.madhav on August 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

^ throw some lights buddy

- Anonymous on September 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

This is Josephus problem.

- Murali Mohan on October 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ye joseohus hai toh kyaa hilaau teraa ?

- CoolCoder on June 02, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More