## Microsoft Interview Question for Software Engineer / Developers

• 5

Team: Office
Country: United States
Interview Type: In-Person

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

We can do this without modifying the list in a single pass using the hashmap where we save the reference of visited node.

``````public Node customizedClone(Node h){
Node newHdr = null;
HashMap<Node, Node> nodeHash = new HashMap<Node, Node>();
Node temp = h;
Node prev = null;
while(temp != null){
Node newNode = null;
Node randomNode = null;

if(!nodeHash.containsKey(temp)){
newNode = new Node();
newNode.data = temp.data;

nodeHash.put(temp, newNode);

}

if( temp.random != null && !nodeHash.containsKey(temp.random)){
randomNode = new Node();
randomNode.data = temp.random.data;
nodeHash.put(temp.random, randomNode);
}

newNode = nodeHash.get(temp);
randomNode = nodeHash.get(temp.random);
newNode.random = randomNode;
if(prev != null){
prev.next = newNode;
}
else{
newHdr = newNode;
}
prev = newNode;
temp = temp.next;
}
return newHdr;
}``````

The space complexity is O(n) and time complexity is O(n)

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

Could you explain ur code

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

The idea is u create a mapping for the new node of the list u are creating. So the key for map is the node of the given list and the value for the map is new node of the list that is being cloned.
So we start scanning the the given list and for each node we create a new node if it is not there and in the same iteration we we also enter the entry for the 'other' node which in my code is 'random' node and make a chain of next and random ( other).

Comment hidden because of low score. Click to expand.
5
of 7 vote

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

best solution..!!!

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

In an interview i would give three successive solutions
1. O(n2) .
Iterate and create a duplicate list with arbit pointing to null.
for each node in copy search in original and fix arbit.
2. Since in above the complexity is because of search. Use Hash map. So complexity is O(n) and space O(n)
3. The best solution as given by anirban.

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

Here is my approach:

loop1:
while(temp != null)
{
if(temp->data < smallNode.data)
{smallNode = temp;}
newNode = getNewNode();
newNode->data = temp->data;
nextNode = temp->next;
temp->next = newNode;
newNode->next = nextNode;
temp = nextNode;
}

loop2:
temp = smallNode;
while(temp->random != null)
{
temp->next->random = temp->random->next;
temp = temp->random;
}
temp->next->random = null;

loop3:
while(temp != null)
{
temp->next = replicate->next;
if(temp->next != null)
{replicate->next = temp->next->next;}
else
{replicate->next = null;}
temp = temp->next;
replicate = replicate->next;
}

Complexity: O(3N), O(1) space.

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

Here is how it works with an example:
List: 9->5->7
9 random points to Null
5 random points to 7
7 random points to 9.

After loop1 list:
9->9->5->5->7->7.
New duplicate nodes added after each original node. We also found smallNode, i.e. 5 in this loop. Only next pointer is set for new nodes.

After loop2:
startWith small Node and assign the random pointer for new Nodes.
9->9->5->5->7->7.

After loop3:
Now we have two a list with duplicate values. separate them into two lists.
9->5->7
9->5->7.

Hope this works:)

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

Can we not just traverse the linked list and create a new node for each node traversed and assign all the values (data, next pointer and random pointer) to the new node ... the random pointer that points to the successor has also got to be just assigned

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

How do you assign this random pointer, that is the question ???
It can't be assigned directly as you are thinking ?, make a linked list of this type and apply what you are saying, then analysis whether you are correct or not,

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

problem is "other" pointers will be different as this is a newly created list

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

It can be done in O(n) & O(1) even though random pointer is pointing to anywhere in the list.
I am not considering the space which you'll need for new list.

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

Can be done, how? Please explain the algorithm.

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

Assumption : Every element is unique.
1) Traverse through the linked list and create the new linked list with same data and next values and keep random pointer as NULL. For every element, save the address of current node to hash(data of current node).
e.g. 1->8->3->6->81->2
hash(1) = address of node 1
hash(8) = address of node 8
...

2) Again run the loop, and from the initial linked list; get the data value at address pointed by random pointer. Use this data as an input to hash() function to get the address in newly created linked list and assign that address in random pointer of newly created linked list.

The linked list is traversed twice, so time complexity is O(2N) = ~ O(N)
Space complexity : O(N)

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

Given List = 1->2->3->4->5->NULL
(I am only showing next pointer here, but you will get the idea)

Step 1 - Push a new node after every node

List - 1->1->2->2->3->3->4->4->5->5->->NULL
(Here first 1 is from old list, second 1 is new node we appended)

Step 2 - Do as following for each node.
node->next->random = node->random->next;

Step 3 - At the end just pop out newly added nodes.
and make old list's last node's next as NULL

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

The solution is correct but you have violated 2 things:

1.you haven't copied the list. After performing these operations, still only 1 list exists in memory albeit it contains the new nodes.

2.You are not allowed to modify the existing list.

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

This cannot be solved without modifying the existing link..
Actually, we can but the time complexity will be O(n2).

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

