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.

- sd September 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

+1
very creative!

- Miguel Oliveira September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- pallavi September 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- sd September 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice one

- kanchan September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.... :)

- kanchan September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- rohit.paturi September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sd September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

aha, genius!

- chuang24@buffalo.edu September 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Most efficient code :)

- Ashish Singhal September 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- celicom September 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simple implementation for described idea :

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

            Node doubledHead = head;

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

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

                head.Next = copy;
 
                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 copyHead = doubledHead.Next;
            Node copyTail = null;
            while (doubledHead != null)
            {
                Node copyNode = doubledHead.Next;

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

                copyTail = copyNode;

                doubledHead = doubledHead.Next.Next;
            }

            return copyHead;
        }

- ZuZu September 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

here is the c++ version of it

node* deepcopy()
{
	if(!this->head) return NULL;

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

	node* newHead = this->head->next;
	cur = newHead;
	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
	cur = this->head;
	while(cur) {
		node* tmp =  cur->next;
		if(cur->next){
			cur->next = cur->next->next;
			cur = tmp;
		} else {
			break;
		}
	}

	return newHead;
}

- tj October 02, 2013 | Flag
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;
node = head;
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;

- regg September 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Miguel Oliveira September 18, 2013 | Flag
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;
}

- moiskim September 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- maillist.danielyin October 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

node *temp=head;
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;


}

- 1517 September 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 1517 September 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- maillist.danielyin October 06, 2013 | Flag
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).

- Anonymous October 17, 2013 | Flag Reply
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?

- GK October 19, 2013 | Flag Reply
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.

- trent.tong September 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Miguel Oliveira September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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,

- kanchan September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- gokayhuz September 19, 2013 | 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