Microsoft Interview Question for Developer Program Engineers


Country: India
Interview Type: Written Test




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

1) Take two Pointers at Head of linked list say P1 and P2
2) Move P2 till isDigit = true
3) Move node pointed by P2 to P1 next
4) Move P2 by 1 Move P1 by 2
5) Repeat step 2,3,4 till P2 != null

- Anonymous October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will not work. Since this is a Singly linked list, you cannot just do step (3). You need to ensure that the list does not break connectivity at any point.

- Anonymous January 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Modified a bit

1) Take two Pointers at Head of linked list say P1 and P2
2) Move P2 till isDigit = true and store P2prev node
P2prev->next= P2->next
P2->next= P1->next
P1->next=P2
P1=P1->next->next
3) Move node pointed by P2 to P1 next
4) Move P2 by 1 Move P1 by 2
5) Repeat step 2,3,4 till P2 != null

- nikhil May 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How are you supposed to know which nodes are numbers and which nodes are letters?

- eugene.yarovoi October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

a. attempt to parse the value
b. use Character.isDigit(char c)

Usually the interviewer will say - "let's assume there's a method, which tells you whether the value is a number or a character", if you don't tell them right away how you are going to check for number/character and then you back to the drawing board.

- Anonymous October 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo :-

Convert it into two array one with only digit and another with only character.
Sort each of this array.
Read each of this array respectively and make a link list.

Time Complexity :- O(n) + O(nlogn) + O(n) = O(nlog n)
Space Complexity :- O(n/2) + O(n/2) = O(n) extra space.

- hprem991 October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually it is better to convert it into two linked lists. One containing only numbers and other only characters.

Then we can do a merge of these two lists.

Time Complexity O(n)
Space Complexity O(1)

- Anonymous October 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dude, how is your space complexity O(1) with 2 extra linklists (o_0)?????

- ^^ November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

U are just using 2 extra header node ,
u r not creating new nodes for creating the 2 new list
Yeah but the problem with this solution is that u lose the original list.

- san November 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have little Confusion about the given I/p

1->2->3->4->a->b->c->d->5->6->e->f

Is it Correct or It Should be like

1->2->3->4->5->6->a->b->c->d->e->f

Please help!!!!

- User October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its correct .. this question was asked in written test

- msankith October 31, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you do this Inplace??

- RushHour November 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes you can do it in place.

- Anonymous November 06, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

pseudo code:

node* current = begining_of_list;
int location = 1;
while( current != NULL)
{
    if(location % 2 == 1 && isDigit(current->element) ) //Ele is a number, OK
    {
        location++;
        current = current -> next;
        continue;
    }
    else
    {
        for( node* temp = current; temp!= NULL; temp= temp->next)
        {
            if( isDigit(temp->ele) )
            {
                node* mid->ele = temp->ele;
                temp->ele = current->ele;
                current->ele = mid->ele;
                break;
            } 
        }
    }
    if(location % 2 == 0 && !(isDigit(current->element)) ) //Ele is a char, OK
    {
        location++;
        current = current -> next;
        continue;
    }
    else
    {
        for( node* temp = current; temp!= NULL; temp= temp->next)
        {
            if( !isDigit(temp->ele) )
            {
                node* mid->ele = temp->ele;
                temp->ele = current->ele;
                current->ele = mid->ele;
                break;
            } 
        }
    }
}

- shanuapril November 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This comment has been deleted.

- Administrator November 11, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Majority of the interview questions are focussed on creating the required solution!

- kratznick November 13, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

node * jumptoNextAlpha(node *a)
{
while(a!= null && isDigit(a->value))
{
a = a->next;
}
return a;
}

node * jumpToNextDigit(node *n)
{
while(n!=null && !isDigit(n->value)
{
n = n->next;
}
return n;
}

void swapNodeValues(node *a,node *b)
{
int value = a->value;
a->value = b->value;
b->value = value;
}

void orderList(node *head)
{
node *current = head;
node *alphaPtr = jumpToNextAlpha(head);
node *numberPtr = jumpToNextDigit(head);
int i = 0;
while(current != null && numberPtr!=null && alphaPtr!=null)
{
if(i%2==0)
{
if(isDigit(current->value))
{
numberPtr = jumpToNextDigit(numberPtr->next);
}
else
{
swap(alphaPtr,numberPtr);
alphaPtr = jumpToNextAlpha(alphaPtr->next);
numberPtr = jumpToNextDigit(numberPtr->next);
}
}
else
{
if(!isDigit(current->value))
{
alphaPtr = jumpToNextAlpha(alphaPtr->next);
}
else
{
swap(alphaPtr,numberPtr);
alphaPtr = jumpToNextAlpha(alphaPtr->next);
numberPtr = jumpToNextDigit(numberPtr->next);
}
}

current = current->next;
i++;
} //While loop end

}

}

