## Microsoft Interview Question

Developer Program Engineers**Country:**India

**Interview Type:**Written Test

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.

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

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.

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.

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)

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

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

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

}

}

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.

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;

}

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

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

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

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

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

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)

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

}

1) Take two Pointers at Head of linked list say P1 and P2

- Anonymous October 31, 20112) 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