Microsoft Interview Question
Developer Program EngineersCountry: 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