- jagadish.dande November 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep 2 ptrs.
One always pointing to digits, another pointing to letters.

1->2->3->4->a->b->c->d->5->6->e->f
Ptr1 -> 1
Ptr2 -> a

Now temp_int = Ptr1 -> next i.e. temp_int -> 3
Ptr1 -> next = Ptr2 i.e. 1 -> a
Ptr1 = temp_int

Now temp_letter = Ptr2 -> next i.e. temp_letter -> b
Ptr2 -> next = Ptr1
Ptr2 = temp_letter

Continue like this.

- Srikant Aggarwal December 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not that easy, you need to also consider when first Numeric list will reach to alphanumeric list

- pc July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Time Complexity = O(n)
Space complexity = NIL (Assuming we can modify original link lists)

- Srikant Aggarwal December 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

NODE interchange(NODE first)
{
NODE p1, p2, temp;

if (!first)
return first;

p1 = p2 = first;
while(p2 && p1->link->link) {
if(p2->link && isdigit((p2->link->info))) {
p2 = p2->link;
} else {
temp = p2->link;
p2->link = temp->link;
temp->link = p1->link;
p1->link = temp;
p1 = p1->link->link;
}
}
return first;
}

- Veena December 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1->2->3->4->a->b->c->d

SWAP 3,4 with a,b and split it mid-way

1->2->a->b->3->4->c->d

Recursively do it on 2 pieces:

PIECE 1:1->2->a->b

Swap 2, a
1->a->2->b = DONE

PIECE 2:3->4->c->d

Swap 4,c
3->c->4->d = DONE

We can write recursive solution for it very easily!!

- Anonymous December 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive solution

void Interchange(NODE* listhead)
{
    NODE* cur = listhead;
    NODE* curend = NULL, prev = NULL, charlisthead = NULL,temp = null tempcharList = NULL; 
    if (cur == NULL) 
          return;
    int iterations = 0;
    // find the first non-digit node
    while( IsDigit(cur->data) == true)
    {
         prev = cur;
         if( cur->next != NULL )
         {
             iterations++
             cur = cur->next;
         }
         else break;
    }
    
    // Now cur points to the first node of the list of Alphabets AND prev points to the last node of the list of integers. Save it
    curend = prev;
    charlisthead = cur;
    cur = listhead;
    int i = 0;
    while(i < iterations)
    {
       temp = cur->next;
       cur->next = charlisthead;
       savecharList = charlisthead->next;
       charlisthead->next = temp;
       cur = temp;
       saveprevhead = charlisthead;
       charlisthead = savecharList;
       i++;
    }
    // charlisthead will now point to the next batch of conseq integer/conseq char list
    saveprevhead->next = Interchange(charlisthead)
    return listhead;       
}

- Anonymous December 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Won't this algorithm fail for this input
1->2->a->b->c->d->3->4->5->e->f->null
From 2 node, you will traverse to a with a circular link list created

- pc July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) iterate through the list (while node->value! = 'f'), if you find a char ( this can be checked by if node->value == 'c' and so on) delete it from its current position and insert it to the tail of the list. after the first iteration the lists looks like this
1- 2-3-4-5-6-a-b-c-d-e-f
2) take two pointers one pointing to head(p1) and another pointing to middle+1(p2) position. iterate p1 till the middle. for each iteration insert p2 between p1 and p1->next, for eg insert a between 1 and 2 , insert b between 2 and 3 and so on.After the iteration the list would become

1-a-2-b-3-c-4-d-5-e-6-f

- vivekh February 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a TreeMap (SortedMap) , add digit as key and if character comes , add the value to the sequence , so will get 1-a , 2-b , 3 -c , d-e and then list down the elements in sequence

- Abhishek April 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void skip_m_del_n (int m, int n) {
    if (root == NULL) {
        cerr << "Error: No elements in the linked list" << endl;
        return;
    }

    Node *tmp = root;
    while (tmp) {
        int i = 0;
        Node *prev = NULL;

        //Skip m
        for (i=0; tmp && i<m; i++) {
            if (i == m-1)
                prev = tmp;
            tmp = tmp->next;
        }
        if (!tmp) {
            continue;
        }

        i = 0;
        //Delete n
        for (i=0; tmp && i<n; i++) {
            Node *tmp1 = tmp;
            tmp = tmp->next;
            tmp1->next = NULL;
            free (tmp1);
        }
        prev->next = tmp;
        print();
    }
}