I did it in O(n) time and O(n) memory withouth modify the original list

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

Yeah ! Solution is violating rules. But, I could not figure out how to do within restrictions.

@francisco.gutierrez.91: Can you give some idea/hint of your algorithm, so that we can get some direction.

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

Guys I have already given you the algorithm below to solve it in O(n) time and space.

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

After Step-3 you can split the linked list alternately.......
like 1st , 3rd , 5th .....nodes as 1st list( original)...
2nd , 4th , 6th ....nodes as 2nd list ( copy list)...
correct me if i am wrong....

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

node copy(node root){
HashMap old=new HashMap();
HashMap now=new HashMap();
int i=0,j=0;
oldfirst=root;
while(root!=null){
old.put(root,i);
root=root.next;
i++;}
while(j<i-1){
node tmp=new node();
j++;
root=oldfirst;
root=root.next;}
return first;}

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

List A
node1.next = node2;
node1.other = node3;

node2.next = node3;
node2.other = node4;

//loop the la as ListA
//lb is our new copy ListB

Node* curLa = la.begin();
Node* curLb = new Node();

// the first is the address be referred
// the second is the real address of node
// we will know second->other = first
// just consider first is single referred by one node;
// otherwise map<Node*, Node*> map_ref change to map< Node*, vector<Node*> >
map<Node*, Node*> map_ref;
map<Node*, Node*>::Iterator it;
while(curLa)
{
Node* p = new Node();
curLb->next = p;
it = map_ref.find(curLa);
if(it != map_ref.end());
{
it->first->other = p;
}

map_ref[curLa->other] = p;
curLa = curLa->next;
curLb = curLb->next;
}

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

I dont see what the problem is here ... we just have to make a copy right ?
we can traverse through the list using node->next;
So we start a new list and copy the contents just like copying an array.

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

Try to understand the problem, need to copy "other" pointer where the actual difficulty is.

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

@hunterr986: like you, I misunderstood the problem.
The problem is, you must make a new linked list, i.e. new nodes in memory. But you must also assign the 'other' pointers to their correct positions for these new nodes. This is not so easy, as the 'other' pointers are allocated to random nodes in the old list. Simply copying the values of the other pointers form the old LL will make the other pointers of the new LL point to the old LL's nodes. We want to make them point to the corresponding new LL's nodes. This is the problem.

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

Isint this a Graph? I can use DFS search algorithm and on every node traversal, I create a node and add corresponding links. Will update with code soon.

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

``````#include<stdio.h>

struct node
{
int data;
struct node * next;
struct node * other;

};

struct node * newnode(int data)
{
struct node * newnode=(struct node *)malloc(sizeof(struct node));
newnode->next=NULL;
newnode->other=NULL;
newnode->data=data;
return newnode;
}

{
static struct node * temp=NULL;
{
newn->next=temp;
temp=newn;
}
}

{

{

}

{
}

}

void printlist(struct node * root)
{
while(root!=NULL)
{
printf("\n data of node is :%d",root->data);
printf("\n other of this node is :%d",(root->other)->data);
if(root->next)
printf("\n next of this node is :%d",(root->next)->data);
printf("\n\n");
root=root->next;
}

}

int main()
{

printf("\n\noriginal list is :\n \n");

printf("\n\n copy list is :\n \n");

return 0;

}``````

Output:

original list is :

data of node is :1
other of this node is :3
next of this node is :2

data of node is :2
other of this node is :1
next of this node is :3

data of node is :3
other of this node is :2

copy list is :

data of node is :1
other of this node is :3
next of this node is :2

data of node is :2
other of this node is :1
next of this node is :3

data of node is :3
other of this node is :2

this is the full code in C . but it doesnt preserve the original list.

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

The key here is that if a node in the original list has an other pointer which is not NULL, you have to allocate the node pointed to by other as well and all other nodes along the chain to that node, in a cascading manner. This is non trivial but we might be able to leverage recursion to do this. I was too lazy to finish the code, but here's a basic outline. I'm sure there are edge cases I haven't handled.

``````void copy_list(node*& head, node*& tail, node*& newHead)
{

while(ptr != tail)
{
if(ptr->other == NULL)
{
{
}
else
{
while(insertPtr->next != NULL) insertPtr = insertPtr->next;

insertPtr->next = create_node();
}
}
else
{
//recurse and create chain from "ptr" upto "other"
while(innerPtr->next != NULL)
{
//append to list
}
}
}
}``````

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

• get length of the list , let us say it is n
• create another list with all other nodes pointing to NULL. Node* other->NULL
• Traverse given list one node at a time and do following
• get other node value for given linkedlist node
• if null move to next node
• if non null do following
in new loop search for location of this address in a given original list
traverse the new list with same with
once the address is found, update the new linkedlist node' other value with node address that has been found while traversing list.

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

It's not that simple, how do you know wich node in thenew list you have to point to

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

Copying other pointer is not easy, Other pointer should be recaclulated as per the new linked 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.