## Microsoft Interview Question for Developer Program Engineers

• 0

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

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?

Comment hidden because of low score. Click to expand.
0

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.

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.

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

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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.

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

Comment hidden because of low score. Click to expand.
0

Its correct .. this question was asked in written test

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

Can you do this Inplace??

Comment hidden because of low score. Click to expand.
0

Yes you can do it in place.

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

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

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

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

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

{
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

}

}

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.

Comment hidden because of low score. Click to expand.
0

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

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)

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;
} else {
}
}
return first;
}

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

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

Recursive solution

``````void Interchange(NODE* 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;
int i = 0;
while(i < iterations)
{
temp = cur->next;
cur = temp;
i++;
}
// charlisthead will now point to the next batch of conseq integer/conseq char list
}``````

Comment hidden because of low score. Click to expand.
0

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

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

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

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();
}
}``````

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

``````var list = new LinkedList<char>();

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();``````

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)???

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

``````ListNode* change(ListNode* head)
{

ListNode* h, t ;
{
if (h == NULL) h = t = head;
else t = t->next = head;
}
else {
if (h == NULL) h = t = head;
else t = t->next = head;
}
}
if (t) t->next = NULL;
if (t) t->next = NULL;
return merge(h, h, 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; }

}``````

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

Steps:
1) Take two pointer named alpha , num.
2) Traverse list and keep adding alphabets to alpha and numbers to num.
3) Do Merging somewhat similar to MergeSort. Pass a reference of count. Check for each recursive step if count%2==0 and add num if true else add alpha to result.
4) You're done congrats. Time Complexity: O(n) + O(n) = O(n)

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

}``````

}

Comment hidden because of low score. Click to expand.
0

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

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.

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