## Microsoft Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

1. copy the 1st node and insert it between node 1 & node 2
3. Similarly, copy 2nd node and insert it between 2 & 3.. and so on
2) Copy the arbitrary link in this fashion
Originalnode->next->arbitrary = Originalnode->arbitrary->next;
and so on...for all nodes
3) Separate the original and copy linked lists.

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

+1
very creative!

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

Hi, I could not really understand what you meant by copy 1st node, insert between node 1 and node 2..

does it mean Original_node 1 --> copied node 1 --> Original_node2 again?
can you give an example as to how it works?

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

OriginalNode1 --> CopiedNode1 --> OriginalNode2 --> CopiedNode2 --> OriginalNode3 --> CopiedNode3 --> NULL

The above linklists merge as well as separation should be simple.

Now, lets say OriginalNode1 --> Arbitrary = OriginalNode3

So, as per the above Arbitrary pointer updation logic
Originalnode1 -->next --> Arbitrary (= CopiedNode1 --> Arbitrary) = OriginalNode1 --> Arbitrary --> next (= OriginalNode3-->next = CopiedNode3)

which is essentially same as CopiedNode1 --> Arbitrary = CopiedNode3
And so on....

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

nice one

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

I got the same question in microsoft coding round, but I did it in the other way which is not so efficient... Thanks for this great idea.... :)

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

good one but I think the time complexity is not O(n) here,right?

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

It is O(n), but you will need multiple iteration of the list.

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

Does it require the extra space when you separate and return the newly created (copied) linkedlist

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

aha, genius!

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

Most efficient code :)

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

I am not sure, but usually the input for the Copy/Clone is a const, so you cannot insert nodes in the original list , as described in this algorithm. Can this problem be solved with this additional restriction?

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

Simple implementation for described idea :

``````static Node Clone(Node head)
{
if (head == null) return null;

// double original list
while (head != null)
{
Node next = head.Next;

Node copy = new Node { Value = head.Value, Next = head.Next };

}

// set random link
Node originalRunner = doubledHead;
while (originalRunner != null)
{
originalRunner.Next.Random = originalRunner.Random == null ? null : originalRunner.Random.Next;
originalRunner = originalRunner.Next.Next;
}

// seperate lists
Node copyTail = null;
while (doubledHead != null)
{
Node copyNode = doubledHead.Next;

if (copyTail != null) copyTail.Next = copyNode;

copyTail = copyNode;

}

}``````

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

here is the c++ version of it

``````node* deepcopy()
{

node* cur = this->head;
while(cur) {
node* cpy = new node(cur->val, cur->next, cur->random);
cur->next = cpy;
cur = cpy->next;
}

while(cur) {
// resolve random's copy position
cur->random = cur->random != NULL ? cur->random->next : NULL;
// move two nodes further
if(cur->next){
cur = cur->next->next;
} else {
break;
}
}

// fix original list and seperate them again
while(cur) {
node* tmp =  cur->next;
if(cur->next){
cur->next = cur->next->next;
cur = tmp;
} else {
break;
}
}

}``````

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

sd's method is very innovative but will require extra space in the old list (adding nodes in the list). Here is an alternate method which does not use extra space in the old list:

1. Duplicate the list, change newnode->random to point to node->next, change node->next to point to newnode. e.g.:

``````node = head;
while(node!=null)
Node newnode = new Node(node);
Node* next_node = node.next;
newnode.random = next_node ;  //preserve the relationship of the old nodes
node.next = newnode;
node = next_node;``````

2. Iterate through both lists, fill in the random pointer and recover the old list

``````newnode = newhead;
while(newnode!=null)
Node* tmp = newnode.random;	//this stores the next node in the old list
newnode.random = node.random.next;

//revert the old node back
node.next = tmp;
node = node.next;
newnode = newnode.next;``````

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

You are doing the same thing because node.next = newnode; is the same as sd's method to insert the new nodes into the list.

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

The solution from sd should work fine and it is very creative.
Another solution can be,

1. It will create a duplicate linked list. But ->next of the original list will point equivalent node in the new linkedlist.

node* pOld = head;
node* pNew = Null;
node* pNewTail = Null;
while (pOld)
{
if (pNewTail == null)
{ pNew=pNewTail = new node; pNew->val = pOld->val; }
else
{
pNewTail->next = new node;
pNewTail->next->val = pOld->val;
pNewTail = pNewTail->next;
}
node* pCurrent = pOld;
pOld = pOld->next;
pCurrent = pNewTail;
}

2. Then update random pointer of the new linkedlist

node* pOld = head;
while (pOld)
{
pNew->random = pOld->random->next;

pNew = pNew->next;
pOld = pOld->next;
}

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

I totally did not get what your code is doing. pOld->random is supposed to be a node in the linkedlist, whose next is another node right behind it. I did not see you modify the next pointer. Besides, you cannot trace the nodes by random pointer, what if some nodes` random pointers are NULL?

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

create_list(node *temp){

node *n;
n=new node;

if(temp->next!=NULL){
create_list(temp->next);
}
n->next=temp->next;
n->rand=temp->rand;

}

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

head recursion will create linked list easily......
add just head pointrer i missed out

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

Be careful of the loops baby. You are copying nodes repeatedly.

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

Iterate over the linkedList and create a copy of each node with following changes:
if we make n' as duplicate of node n:
1. n'.random=n.random
2. n.random=n'

Now we iterate over the lists one more time and for every node-duplicate pair:
1. temp=n'.random
2. n'.random=temp.random
3. n.random=temp

This works in O(n).

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

sd's code traverses the list multiple times - to insert and to separate the lists. Is the time complexity still O(N). If so, can someone please elaborate?

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

I am not sure i got the what this question is asking for entirely. why can not one copy the linked list based on the next pointer first and fix up the random node pointer after the linked list is copied.

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

After copying the list based on the next pointer, when you try to copy the random pointers, you don't know that is the correct element pointer by the random pointer in the cloned list.

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

yes, you can, but it takes time coz u need to compare original->random to all other nodes in that list and as you are moving in the other list also,

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

This is possible but would yield a O(n^2) solution with a space complexity of O(n^2).

The optimal solution has time complexity of O(n) and space complexity of O(1)

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.