- Sam May 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

var list = new LinkedList<char>();
            list.Add('1');
            list.Add('2');
            list.Add('3');
            list.Add('4');
            list.Add('a');
            list.Add('b');
            list.Add('c');
            list.Add('d');
            list.Add('5');
            list.Add('6');
            list.Add('e');
            list.Add('f');

            list.Print();
            
            var listPointer = list.Root;
            var numberPointer = list.Root;
            var letterPointer = list.Root;
            var lookingForNumber = true;
            while (listPointer != null)
            {
                var temp = listPointer.Value;
                if (lookingForNumber)
                {
                    while (numberPointer != null && !char.IsDigit(numberPointer.Value))
                    {
                        numberPointer = numberPointer.Next;
                    }

                    if (numberPointer == null)
                    {
                        break;
                    }

                    listPointer.Value = numberPointer.Value;
                    numberPointer.Value = temp;
                    numberPointer = numberPointer.Next;
                }
                else
                {
                    while (letterPointer != null && char.IsDigit(letterPointer.Value))
                    {
                        letterPointer = letterPointer.Next;
                    }

                    if (letterPointer == null)
                    {
                        break;
                    }

                    listPointer.Value = letterPointer.Value;
                    letterPointer.Value = temp;
                    letterPointer = letterPointer.Next;
                }

                listPointer = listPointer.Next;
                lookingForNumber = !lookingForNumber;
            }

            list.Print();

- Shtin July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i have an doubt. how a linkedlist will have both type Node(one char Node and one int Mode)???

- goel August 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ListNode* change(ListNode* head)
{
      if (head == NULL || head->next == NULL) return head;

      ListNode* h[2], t[2] ;
      while (head != NULL)
      {
               if (head->val >= '0' && head->val <= '9') {
                           if (h[0] == NULL) h[0] = t[0] = head;
                           else t[0] = t[0]->next = head;
               }
               else {  
                           if (h[1] == NULL) h[1] = t[1] = head;
                           else t[1] = t[1]->next = head;
               }
              head = head->next;
      }
      if (t[0]) t[0]->next = NULL;
      if (t[1]) t[1]->next = NULL;
      return merge(h[0], h[1], true);
      
}

ListNode* merge(ListNode* a, ListNode* b, bool flag)
{
         if (a == NULL) return b;
         if (b == NULL) return a;
         if (flag) { a->next = merge(a->next, b, !flag); return a; }
         else { b->next = merge(a, b->next, !flag); return b; } 
         
}

- Anonymous August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

// considering i/p: 1->2->3->4->a->b->c->d->5->6->e->f

        //step 1: start from left. scan till first char occurs. It is 
        //keep start node(where the first int occured),prevToStart(previous to start node.First time
        //it is present node itself).also count number of non-chars before the current char.
        
        //step 2: loop till the count. detach each node from start position , attach it to the left of the current node.
        //increment the start node to next position.Keep the prevToStart=start.
        
        public static void Rearrange(Node list)
        {
            if (list == null)
                return;
            Node prevToStart = null, start = list, prevToCurrent = null, current = list;
            int i = 0, count = 0;

            while (current != null)
            {
                //finding till first char occurs
                if (current.Ch >= '0' && current.Ch <= '9')
                {
                    //count of integers before first char
                    count++;
                    current = current.Front;
                }
                else
                {
                    //loop till count
                    while (i < count )
                    {
                        Node nextToStart = start.Front;
                        if (prevToStart != null)
                        {
                            // here we are taking the Front link right from the char node in the previous case
                            //eg. 1->a->. prevToStart at 1 and taking Front link from 'a'
                            //and storing address of present start node '2'. so 1->a->2. 
                            prevToStart.Front.Front = start;
                            //then pointing prevToStart to '2'
                            prevToStart = start;
                        }
                        else
                        {
                            prevToStart = start;
                        }
                        start.Front = current;
                        start = nextToStart;
                        i++;
                        prevToCurrent = current;

                        //if there is no suffient nodes avaialable for sawpping, just return
                        if (current.Front != null)
                            current = current.Front;
                        else return;
                    }
                    prevToStart = prevToCurrent;
                    start = prevToCurrent.Front;
                    count = 0;
                    i = 0;
                }

            }

}

- BVarghese December 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will fail with smaller numric list followed by longer apphabetic list

- pc July 06, 2012 | Flag


Add a Comment
Name:

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

Books

is a comprehensive book on 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