Microsoft Interview Question
Software Engineer / DevelopersTeam: Office
Country: United States
Interview Type: In-Person
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).
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.
Here is my approach:
loop1:
temp = smallNode = head;
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:
replicateHead = head->next;
temp = head;
replicate = replicateHead;
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.
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:)
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
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,
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.
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)
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
Comments Welcome
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.
This cannot be solved without modifying the existing link..
Actually, we can but the time complexity will be O(n2).
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.
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++;}
node head=new node();
node first=head;
now.put(j,head);
while(j<i-1){
node tmp=new node();
head.next=tmp;
head=tmp;
j++;
now.put(j,head);}
head.next=null;
head=first;
root=oldfirst;
while(head!=null){
head.other=now.get(old.get(root));
head=head.next;
root=root.next;}
return first;}
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;
}
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.
Try to understand the problem, need to copy "other" pointer where the actual difficulty is.
@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.
#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;
}
void func(struct node * head1,struct node **head2)
{
static struct node * temp=NULL;
if (head1!=NULL)
{
func(head1->next,head2);
struct node * newn= newnode(head1->data);
newn->next=temp;
*head2=newn;
temp=newn;
}
}
void fun(struct node * head1, struct node **head2)
{
struct node *resultlist=*head2;
struct node *head1temp=head1->next;
while(head1!=NULL)
{
head1->next=(*head2);
(*head2)->other=head1;
(*head2)=(*head2)->next;
head1=head1temp;
if(head1temp)
head1temp=head1temp->next;
}
*head2=resultlist;
while((*head2)!=NULL)
{
(*head2)->other=(*head2)->other->other->next;
(*head2)=(*head2)->next;
}
*head2=resultlist;
}
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()
{
struct node* head2=NULL;
struct node * head1=newnode(1);
head1->next=newnode(2);
head1->next->next=newnode(3);
head1->other=head1->next->next;
head1->next->other=head1;
head1->next->next->other=head1->next;
printf("\n\noriginal list is :\n \n");
printlist(head1);
func(head1,&head2);
fun(head1,&head2);
printf("\n\n copy list is :\n \n");
printlist(head2);
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.
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)
{
if(head == NULL) return;
node* ptr = head;
while(ptr != tail)
{
if(ptr->other == NULL)
{
if(newHead == NULL)
{
newHead = create_node();
}
else
{
node* insertPtr = newHead;
while(insertPtr->next != NULL) insertPtr = insertPtr->next;
insertPtr->next = create_node();
}
}
else
{
//recurse and create chain from "ptr" upto "other"
node* innerHead = NULL;
copy_list(ptr, ptr->other, innerHead);
node* innerPtr = innerHead;
while(innerPtr->next != NULL)
{
//append to list
}
}
}
}
• 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.
We can do this without modifying the list in a single pass using the hashmap where we save the reference of visited node.
The space complexity is O(n) and time complexity is O(n)
- Prajwal Rupakheti January 24, 2013